Les épreuves np sont-elles limitées à la longueur polynomiale?

Question

Dans la théorie de la complexité informatique, le NP (temps polynôme non déterministe) est une classe de complexité utilisée pour classer les problèmes de décision.NP est l'ensemble des problèmes de décision pour lesquels les instances problématiques, où la réponse est "oui", ont des preuves vérifiables en temps polynomial par une machine à trouble déterministe.

Les preuves d'un problème de décision NP sont vérifiées en temps polynomial.

Cela implique-t-il que les preuves sont à la plupart une longueur polynomiale?

"Eh bien, vous devez lire l'entrée entière. Si l'entrée est plus longue que polynomiale, le temps est supérieur au polynôme."

Le problème de décision "est le premier bit de l'entrée A 0?"peut être résolu en temps et en espace constant - sans lire l'entrée entière.

Par conséquent, peut-être un problème de NP a des preuves candidates plus longues que la longueur polynomiale mais vérifiée dans du temps polynomial.

Answer 1

Le problème de décision "est le premier bit de l'entrée A 0?"peut être résolu en temps et en espace constant - sans lire l'entrée entière.

Étant donné qu'une tête de machine de Turing se déplace une étape droite à la fois, une tête de machine de Turing ne peut lire qu'une quantité polynomiale de la preuve en temps polynomial.

Bien que vous puissiez définir des preuves pour dépasser une longueur polynomiale, seule une préfixe polynomiale de la preuve pourrait être lue en temps polynomial, en supposant que la tête commence à la cellule 0 et peut se déplacer à une seule cellule maximale dans une unité de temps.

Answer 2

Une preuve d'instance "oui" signifie fournir une solution.Fournir une solution fournit une entrée valide.Par définition, il peut être vérifié dans le temps et l'espace polynomial relativement à l'entrée, sinon ce n'est pas un problème dans NP.

On ignore si toutes les preuves d'instances "non" sont vérifiables dans du temps et de l'espace polynomial (la différence entre NP et CO-NP).

Pour répondre à la question précisément, la preuve d'une instance "oui" est la valeur d'entrée.Vous ne pouvez pas dire que l'entrée a une longueur polynomiale car le polynôme est utilisé lors de la comparaison de la taille d'entrée.Par conséquent, la question est sans signification à cause du mot «polynôme».Si vous voulez vraiment un polynôme quelque part, la taille de la preuve relativement à l'entrée peut être définie comme une fonction linéaire F (x)= AX + B où a= 1 et b= 0, qui peut être simplifié à F (x)= x parce que la taille de l'entrée est égale à elle-même.