Problema de decisão fácil, problema de pesquisa difícil

Decidir se existe um equilíbrio de Nash é fácil (sempre existe); no entanto, achar que é difícil encontrar um (é completo com o PPAD).

Quais são alguns outros exemplos de problemas em que a versão de decisão é fácil, mas a versão de pesquisa é relativamente difícil (comparada à versão de decisão)?

Eu estaria particularmente interessado em problemas em que a versão da decisão não é trival (ao contrário do caso com o equilíbrio de Nash).

Dado um número inteiro, ele possui um fator não trivial? -> Não trivialmente em P.

Dado um número inteiro, encontre um fator não trivial, se houver um -> Desconhecido no FP.

Aqui está outro exemplo: dado um gráfico cúbico G e um ciclo hamiltoniano H em G, encontre um ciclo hamiltoniano diferente em G. Esse ciclo existe (pelo teorema de Smith), mas, tanto quanto eu sei, está aberto se pode ser possível. calculado em tempo polinomial.

Se você der o seguinte "espaço de manobra" para os equilíbrios de Nash, a seguir:

• Fatoração de número inteiro, em que o problema de decisão é "Existe uma representação fatorada desse número inteiro?" (trivialmente, sim), e o problema da pesquisa é produzi-lo

Vários problemas de treliça podem se encaixar aqui com o mesmo tipo de subsídio generoso para definir o problema de decisão:

• Problema de vetor mais curto (SVP) - decida se existe um vetor mais curto do que o encontrado
• Problema do vetor mais próximo (CVP) - decida se existe um vetor mais próximo do que encontrar

Obviamente, são todos os casos em que a versão da decisão que mencionei não é muito interessante (porque é trivialmente o caso). Um problema que não é tão trivial :

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

O problema de decisão da coloração do gráfico planar 4 está em P. Mas obter a primeira solução lexicograficamente é NP-difícil ( Khuller / Vazirani ).

Observe que a propriedade na qual você realmente está interessado é a auto-redutibilidade (ou melhor, a não-auto-redutibilidade). No problema de coloração do gráfico planar, a questão essencial é que o método de auto-redução do caso geral da colorabilidade- destruirá a planaridade em um gráfico.$k$

Vamos , o gráfico aleatória em 1 , ... , n , em que cada aresta está presente de forma independente com probabilidade 1 / 2 . Escolha n 1 / 3 vértices de L uniformemente aleatoriamente e adicionar todas as arestas entre as mesmas; chamar o gráfico resultante H . Em seguida, H tem um clique de tamanho n 1 /$G=G(n,1/2)$$1,\ldots,n$$1/2$$n^{1/3}$$G$$H$$H$$n^{1/3}$ .

Problema de pesquisa: encontre um clique de tamanho pelo menos .$10\log n$

Mais um exemplo; O subconjunto-somas igualdade: Dado números naturais com Σ n 1 um i < 2 n - 1 . O princípio pombo-furo garante a existência de dois subconjuntos I , J , em 1 , 2 , . . . , N tal que Σ i ∈ I um i $a_1,a_2,a_3,...,,a_n$$\sum_1^n{a_i} \lt 2^n -1$$I, J$${1,2,..., n}$ (já que existem mais subconjuntos que somas possíveis). A existência do algoritmo de tempo polinomial para encontrar os conjuntosIeJé um famoso problema em aberto.$\sum_{i\in I} a_i=\sum_{j \in J} a_j$$I$$J$

Igualdade de subconjuntos-somas (versão pigeonhole)

Outro exemplo da teoria dos números, semelhante aos acima. É sabido pelo postulado de Bertrand que, para todo número inteiro positivo , existe um primo entre n e 2 n . Mas atualmente não temos um algoritmo de tempo polinomial para encontrar um valor tão primo, dado n . (O algoritmo desejado deve ser executado no tempo polylog ( n ).) Pode-se facilmente criar algoritmos aleatórios no tempo polinomial por causa do teorema do número primo ), mas nenhum algoritmo determinístico do tempo polinomial incondicionalmente é conhecido. Trabalhos relacionados foram feitos recentemente no projeto Polymath4 ; A publicação do blog de Tao no projeto é um bom resumo.$n$$n$$2n$$n$$n$ e pode-se derandomizar ao assumi-lo assumindo algumas conjecturas teóricas numéricas padrão (como a conjectura de Cramer

Correndo o risco de ser um pouco fora de tópico, deixe-me dar um exemplo simples e natural de uma resposta C da teoria : Ciclos eulerianos e algoritmos distribuídos.

O problema de decisão não é completamente trivial, no sentido de que existem gráficos eulerianos e não-eulerianos.

Existe, no entanto, um algoritmo distribuído rápido e simples que resolve o problema de decisão (no sentido de que para instâncias yes todos os nós emitem "1" e para instâncias não pelo menos um nó gera "0"): cada nó apenas verifica a paridade de seu próprio grau e gera 0 ou 1 de acordo.

Mas se você deseja encontrar um ciclo euleriano (no sentido de que cada nó produz a estrutura do ciclo em sua própria vizinhança), precisamos de informações essencialmente globais no gráfico. Não deve ser difícil apresentar alguns exemplos que mostrem que o problema requer rodadas de comunicação; por outro lado, O ( n ) rodadas é suficiente para resolver qualquer problema (assumindo IDs únicos).$\Omega(n)$$O(n)$

Em resumo: -tempo decisão problema, Θ ( n ) problema de pesquisa -time, e este é o pior diferença possível.$O(1)$$\Theta(n)$

Editar: Isso implica implicitamente que o gráfico esteja conectado (ou, equivalentemente, que desejamos encontrar um ciclo euleriano em cada componente conectado).

Encontrar partições Tverberg é de complexidade desconhecida:

Teorema: Vamos $x_1,x_2,\dots, x_m$ be points in $R^d$, $m \ge (r-1)(d+1)+1$. Then there is a partition $S_1,S_2,\dots, S_r$ of ${1,2,\dots,m}$ such that $\cap _{j=1}^r \text{conv} (x_i: i \in S_j) \ne \emptyset$.

Like with Nash equilibria, the partition is guaranteed by the theorem, but it's not known if a polytime algorithm exists to find one.

Gil Kalai wrote a wonderful series of posts on this topic: One, Two and Three.

In all the examples above the decision problem is in P and the search problem is not known to be in P but not known to be NP-hard either. I want to point out that it is possible to have an NP-hard search problem whose decision version is easy.

Consider the generalized satisfiability problem for given relations $R_1,\ldots,R_k$ over Boolean domain $\{0,1\}$. An instance is an expression of the form

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.