Question

Pourquoi la prochaine idée ne fonctionne pas:

If L_2 in R and L_1 in P and the languages are not trivial, 
then there is a polynomial-time reduction from L_1 to L_2

Je sais que si une telle réduction existe, que L_1 est également dans R -> mais L_1 est en P et P est en R, donc tout va bien :)

Sera heureux de votre aide ici.

Pas de solution correcte

Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange
scroll top