Y a-t-il des problèmes faciles à calculer mais difficiles à vérifier?

En supposant que P NP, les problèmes NP-complets sont "difficiles à résoudre, mais ont des réponses faciles à vérifier". Est-il sensé de considérer le contraire, c'est-à-dire des problèmes pour lesquels il est facile de calculer une réponse correcte, mais difficile de vérifier une prétendue solution arbitraire? $\neq$

Je pense qu'un tel problème impliquerait soit:

De manière exponentielle, de nombreuses réponses «correctes» pour une entrée donnée, car sinon la vérification pourrait être effectuée en calculant simplement toutes les réponses correctes.
Certaines réponses «correctes» sont faciles à calculer, mais d'autres sont difficiles à trouver.

complexity-theory rphv
la source

J'en doute. Si une réponse est facile à calculer, le choix du certificat est facile: fournissez la réponse supposée avec le problème, et "vérifiez" la réponse en résolvant le problème, et en voyant si la réponse supposée est réellement la réponse.

Patrick87

@ Patrick87 - Je pense que je l'ai abordé dans la question. Qu'en est-il d'une fonction à valeurs multiples qui associe un ensemble de valeurs à une entrée ? Supposons que , et qu'il est facile de choisir un élément dans , mais étant donné il est difficile de déterminer si .

f

$f$

I_{f} (x) = {y_{1}, y_{2}, \dots}

$I_f(x) = \{y_1, y_2, \dots \}$

x

$x$

| I_{f} (x) | = 2^{| x |}

$|I_f(x)| = 2^{|x|}$

I_{f} (x)

$I_f(x)$

z

$z$

z \in I_{f} (x)

$z \in I_f(x)$

rphv

@ Patrick87 Le solveur peut être déterministe et ne produire qu'une seule de toutes les réponses existantes. Vous avez ensuite besoin d'un moyen efficace pour vérifier si deux solutions sont équivalentes. L'équivalence sur un ensemble peut-elle être plus difficile que de résoudre un problème sur celui-ci?

Raphael

En fait, j'ai raté cette partie, désolé. Pourtant, je suis enclin à douter de la prémisse. J'y penserai un peu plus et reviendrai si j'ai des pensées plus pertinentes.

Patrick87

Un certificat signifie généralement qu'il existe un moyen facile de reconstruire une preuve, donc par définition, si vous fournissez un certificat, la vérification est facile. Une solution sans certificat peut être difficile.

Gilles 'SO- arrête d'être méchant'

Réponses:

Si vous êtes bien avec des problèmes artificiels, vous pouvez en faire beaucoup. Voici quelques-uns:

Étant donné un entier positif n en unaire, répondez à une formule 3CNF satisfaisante dans n variables booléennes.
Donner une formule 3CNF satisfaisable est facile, mais décider si une formule 3CNF donnée est satisfaisable ou non est 3SAT, un problème NP-complet bien connu.
Il n'y a aucune entrée. Répondez simplement à une machine de Turing qui s'arrête (lorsqu'elle est exécutée avec une bande d'entrée vide).
Donner une telle machine de Turing est facile, mais si une machine de Turing donnée s'arrête ou non, c'est indécidable.

Ajouté : Soit dit en passant, je ne pense pas que ce que vous avez écrit dans le dernier paragraphe soit valable:

Je pense qu'un tel problème impliquerait exponentiellement de nombreuses réponses «correctes» pour une entrée donnée, car sinon la vérification pourrait être effectuée en calculant simplement toutes les bonnes réponses.

Si le problème a une solution, alors vérifier une réponse n'est pas plus difficile que de calculer la bonne solution. Cependant, si le problème a une solution facile et une solution difficile, vous ne pouvez pas calculer toutes les solutions efficacement. Voici un de ces problèmes (qui est très artificiel):

Étant donné une machine Turing M , répondez à l'une des affirmations suivantes: « M s'arrête sur une bande d'entrée vide», « M ne s'arrête pas sur une bande d'entrée vide» et « M est une machine Turing». Il
est facile de proposer une solution : vous pouvez toujours choisir « M est une machine de Turing». Cependant, qu'une réponse donnée soit correcte ou non est indécidable. Notez que dans ce problème, il n'y a que deux solutions pour chaque instance.

Tsuyoshi Ito
la source

Existe-t-il un moyen raisonnable de définir formellement ce que signifie que de tels problèmes sont «artificiels»? (Par «raisonnable», je veux dire quelque chose sur lequel nous pouvons largement nous mettre d'accord, comme dire qu'une définition de «calculable» capture notre intuition de ce que cela devrait signifier.)

Gilles 'SO- arrête d'être mauvais'

@ Gilles: Non, je ne pense pas. J'ai appelé ces problèmes «artificiels» parce qu'il est très peu probable que quelqu'un rencontre ces problèmes d'abord et découvre ensuite qu'il est facile de faire une seule réponse et difficile de décider de l'exactitude d'un candidat de réponse donné. Mais ce «caractère artificiel» n'est en aucun cas une notion rigoureuse.

Tsuyoshi Ito

@Tsuyoshi Ito - Merci pour votre réponse claire. J'ai édité le dernier paragraphe pour refléter votre perspicacité.

rphv

Bien que la réponse de Tsuyoshi Ito couvre la réponse "principale", il y avait deux notes plus subtiles que je voulais ajouter.

Même lorsque la solution est difficile à vérifier, la vérification de la solution est toujours facile à vérifier avec une chaîne de preuve courte. C'est-à-dire qu'en étendant un peu la solution avec des informations supplémentaires, elle devient facilement vérifiable; la vérification est toujours en NP. Une façon de voir cela est que l'agent qui calcule une solution peut enregistrer tous les bits aléatoires qu'il utilise, puis le vérificateur peut utiliser cette même chaîne aléatoire pour exécuter le même calcul. (Le prouveur doit utiliser des bits aléatoires, sinon ils produisent toujours la même réponse, et le vérificateur peut toujours vérifier facilement en calculant une réponse par la même méthode.)
Pour les ordinateurs quantiques, c'est une question très ouverte. Pour les ordinateurs classiques, le vérificateur peut toujours faire quelque chose comme simuler le prouveur et vérifier qu'il obtient la même réponse. Il est tout à fait possible que pour un problème délicat, il existe un algorithme quantique qui produit une distribution uniforme entre toutes les solutions (exponentiellement nombreuses), qui sont difficiles à vérifier. Vous ne pouvez pas relancer le prouveur, car vous obtiendrez très probablement une réponse différente à chaque fois.

À titre d'exemple d'un problème similaire, le problème Deutsch-Jozsa en souffre un peu. Si un oracle n'est pas une fonction équilibrée, un ordinateur quantique peut rapidement déterminer que c'est le cas, mais il n'y a pas de preuve courte qui permettrait à un ordinateur classique de le vérifier. (Ce n'est qu'un problème "similaire" car il peut toujours être vérifié par un autre ordinateur quantique, et la vérification est également en BPP classique même si ce n'est pas en P.)

Alex Meiburg
la source