Polinomiale tempo riducibilità

Question

$ L_1 $ e $ L_2 $ sono due lingue definite sull'alfabeto $ \ somma $. $ L_1 $ è riducibile a $ L_2 $ in tempo polinomiale. Quale delle seguenti non può essere vero?

• $ L_1 \ in P $ e $ L_2 $ è finito
• $ L_1 \ in NP $ e $ L_2 \ in P $
• $ L_1 $ è indecidibile e $ L_2 $ è decidibile
• $ L_1 $ è ricorsivamente enumerabile e $ L_2 $ è ricorsiva

Il mio ragionamento è il seguente,

Se $ A \ le_p B $ e $ B \ in P $, quindi $ A $ possono essere ridotti a $ B $ in tempo polinomiale e risolti in tempo polinomiale facendo $ A \ in P $. Così ho inizialmente pensato che il 2 ° scelta come falsa, e quindi la risposta giusta.

Tuttavia usando lo stesso argomento sulla mappatura riducibilità, il 3 ° scelta sembra essere falso pure. La quarta scelta è la stessa come il terzo.

Sono stato infruttuoso nel ragionamento nulla del 1 ° scelta.

Per mettere le mie argomentazioni di cui sopra nel contesto, sto imparando sulla teoria della computazione e hanno appena circa scremato la superficie della teoria della computabilità e della complessità. me Helo fuori.

Answer 1

Tre delle opzioni utilizzano lo stesso trucco: se $ C1, C2 $ sono due classi di linguaggi e di $ C1 \ subseteq C2 $; allora $ L1 \ in C2 $ non implica che $ L1 \ notin C1 $.

L'unica scelta che non può essere fatto vero è 3: se v'è una riduzione del tempo polinomiale da una lingua indecidibile $ L_1 $ ad un linguaggio decidibile $ L_2 $ allora $ L_1 $ diventa decidibile, troppo (solo costruire una macchina di Turing che calcola la riduzione e quindi risolvere il problema applicando il decisore a $ L_2 $) e questo è un contraddizione.