Problema de decisión fácil, problema de búsqueda difícil

Decidir si existe un equilibrio de Nash es fácil (siempre existe); sin embargo, se cree que encontrar uno es difícil (es PPAD-Complete).

¿Cuáles son algunos otros ejemplos de problemas en los que la versión de decisión es fácil pero la versión de búsqueda es relativamente difícil (en comparación con la versión de decisión)?

Me interesarían particularmente los problemas en los que la versión de decisión no es trival (a diferencia del caso con el equilibrio de Nash).

Dado un número entero, ¿tiene un factor no trivial? -> No trivialmente en P.

Dado un número entero, encuentre un factor no trivial, si hay uno -> No se sabe que está en FP.

Aquí hay otro ejemplo: dado un gráfico cúbico G y un ciclo hamiltoniano H en G, encuentre un ciclo hamiltoniano diferente en G. Tal ciclo existe (según el teorema de Smith) pero, hasta donde yo sé, está abierto si puede ser calculado en tiempo polinomial.

Si le da al siguiente el mismo "margen de maniobra" que lo hace para equilibrios de Nash, entonces:

• Factorización de enteros, donde el problema de decisión es "¿Hay una representación factorizada de este entero?" (trivialmente, sí), y el problema de búsqueda es generarlo

Una serie de problemas de red podrían encajar aquí con el mismo tipo de asignación generosa para definir el problema de decisión:

• Problema de vector más corto (SVP): decida si hay un vector más corto en lugar de encontrarlo
• Problema de vector más cercano (CVP): decida si hay un vector más cercano en lugar de encontrarlo

Por supuesto, estos son todos los casos en los que la versión de decisión que he mencionado no es muy interesante (porque es trivial). Un problema que no es tan trivial :

• Gráfico plano -colorabilidad para k ≥ $k$$k \ge 4$

El problema de decisión de la colorabilidad del gráfico plano 4 está en P. Pero obtener la primera solución lexicográfica es NP-hard ( Khuller / Vazirani ).

Tenga en cuenta que la propiedad que realmente le interesa es la auto-reducibilidad (o más bien, la no auto-reducibilidad). En el problema de coloración del gráfico plano, la cuestión esencial es que el método de auto-reducción del caso general de coloración destruirá la planaridad en un gráfico.$k$

Vamos , el gráfico de azar en 1 , ... , n , en el que cada borde es independientemente presente con una probabilidad de 1 / 2 . Elige n 1 / 3 vértices de G uniformemente al azar y añadir todos los bordes entre ellos; llamar a la gráfica resultante H . Entonces H tiene un clique de tamaño n 1 / 3 .$G=G(n,1/2)$$1,\ldots,n$$1/2$$n^{1/3}$$G$$H$$H$$n^{1/3}$

Problema de búsqueda: encuentre una camarilla de tamaño de al menos .$10\log n$

Un ejemplo mas; El subconjunto-sumas igualdad: Dado números naturales con Σ n 1 a i < 2 n - 1 . El principio casillero garantiza la existencia de dos subconjuntos I , J en 1 , 2 , . . . , n tal 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}$ (ya que hay más subconjuntos que sumas posibles). La existencia del algoritmo de tiempo polinómico para encontrar los conjuntos I y J es un famoso problema abierto.$\sum_{i\in I} a_i=\sum_{j \in J} a_j$$I$$J$

Igualdad de sumas de subconjuntos (versión de casillero)

Otro ejemplo de teoría de números, similar a los anteriores. Es conocido por el postulado de Bertrand que para cada entero positivo , hay un primo entre n y 2 n . Pero actualmente no tenemos un algoritmo de tiempo polinomial para encontrar tal primo, dado n . (El algoritmo deseado debe ejecutarse en tiempo polylog ( n )). Uno puede encontrar fácilmente algoritmos aleatorios de tiempo polinómico debido al teorema del número primo , y puede desrandomizarlos asumiendo algunas conjeturas teóricas de números estándar (como la conjetura de Cramer$n$$n$$2n$$n$$n$), pero no se conoce un algoritmo determinista de tiempo polinómico incondicional. El trabajo relacionado se realizó recientemente en el proyecto Polymath4 ; La publicación de blog de Tao sobre el proyecto es un buen resumen del mismo.

A riesgo de estar un poco fuera de tema, permítanme dar un ejemplo simple y natural de una respuesta de teoría C : ciclos eulerianos y algoritmos distribuidos.

