Problème de décision facile, problème de recherche difficile

Il est facile de décider si un équilibre de Nash existe. cependant, en trouver un est difficile (PPAD-Complete).

Quels sont quelques autres exemples de problèmes où la version de décision est facile mais la version de recherche est relativement difficile (comparée à la version de décision)?

Je serais particulièrement intéressé par les problèmes où la version de décision est non-trival (contrairement à l’équilibre de Nash).

Étant donné un entier, a-t-il un facteur non trivial? -> Non trivialement en P.

Étant donné un entier, trouvez un facteur non trivial, s'il en existe un -> Inconnu dans la PF.

Voici un autre exemple: Soit un graphe cubique G et un cycle hamiltonien H en G, trouve un cycle hamiltonien différent en G. Un tel cycle existe (selon le théorème de Smith) mais, autant que je sache, il est possible calculé en temps polynomial.

Si vous donnez aux mêmes "marges de manœuvre" que vous faites pour les équilibres de Nash, alors:

• Factorisation d'entiers, où le problème de décision est "Existe-t-il une représentation factorisée de cet entier?" (trivialement, oui), et le problème de recherche est de le sortir

Un certain nombre de problèmes de réseau pourraient éventuellement convenir ici avec le même type d'allocation généreuse pour définir le problème de décision:

• Problème de vecteur le plus court (SVP) - décide s’il existe un vecteur le plus court vs le trouver
• Problème de vecteur le plus proche (CVP) - décide s'il existe un vecteur le plus proche vs le trouver

Bien sûr, ce sont tous des cas où la version de décision que j'ai mentionnée n'est pas très intéressante (car c'est trivialement le cas). Un problème qui n’est pas aussi anodin :

• Planar graphe -colorability pour k ≥ $k$$k \ge 4$

Le problème de décision de la colorabilité 4 du graphe planaire est en P. Mais l'obtention de la première solution lexicographiquement est NP-difficile ( Khuller / Vazirani ).

Notez que la propriété qui vous intéresse vraiment est auto-réductibilité (ou plutôt non-auto-réductibilité). Dans le problème de coloration de graphes planaires, le problème essentiel est que la méthode de réduction automatique du cas général de colorabilité détruira la planarité dans un graphe.$k$

Soit , le graphe aléatoire sur 1 , ... , n , dans lequel chaque bord est indépendamment présent avec une probabilité de 1 / 2 . Choisissez n 1 / 3 sommets de G uniformément au hasard et ajouter tous les bords entre eux; appeler le graphe résultant H . Ensuite , H a une clique de taille n une / 3 .$G=G(n,1/2)$$1,\ldots,n$$1/2$$n^{1/3}$$G$$H$$H$$n^{1/3}$

Problème de recherche: trouvez une clique d’au moins .$10\log n$

Un autre exemple; Les sommes Sous - ensemble-égalité: Compte tenu d' nombres naturels avec Σ n 1 a i < 2 n - 1 . Le principe pigeon trous garantit l'existence de deux sous - ensembles I , J à 1 , 2 , . . . , N telle que Σ i ∈ I a i$a_1,a_2,a_3,...,,a_n$$\sum_1^n{a_i} \lt 2^n -1$$I, J$${1,2,..., n}$ (car il y a plus de sous-ensembles que de sommes possibles). L'existence d'un algorithme temporel polynomial pour trouver les ensembles I et J est un problème ouvert bien connu.$\sum_{i\in I} a_i=\sum_{j \in J} a_j$$I$$J$

Egalité des sous-ensembles (version en casier)

Un autre exemple de théorie des nombres, similaire à ceux ci-dessus. Selon le postulat de Bertrand, pour tout entier positif , il existe un nombre premier compris entre n et 2 n . Mais nous n'avons actuellement aucun algorithme polynomial pour trouver un tel nombre premier, étant donné n . (L'algorithme désiré doit être exécuté en temps polylog ( n ).) On peut facilement trouver des algorithmes aléatoires polynomiaux en raison du théorème des nombres premiers , et on peut les dérandonner en supposant des conjectures théoriques sur les nombres standard (telles que la conjecture de Cramer).$n$$n$$2n$$n$$n$), mais aucun algorithme déterministe en temps polynomial inconditionnel n'est connu. Des travaux connexes ont récemment été réalisés dans le projet Polymath4 ; Le billet de blog de Tao sur le projet en est un bon résumé.

