Question

Selon Wikipédia et d'autres références existent un langage complet $ L dans exp $ tel que pour toutes les langues $ L '$ dans $ Exp $ il existe une réduction polynomiale $ f $ qui convertit l'instance de $ L '$ dans $ L $ en temps polynomial. Je crois que cette définition va bien mais j'ai une observation qui me confond. Je construis une langue $ L '' $ dans $ Exp $ tel que $ L '' $ ne peut pas être converti en $ L $ avec des réductions de temps polynomial et $ L '' $ est dans $ Exp $ avec un algorithme M de cette manière:

laisser $ f_i $ être l'itération de toutes les réductions.

1) $ entrée (i, x) $

2) Courir $ f_i (i, x) $ dans le temps au plus 2 $ ^ n $ Si le temps de calcul est supérieur à $ n ^ { log n} $ alors acceptez.

3) Sinon accepter $ (i, x) $ fic $ f_i (i, x) not in l $.

Évidemment $ Language (m) dans Exp $ Il existe donc une réduction de temps polynomiale de $ Langue (m) $ à $ L $ mais cela fait une contradiction car m empêche les réductions de moins que $ n ^ { log n} $ temps de $ L $ Et c'est à cause de la ligne 3 d'Algorithm.Suppose $ f_j $ est la réduction polynomiale, l'adhésion à $ (i, x) $ dans $ L (m) $ est l'opposé du navire membre de $ f_j (j, x) $ alors $ f_j $ n'est pas une réduction de L (m) à L par la ligne 3 de l'algorithme.

Ma question est: où est mon erreur?

Pas de solution correcte

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