El problema de decisión no es completamente trivial, en el sentido de que hay gráficos tanto eulerianos como no eulerianos.

Sin embargo, existe un algoritmo distribuido rápido y simple que resuelve el problema de decisión (en el sentido de que para instancias sí todos los nodos generan "1" y para no instancias al menos un nodo genera "0"): cada nodo simplemente verifica la paridad de su propio grado y produce 0 o 1 en consecuencia.

Pero si desea encontrar un ciclo euleriano (en el sentido de que cada nodo genera la estructura del ciclo en su propio vecindario), entonces necesitamos información esencialmente global en el gráfico. No debería ser difícil encontrar un par de ejemplos que muestren que el problema requiere rondas de comunicación ; Por otro lado, O ( n ) rondas es suficiente para resolver cualquier problema (suponiendo identificaciones únicas).$\Omega(n)$$O(n)$

En resumen: problema de decisión en el tiempo, Θ ( n ) problema de búsqueda en el tiempo, y esta es la peor brecha posible.$O(1)$$\Theta(n)$

Editar: Esto supone implícitamente que el gráfico está conectado (o, de manera equivalente, que queremos encontrar un ciclo euleriano en cada componente conectado).

Encontrar particiones de Tverberg es de complejidad desconocida:

$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$

Al igual que con los equilibrios de Nash, la partición está garantizada por el teorema, pero no se sabe si existe un algoritmo polytime para encontrar uno.

Gil Kalai escribió una maravillosa serie de publicaciones sobre este tema: Uno , Dos y Tres .

En todos los ejemplos anteriores, el problema de decisión está en P y no se sabe que el problema de búsqueda esté en P, pero tampoco se sabe que es NP-hard. Quiero señalar que es posible tener un problema de búsqueda NP-hard cuya versión de decisión es fácil.

Considere el problema de satisfacción generalizado para determinadas relaciones $R_1,\ldots,R_k$ sobre dominio booleano $\{0,1\}$. Una instancia es una expresión de la forma

It was shown by Reith and Vollmer here that there exists a choice of relations $R_1,\ldots,R_k$ that make this problem NP-hard (actually OptP-complete) but keep the satisfiability problem easy (quite trivial actually). An example given in the paper is $R = \{(1,0,0),(0,1,0),(1,1,1)\}$ (here $k = 1$). Once the satisfiability problem is solvable in polynomial-time, the question whether there exists a lexicographically minimal satisfying assignment is trivial.

See Corollary 13 and the example following it in the paper above (at least in this on-line version).

• Decision version is (highly) non-trival in P: $k$-colourability ($k$ fixed) on graphs without induced path with five vertices; due to this paper.
• Search version is NP-hard: Finding the chromatic number of graphs without induced path with five vertices; due to this paper.

Take a "pairing-friendly" elliptic curve. That is, a curve that has a one bilinear map $e$ associated with it - with $e (a + b, c + d) = e (a c) e (a d) e (b c) e (b d)$ such that $e$ is difficult to invert).

Such pairings are used widely in cryptography, partially since given $e$, it is trivial to solve Decisional Diffie-Hellman (given $(g, h, g^a, h^b)$, decide if $a = b$: just verify whether $e (g, h^b) = e (h, g^a)$). However, it is still conjectured that the search/computational Diffie-Hellman problem is difficult.

Such groups are also generalized to "gap groups".

I guess Planar Perfect Matching got missed out from this list.

• The decision version is in NC (even the counting version is in $\mathsf{NC}$) by a parallel version (see Mahajan-Subramanya-Vinay) of Kastelyn's algorithm
• The search version remains unparallelised to date i.e there is no known deterministic $\mathsf{NC}$ algorithm for this problem (though if we drop either of the parallel or deterministic restrictions there are well known algorithms - Edmonds and Mulmuley-Vazirani-Vazirani/Karp-Upfal-Wigderson, respectively.

Let's notch up the complexity a bit.

Many decision problems about vector addition systems (VAS) are EXPSPACE-complete, but may require much larger witnesses. For instance, deciding whether the language of a VAS is regular is EXPSPACE-complete (e.g. Blockelet & Schmitz, 2011), but the smallest equivalent finite-state automaton might be of Ackermannian size (Valk & Vidal-Naquet, 1981). The explanation behind this huge gap is that there exist much smaller witnesses of non-regularity.