Complexité temporelle des langues qui sont du temps polynomial réductible aux langues complètes NP
-
30-10-2019 - |
Question
Je me demande si vous donne la complexité du temps d'un problème NP-Complete ou au moins quelques informations à ce sujet par exemple si $ sat dans le temps (2 ^ {Sqrt (n)}) $ (hypothétiquement) puis-je supposer que toutes les langues en NP (qui sont clairement le temps polynomial réductible à SAT) sont également $ dans le temps (2 ^ {sqrt (n)}) $
Je crois que la réponse est fausse parce que je pouvais essentiellement choisir n'importe quelle classe arbitraire de fonctions temporelles exponentives et affirmer que toutes les langues en NP y sont contenues alors qu'elle peut réellement appartenir à une classe de puissance supérieure ... mais je ne sais pas comment pour formuler cela comme une preuve.
Pas de solution correcte