Au risque d’être un peu hors sujet, laissez-moi vous donner un exemple simple et naturel de réponse théorique à la théorie C : Les cycles eulériens et les algorithmes distribués.

Le problème de la décision n’est pas totalement trivial, dans la mesure où il existe à la fois des graphes eulériens et non eulériens.

Il existe cependant un algorithme distribué simple et rapide qui résout le problème de la décision (en ce sens que tous les nœuds produisent "1" pour tous les nœuds et au moins un nœud indique "0"): chaque nœud vérifie simplement la parité de son propre degré et génère 0 ou 1 en conséquence.

Mais si vous souhaitez trouver un cycle eulérien (en ce sens que chaque nœud génère la structure du cycle dans son propre voisinage), vous avez besoin d'informations essentiellement globales sur le graphique. Il ne devrait pas être difficile de trouver deux exemples qui montrent que le problème nécessite rounds de communication; d'autre part, O ( n ) tours est suffisant pour résoudre tous les problèmes ( en supposant un ID unique).$\Omega(n)$$O(n)$

En résumé: problème décision -temps, Θ ( n ) problème de recherche -temps, ce qui est le pire écart possible.$O(1)$$\Theta(n)$

Éditer: Cela suppose implicitement que le graphique est connecté (ou, de manière équivalente, que nous souhaitons trouver un cycle eulérien dans chaque composant connecté).

Trouver des partitions Tverberg est d'une complexité inconnue:

$x_1,x_2,\dots, x_m$$R^d$$m \ge (r-1)(d+1)+1$$S_1,S_2,\dots, S_r$${1,2,\dots,m}$$\cap _{j=1}^r \text{conv} (x_i: i \in S_j) \ne \emptyset$

Comme avec les équilibres de Nash, la partition est garantie par le théorème, mais on ne sait pas s'il existe un algorithme polytime pour en trouver un.

Gil Kalai a écrit une série d'articles sur ce sujet: Un , Deux et Trois .

Dans tous les exemples ci-dessus, le problème de la décision est dans P et le problème de la recherche n'est pas connu pour être dans P mais pas non plus pour être NP-difficile. Je tiens à souligner qu'il est possible d'avoir un problème de recherche NP-hard dont la version de décision est facile.

$R_1,\ldots,R_k$$\{0,1\}$

$R_1,\ldots,R_k$$R = \{(1,0,0),(0,1,0),(1,1,1)\}$$k = 1$). Une fois que le problème de satisfiabilité est résolu en temps polynomial, la question de savoir s'il existe une assignation satisfaisante lexicographiquement minimale est triviale.

Voir le corollaire 13 et l'exemple qui le suit dans le document ci-dessus (au moins dans cette version en ligne).

• $k$$k$
• La version de recherche est NP- hard: recherche du nombre chromatique de graphes sans chemin induit à cinq sommets; en raison de ce papier .

$e$$e (a + b, c + d) = e (a c) e (a d) e (b c) e (b d)$$e$

$e$$(g, h, g^a, h^b)$$a = b$$e (g, h^b) = e (h, g^a)$

De tels groupes sont également généralisés aux "groupes de gap".

Je suppose que Planar Perfect Matching a été oublié de cette liste.

• $\mathsf{NC}$
• $\mathsf{NC}$

Notons un peu la complexité.

De nombreux problèmes de décision concernant les systèmes d’addition de vecteurs (SVA) sont complets, mais peuvent nécessiter des témoins beaucoup plus grands. Par exemple, décider si le langage d'un SAV est régulier est EXPSPACE-complete (par exemple, Blockelet & Schmitz, 2011 ), mais le plus petit automate équivalent à états finis pourrait être de taille Ackermannian ( Valk & Vidal-Naquet, 1981 ). L'explication derrière cet énorme fossé est qu'il existe des témoins beaucoup moins nombreux de non- régularité.