Existe-t-il une tâche pouvant être résolue en temps polynomial mais non vérifiable en temps polynomial?

Un de mes collègues et moi-même venons de tirer quelques notes d’un de nos professeurs. Les notes indiquent qu'il existe des tâches qu'il est possible de résoudre en temps polynomial (appartiennent à la classe de PF) mais qui ne sont PAS vérifiables en temps polynomial (ne font pas partie de la classe de NPF).

Pour en savoir plus sur ces classes: Nous obtenons une entrée X et produisons une sortie Y telle que (X, Y) soient en relation R représentant notre tâche. S'il est possible d'obtenir Y pour X en temps polynomial, la tâche appartient à la classe de PF. S'il est possible de vérifier que le certificat de longueur polynomiale Z prouvant qu'un tuple (X, Y) est en relation R en temps polynomial, la tâche appartient à la classe des NPF.

Nous ne parlons pas de problèmes de décision, où la réponse est simplement OUI ou NON (plus formellement si une chaîne appartient à une langue). Pour les problèmes de décision, il apparaît que PF est un sous-ensemble approprié des FNP. Cependant, pour d'autres tâches, cela pourrait être différent.

Connaissez-vous une tâche qui peut être résolue en temps polynomial mais non vérifiée en temps polynomial?

complexity-theory np Drozi
la source

J'ai peut-être mal compris, mais pourquoi ce qui suit n'est-il pas un algorithme de vérification polynomial? Étant donné , calculez vous-même la fonction à l'aide de l'algorithme polynomial et retournez "correct" si . Est-il possible que vous ayez mal interprété ou que le professeur se soit mal exprimé et ait voulu dire au contraire qu'il existe des problèmes vérifiables en temps polynomial mais non résolus en temps polynomial?

(x, y)

$(x,y)$

f (x)

$f(x)$

f (x) = y

$f(x)=y$

Lieuwe Vinkhuijzen

@LieuweVinkhuijzen "pour dire qu'il existe des problèmes vérifiables en temps polynomial mais non résolus en temps polynomial?" [réf. nécessaire]

T. Verron

@ T.Verron Haha oui, je serais moi aussi très heureux de voir la preuve du professeur pour cette affirmation;)

Lieuwe Vinkhuijzen

Réponses:

Ceci n'est possible que s'il existe plusieurs sorties admissibles pour une entrée donnée. C'est-à-dire lorsque la relation n'est pas une fonction car elle viole l'unicité. $R$

Par exemple, considérons ce problème:

Étant donné que (représenté par unaire) et un TM , produisez un autre TM tel que et (où représente le codage (nombre de Gödel) de dans un entier naturel) $n \in \mathbb{N}$ $M$ $N$ $L(M)=L(N)$ $\# N > n$ $\# N$ $N$

La solution à ce problème est simple: ajoutez quelques états redondants au TM , éventuellement avec quelques transitions factices entre eux, jusqu'à ce que son codage dépasse . Ceci est une application de base répétée du lemme de rembourrage sur les MT. Cela nécessitera rembourrages, chacun pouvant ajouter un état, donc cela peut être fait en temps polynomial. $M$ $n$ $n$

D'autre part, étant donné est indécidable pour vérifier si est une sortie correcte pour les entrées . En effet, vérifier est indécidable (appliquez le théorème de Rice), et la contrainte ne supprime que finement beaucoup de s. Puisque nous retirons une quantité finie d'éléments d'un problème indécidable, nous obtenons toujours un problème indécidable. $n,M,N$ $N$ $n,M$ $L(M)=L(N)$ $\#N > n$ $N$

Vous pouvez également remplacer la propriété indécidable pour obtenir des variations qui sont toujours calculables mais NP difficiles / complètes. Par exemple, étant donné (unaire), il est trivial de calculer un graphe ayant -clique à l'intérieur. Mais étant donné il est difficile de vérifier si une clique existe. $L(M)=L(N)$ $n$ $G$ $n$ $n,G$ $n$

