«Compte tenu d'un algorithme, décidez si cela fonctionne dans du temps polynomial» est-ce que ce problème dans NP?

Question

Ce problème n'est pas décritable (réductible à la haine problème) mais est semi-décitable et qu'il est vérifiable (comme ces deux définitions sont équivalentes: Comment prouver Semi-Decidable= vérifiable? ).

Cependant, ce problème est-il vérifiable poly-time?

Un problème de décision $ p $ est la poly time vérifiable iff il y a un algorithme

Answer 1

Non.Si le problème était vérifiable du temps polynomial, il serait satisfait de l'époque exponentielle et donc enrichissable;Mais nous savons déjà que ce n'est pas décidable.

Pourquoi dans le temps exponentiel?Parce que $ v $ est exécuté dans le temps $ | w $ , il peut lire au plus $ | W | ^ K $ bits de l'entrée.Donc, il suffit d'énumérer toutes les chaînes possibles $ C $ de longueur au plus $ | w | ^ k $ , et courez $ v $ sur chacun d'eux.Le temps d'exécution sera à propos de 2 ^ {| w | ^ k} $ , qui est fini et suffisamment pour rendre le problème initial décidé.