réductibilité polynomiale

Question

$ L_1 $ et $ L_2 $ sont deux langues définies sur l'alphabet $ \ sum $. $ L_1 $ est réduit à $ L_2 $ en temps polynomial. Lequel des suivants ne peut pas être vrai?

• $ L_1 \ dans P $ et $ L_2 $ est fini
• L_1 $ \ dans NP $ et L_2 $ \ dans P $
• $ L_1 $ est indécidable et $ L_2 $ est décidable
• $ L_1 $ est récursive et dénombrable $ L_2 $ est récursive

Mon raisonnement est le suivant,

Si $ A \ le_p B $ et $ B \ dans P $, alors $ A $ peut être réduit à $ B $ en temps polynomial et résolus en temps polynomial faisant $ A \ in P $. Ainsi, je me suis d'abord le 2ème choix faux et donc la bonne réponse.

Cependant, l'utilisation du même argument sur réductibilité de cartographie, le 3e choix semble être faux aussi. Le quatrième choix est le même que le troisième.

Je ne réussissait pas à quoi que ce soit au sujet du raisonnement 1er choix.

Pour mettre mes arguments ci-dessus dans le contexte, je suis d'apprentissage sur la théorie du calcul et ont à peu près qu'effleurer le de la théorie de la calculabilité et de la complexité. Helo-moi.

Answer 1

Trois des options utilisent la même astuce: si $ C1, C2 $ sont deux classes de langues et $ C1 \ subseteq C2 $; puis $ L1 \ en C2 $ ne signifie pas que $ L1 \ Notin $ C1.

Le seul choix qui ne peut être fait vrai est 3: s'il y a une réduction du temps polynomiale d'une langue indécidable $ L_1 $ à une langue décidable $ L_2 $, alors $ L_1 $ devient décidable aussi (il suffit de construire une machine de Turing calcule la réduction, puis résoudre le problème en utilisant le decider pour $ L_2 $), ce qui est un Contraddiction.