J'ai un problème de décision avec 2 ^ N $ Certificats de taille bit, comment vérifierais-je mon problème de décision efficacement s'il est en dollars NP $?

Question

Problème de décision: est 2 ^ k $ + $ M $ A Premier?

Les entrées de $ K $ et $ m $ sont des entiers uniquement. La solution est la somme de 2 ^ k $ + $ M $ . ( Utilisez des AKS pour décider Prime )

les pouvoirs de 2 ont environ 2 ^ n $ chiffres. Considérons 2 ^ k $ où $ k $ = 100000. Comparez la quantité de chiffres dans $ K $ à la quantité de chiffres dans sa solution!

Question

Voir que le certificat de la décision du problème peut être 2 ^ n $ dimensionné, comment puis-je vérifier le problème de décision en polynôme, en considérant que je peux juste regarder le États de transition en tant que certificat en soi?

En d'autres termes, à quoi ressemblerait un vérificateur de temps polynomial pour ce problème de décision?

Answer 1

Un problème de décision a une réponse oui / non, donc il ne peut donc pas avoir une "taille exponentielle".Vous posez des problèmes de recherche, ceux-ci peuvent certainement avoir une taille exponentielle.Et oui, si la taille de la solution (écrite dans un format dûment compact, c'est-à-dire) est exponentielle de la taille du problème d'origine, il est clairement impossible d'écrire même la réponse en temps polynomial.

Dans tous les cas, P et NP s'appliquent strictement uniquement aux problèmes de décision.Mais jetez un coup d'œil à la "Décision vs Search" pour unrelation entre les deux.