Faits: A. Par jugement du 23 octobre 2009, le Tribunal correctionnel du district de La Chaux-de-Fonds a reconnu X._ coupable de remise de substances nocives à des enfants, d'actes d'ordre sexuel avec une enfant, de contrainte sexuelle, de désagréments causés par la confrontation à un acte d'ordre sexuel et d'infractions graves à la loi fédérale sur les stupéfiants, l'a condamné à une peine privative de liberté de quatre ans et demi et a assorti cette peine d'une mesure d'internement au sens de l'art. 64 CP. Pour l'essentiel, le jugement repose sur les faits suivants: Le 14 septembre 2008, alors qu'il circulait en train entre Sonceboz-Sombeval et La Chaux-de-Fonds, X._ a abordé A._, âgée de quinze ans, qu'il ne connaissait pas. Sous la menace d'un couteau, il l'a obligée à fumer de la marijuana et à consommer, à plusieurs reprises, de la cocaïne. Profitant de l'état second et de la crainte dans lesquels il avait ainsi placé sa victime, il l'a embrassée sur la bouche, lui a caressé la poitrine, lui a pénétré du doigt le vagin et l'anus, l'a forcée à lui pratiquer une fellation et a tenté, en vain, de la sodomiser avant de la contraindre à une seconde fellation. Le 15 janvier 2009, il s'est masturbé dans le train reliant Oberbuchsiten et Soleure sous les yeux de B._. Entre juin 2008 et le 15 janvier 2009, il s'est adonné au trafic d'au minimum 44 grammes de cocaïne, dont cinq ont été affectés à sa consommation personnelle. B. Par arrêt du 15 mars 2010, la Cour de cassation pénale neuchâteloise a rejeté le recours de X._. Le 1er octobre 2010, la Cour de droit pénal du Tribunal fédéral a annulé l'arrêt cantonal, en tant qu'il ordonnait l'internement du condamné, et a renvoyé la cause à l'autorité cantonale pour complément d'instruction (arrêt 6B_313/2010). Elle a considéré que l'expertise n'était pas assez précise dans la mesure où il ne pouvait en être déduit s'il existait un danger suffisamment grave et imminent de réitération d'actes d'ordre sexuel avec des enfants ou de contraintes sexuelles. En outre, l'expertise n'apportait pas suffisamment d'éléments pour déterminer si la peine de quatre ans et demi que devait exécuter le condamné pouvait suffire à le dissuader de récidiver. C. Dans un nouveau jugement du 25 octobre 2011, le Tribunal criminel des Montagnes et du Val-de-Ruz (qui a succédé au Tribunal correctionnel à la suite de la réorganisation judiciaire entrée en vigueur en même temps que le nouveau code de procédure pénale le 1er janvier 2011) est arrivé à la conclusion que les conditions d'un internement au sens de l'art. 64 CP n'étaient pas données. Le Tribunal a fondé sa décision sur deux compléments d'expertise des 12 mai et 17 juin 2011, ainsi que sur les déclarations de l'expert lors de l'audience. Par jugement d'appel du 29 mai 2012, la Cour pénale du Tribunal cantonal neuchâtelois a rejeté l'appel du Ministère public neuchâtelois. D. Contre ce dernier jugement, le Ministère public du canton de Neuchâtel dépose un recours en matière pénale devant le Tribunal fédéral, concluant au prononcé d'une mesure d'internement. Invité à se déterminer sur le recours, X._ a déposé une réponse, concluant au rejet dudit recours. En outre, il a sollicité l'assistance judiciaire.