chi
la source

Cela ne devrait pas être le cas. Très bonne réponse!

Filip Haglund

Cela ne répond pas à la question. Le PO a spécifiquement demandé un problème non vérifiable au sens habituel, dans lequel, en plus de l'entrée et de la réponse alléguée, nous obtenons un certificat

qui certifie l'exactitude de la réponse. Dans votre cas, le certificat correspond aux bits utilisés pour générer de manière non déterministe la nouvelle machine de Turing équivalente. Compte tenu de

, il est facile de vérifier si

donne la machine

. Sans

, la question est de savoir s'il est facile de générer des instances matérielles de langages (NPC), ce qui n'est vrai que dans Minicrypt et Cryptomania.

z

$z$

M, N

$M, N$

z

$z$

z

$z$

M

$M$

z

$z$

Lieuwe Vinkhuijzen

@chi Toutes les paires

ne peuvent pas être certifiées, mais l'ensemble des paires

générées par votre algorithme peut être certifié. Le certificat est la transcription de votre algorithme produisant

partir de

(par exemple, "commencez par

, puis ajoutez cet état et ajoutez cette transition, puis ... et voilà,

!"). En général, si

est un algorithme non déterministe qui, avec

, calcule toujours un

admissible , alors une transcription d'un chemin de calcul de

est un certificat selon lequel un

donné est admissible.

M, N

$M, N$

M, N

$M, N$

N

$N$

M

$M$

M

$M$

N

$N$

T

$T$

x

$x$

y

$y$

T (x)

$T(x)$

y

$y$

Lieuwe Vinkhuijzen

@chi Il y a une légère nuance dans la question: pour une relation arbitraire

, il est possible que tous les

admissibles ne soient pas certifiables, et vous donnez un exemple élégant. Cependant, la question ne demande pas s'il existe des relations admissibles mais non vérifiables (la réponse est oui , selon votre exemple). Elle demande plutôt si nous pouvons avoir un algorithme produisant une sortie admissible et non vérifiable. La réponse, ici, doit être non , à cause de l'argument ci-dessus.

R

$R$

y

$y$

Lieuwe Vinkhuijzen

@chi Je ne sais pas ce que le PO avait l'intention de demander, mais j'ai trouvé votre réponse très éclairante, j'ai néanmoins appris quelque chose! Si la question peut être lue comme vous le faites, ou de manière tout aussi plausible que " existe-t-il des fonctions unidirectionnelles? " (peut-être) ou " est-ce que des problèmes difficiles de problèmes de NP sont faciles à générer? " la façon dont je l' ai lu, comme " Is ? $NP\subsetneq P$ " (non).

Lieuwe Vinkhuijzen

Ceci est simplement un développement de la première phrase de la réponse de @ chi, puisque je ne l'ai pas trouvée évidente.

L'idée est la suivante: si vous avez un algorithme qui trouve la réponse à un problème en temps polynomial, vous avez alors deux possibilités:

Vous avez précédemment prouvé (mathématiquement) que la sortie de l'algorithme est une solution au problème. Dans ce cas, les étapes de l'algorithme elles-mêmes constituent la preuve de la correction.
Vous avez un algorithme différent pour vérifier que la sortie est bien une solution. Dans ce cas, vous devez exécuter cet algorithme (sinon, vous tomberiez sous le cas n ° 1), ce qui implique que vous le faites en temps polynomial.

Par conséquent, il ne peut y avoir un tel problème.

Mehrdad
la source

Je ne comprends pas # 2. Qu'est-ce qui implique que l'algorithme différent s'exécute en temps polynomial?

Albert Hendriks

@ AlbertHendriks: Si le vérificateur n'a pas fonctionné dans le temps polynomial, le solveur d'origine ne peut pas prétendre avoir trouvé une solution correcte dans le temps polynomial, car il doit l'exécuter pour s'assurer que sa solution est correcte.

Mehrdad