Problemas entre P e NPC

Factoring e isomorfismo gráfico são problemas em NP que não são conhecidos por estar em P nem por NP-Complete. Quais são alguns outros problemas naturais (suficientemente diferentes) que compartilham essa propriedade? Exemplos artificiais provenientes diretamente da prova do teorema de Ladner não contam.

Algum desses exemplos é comprovadamente intermediário em NP, assumindo apenas alguma hipótese "razoável"?

Aqui está uma coleção de algumas das respostas de problemas entre P e NPC:

• Factoring
• Problemas de isomorfismo: gráfico isomorfismo [não NPC, a menos que ] (via @Jeff Kinne), gráfico automorfismo, isomorfismo de grupo, automorfismo, isomorfismo em anel e automorfismo (via @Joshua Grochow)$\sum_2^p=\prod_2^p$
• Computando a distância de rotação entre duas árvores binárias ou a distância de rotação entre duas triangulações do mesmo conjunto de pontos planares (via @David Eppstein)
• O problema do turnpike de reconstruir pontos on-line a distâncias (via @Suresh Venkat)
• Problemas decorrentes da conjectura de jogos exclusivos (via @Moritz)
• Problema de log discreto e outros relacionados a suposições criptográficas (via @Joe Fitzsimons)
• Determinando o vencedor em jogos de paridade (via @mashca)
• Determinar quem tem maior chance de ganhar um jogo estocástico (via @Peter Shor no MO)
• Problemas com números em caixas (via @Joshua Grochow)
• Controle de agenda para torneios equilibrados de eliminação única (via @virgi)
• Trivialidade do nó (via @JeffE)
• (Assumindo NEXP ≠ EXP) versões compactadas de problemas completos com NEXP (via @Joshua Grochow)
• Problemas no TFNP (via @Marcos Villagra)
• Interseção SAT monótona (via @ András Salamon)
• Problema com o tamanho mínimo do circuito (via @Eric Allender)
• Decidir se um determinado coletor triplo triangular é uma esfera (via @ Joe O'Rourke e @ Peter Shor)
• O problema do material de corte com um número constante de comprimentos de objeto (via @Suresh Venkat)
• Auto-dualidade monótona (via @Danu)
• Bissecção mínima planar (via @turkistany)
• Soma do subconjunto do buraco de pombo (via @ user834)
• Somas de raiz quadrada (via @JeffE)
• Decidir se um gráfico admite uma rotulação graciosa (via @Oleksandr Bondarenko)
• Versão gap do vetor mais próximo no problema de rede GapCVP (via @MCH)$(\sqrt{n})$
• O problema da divisibilidade linear [conhecido por ser completo, mas não o NPC] (via @Oleksandr Bondarenko)$\gamma$
• Localizando a dimensão VC (via @Mohammad al Turkistany)
• Encontrar o conjunto mínimo de domínio em um torneio (via @Mohammad al Turkistany)
• Planaridade em cluster

Meu problema favorito nesta classe (vou descrevê-lo como um problema funcional, mas é fácil transformar-se em um problema de decisão da maneira padrão): calcular a distância de rotação entre duas árvores binárias (equivalentemente, a distância de rotação entre duas triangulações de um polígono convexo).

Um problema que não é mencionado nesta lista ou na lista MO é o problema do turnpike. Dado um conjunto múltiplo de n (n-1) / 2 números, cada número representando a distância entre dois pontos na linha, reconstrua as posições dos pontos originais.

Observe que o que torna isso não trivial é que, para um determinado número d no multiset, você não sabe qual par de pontos está d unidades separadas.

Embora se saiba que, para qualquer instância, existe apenas um número polinomial de soluções, não se sabe como encontrar uma!

O problema da soma das raízes quadradas: Dadas duas seqüências $a_1, a_2, \dots, a_n$ e de inteiros positivos, é uma : = Σ i $b_1, b_2, \dots, b_n$ menor que, igual a ou maior queB:=∑i$A := \sum_i \sqrt{a_i}$ ?$B := \sum_i \sqrt{b_i}$

• O problema tem um algoritmo trivial de tempo de na RAM real - apenas calcule as somas e compare-as! -, mas isso não implica a participação em P.$O(n)$

• Existe um algoritmo óbvio de precisão finita, mas não se sabe se um número polinomial de bits de precisão é suficiente para correção. (Consulte http://maven.smith.edu/~orourke/TOPP/P33.html para obter detalhes.)

• O teorema de Pitágoras implica que o comprimento de qualquer curva poligonal cujos vértices e pontos finais inteiros é uma soma das raízes quadradas dos números inteiros. Assim, o problema de soma de raízes é inerente a vários problemas de geometria computacional planares, incluindo Euclidiana árvore de extensão mínima , Euclidiana caminhos mais curtos , triangulações-peso mínimo , e o problema do caixeiro viajante euclidiana . (O problema do MST euclidiano pode ser resolvido em tempo polinomial sem resolver o problema da soma das raízes, graças à estrutura matróide subjacente e ao fato de que o EMST é um subgrafo da triangulação de Delaunay.)

• Não é um algoritmo randomizado de tempo polinomial, devido à Johannes Blomer , para decidir se as duas somas são iguais. No entanto, se a resposta for não, o algoritmo de Blömer não determina qual soma é maior.

• A versão de decisão desse problema (Is ?) Nem é conhecida por estar no NP. No entanto, o algoritmo de Blömer implica que, se o problema de decisão estiver no NP, ele também estará no co-NP. Portanto, é improvável que o problema seja NP-completo.$A > B$

Aqui está uma lista de problemas que podem ou não se qualificar como "suficientemente" diferentes. Pela mesma prova que para o isomorfismo do gráfico, se algum deles estiver completo com NP, a hierarquia polinomial entra em colapso para o segundo nível. Eu não acho que exista um consenso amplo sobre qual desses "deveria" estar em P.

• Automorfismo do gráfico (determine se um gráfico tem um automorfismo não trivial). Reduz ao gráfico o isomorfismo, mas não é conhecido (não pensado?) Por ser resistente a GI.
• Isomorfismo de grupo e Automorfismo (onde os grupos são dados por suas tabelas de multiplicação). Mais uma vez, reduz-se ao isomorfismo do gráfico, mas não é considerado difícil para o GI.
• Isomorfismo de Anel e Automorfismo. Em certo sentido, esse é o avô de todos os problemas acima, uma vez que o fatoramento inteiro é equivalente a encontrar um automorfismo não trivial de um anel, e o isomorfismo de gráfico se reduz ao isomorfismo de anel. Veja Neeraj Kayal, Nitin Saxena. Complexidade dos problemas de morfismo em anel. Computational Complexity 15 (4): 342-390 (2006). (Curiosamente, determinar se um anel tem um automorfismo não trivial está em )$P$
• Este post de Bill Gasarch contém alguns outros problemas com o gosto da teoria de Ramsey que parecem intermediários.
• Pelo Teorema de Mahaney, nenhum conjunto esparso pode ser NP-completo. Mas também sabemos que existem conjuntos esparsos em - P sse N E X P não é igual a E X P . Então, assumindo N E X P ≠ E X P , a versão acolchoada de qualquer problema completo de N E X P é de complexidade intermediária. (Esse conjunto não pode estar em P, a menos que N E X P = E X $NP$$P$$NEXP$$EXP$$NEXP \neq EXP$$NEXP$$P$$NEXP = EXP$, contradizendo nossa suposição.) Há muitos problemas naturais completos.$NEXP$

O Problema Mínimo do Tamanho do Circuito (MCSP) é o meu problema "natural" favorito no NP que não é conhecido como NP-completo: Dada a tabela de verdade (de tamanho n = 2 ^ m) de uma função booleana m-variável f, e dado um número s, f tem um circuito de tamanho s? Se o MCSP for fácil, não haverá função unidirecional criptograficamente segura. Esse problema e suas variantes forneceram grande parte da motivação para o estudo de algoritmos de "força bruta" na Rússia, levando ao trabalho de Levin sobre a completude de NP. Esse problema também pode ser visto em termos de complexidade de Kolmogorov limitada por recursos: perguntando se uma sequência pode ser recuperada rapidamente a partir de uma descrição curta. Esta versão do problema foi estudada por Ko; o nome MCSP foi usado primeiro por Cai e Kabanets, até onde eu sei. Mais referências podem ser encontradas em alguns artigos meus: http://ftp.cs.rutgers.edu/pub/allender/KT.pdf http://ftp.cs.rutgers.edu/pub/allender/pervasive.reach.pdf

Auto-dualidade monótona

Para qualquer booleano função $f=f(x_1, x_2, ..., x_n)$ , é dupla é $f^d=\bar{f}(\bar{x_1}, \bar{x_2}, ..., \bar{x_n})$ . Dado$f(x_1, x_2, ..., x_n)$representado por uma fórmula CNF, temos que decidir se $f=f^d$ .

Esse problema está em co-NP [ $\log^2 n$ ], ou seja, é decidível com $O(\log^2n/ \log\log n)$ etapas não determinísticas. Assim, ele possui um algoritmo de tempo quase-polinomial (tempo $O(n^{\log n/\log \log n})$ ) e, portanto, é improvável que seja co-NP-hard.

Ainda está aberto se esse problema está em P ou não. Mais detalhes podem ser encontrados no artigo de 2008 " Aspectos computacionais da dualização monótona: uma breve pesquisa " de Thomas Eiter, Kazuhisa Makino e Georg Gottlob.

Trivialidade do nó: Dada uma cadeia poligonal fechada em 3 espaços, ela não está marcada (isto é, isotópica do ambiente em um círculo plano)?

Sabe-se que isso ocorre em NP por resultados profundos na teoria normal da superfície, mas nenhum algoritmo de politempo ou prova de dureza NP é conhecido.

Não se sabe se é possível decidir em tempo polinomial se o jogador 1 tem uma estratégia vencedora em um jogo de paridade (a partir de uma determinada posição inicial). O problema, no entanto, está contido em NP e co-NP e até em UP e co-UP.

Você obtém uma lista muito longa de problemas se estiver disposto a aceitar problemas de aproximação, como aproximar o Max-Cut de um fator 0,878. Não sabemos se é NP-difícil ou em P (só sabemos NP-dureza assumindo a Conjectura de Jogos Uniuqe).

Em uma fórmula CNF monótona, cada cláusula contém apenas literais positivos ou literais negativos. Em um cruzamento fórmula monótona de CNF que se toda cláusula positiva tem alguma variável em comum com toda cláusula negativa.

O problema de decisão

INTERSECTING MONOTONE SAT
Input: fórmula CNF monótona de interseção $f$
Pergunta: é satisfatória?$f$

tem um algoritmo log n ) que remonta a 1996, mas não se sabe que esteja em P. (é claro que pode vir a estar em P, mas isso seria um resultado importante).$n^{o(\log\ n)}$

• Thomas Eiter e Georg Gottlob, Computação Transversal do Hypergraph e Problemas Relacionados em Lógica e IA , JELIA 2002. doi: 10.1007 / 3-540-45757-7_53

Um dado múltiplo triangular é uma 3-esfera? De Joe O'Rourke.

A versão Pigeonhole da soma de subconjuntos (ou igualdade de soma de subconjuntos).

Dado:

n - 1 ∑ k = 0 a k < 2 n

Pelo princípio do pigeonhole, devem existir dois subconjuntos disjuntos, modo que:$S_1, S_2 \subseteq \{ 1, \dots, n \}$

O problema da soma dos subconjuntos de pombos pede uma solução desse tipo. Originalmente indicado em " Algoritmos de aproximação eficientes para o problema de SUBSET-SUMS EQUALITY " de Bazgan, Santha e Tuza.

Existem muitos problemas relacionados à localização de subgrupos ocultos. Você mencionou a fatoração, mas também há o problema de log discreto, além de outros relacionados a curvas elípticas, etc.

Aqui está um problema na escolha social computacional que não é conhecido por P e pode ou não ser NP completo.

Controle de agenda para torneios equilibrados de eliminação única:

Dado: gráfico do torneio em n = 2 k nós, nó $T$$n=2^k$$a$

Pergunta: existe uma permutação dos nós (um colchete ) para que a seja o vencedor do torneio de eliminação única induzida?

Dada uma permutação em 2 k nós de V e um gráfico de torneio T em V , pode-se obter uma permutação P k - 1 em 2 k - 1 nós da seguinte maneira. Para todo i > 0 , considere P k [ 2 i - 1 ] e P k [ 2 i ] e o arco e entre eles em T ; deixe P $P_k$$2^k$$V$$T$$V$$P_{k-1}$$2^{k-1}$$i>0$$P_k[2i-1]$$P_k[2i]$$e$$T$see=( P k [2i-1], P k [2i])e P k - 1 [i]= P k [2i]caso contrário. Ou seja, combinamos pares de nós de acordo com P k e usamos$P_{k-1}[i]=P_k[2i-1]$$e=(P_k[2i-1],P_k[2i])$$P_{k-1}[i]=P_k[2i]$$P_k$$T$para decidir quais nós (vencedores) passam para a próxima rodada . Portanto, dada uma permutação em 2 k, é possível definir k arredondamentos P k - 1 , ... , P 0 indutivamente, como acima, até que a última permutação contenha apenas um nó. Isso define um torneio de eliminação única (equilibrado) em 2 k nós. O nó que permanece após todas as rodadas é o vencedor do torneio.$P_{k-1}$$2^k$$k$$P_{k-1},\ldots,P_0$$2^k$

Controle de agenda para torneios equilibrados de eliminação única (formulação de gráficos):

Dado: gráfico do torneio em n = 2 k nós, nó $T$$n=2^k$$a$

Pergunta: contém uma arborescência binomial (de abrangência) em 2 k nós com raiz em a ?$T$$2^k$$a$

Uma arborescência binomial em nós com raiz em um nó x é definida recursivamente como uma arborescência binomial em 2 k - 1 nós com raiz em xe uma arborescência binomial em 2 k - 1 nós com raiz em um nó diferente y e um arco de x a y . (Se k = $2^k$$x$$a$$2^{k-1}$$x$$2^{k-1}$$y$$x$$y$$k=0$ , uma arborescência binomial é apenas a raiz.) As arborescências binomiais abrangentes em um gráfico de torneio capturam exatamente os torneios de eliminação única que podem ser jogados, dadas as informações sobre o resultado da partida no gráfico do torneio.

Algumas referências:

1. Jérôme Lang, Maria Silvia Pini, Francesca Rossi, Kristen Brent Venable, Toby Walsh: Determinação do Vencedor na Votação Sequencial por Maioria. IJCAI 2007: 1372-1377.
2. N. Hazon, PE Dunne, S. Kraus e M. Wooldridge. Como fraudar eleições e competições. COMSOC 2008.
3. Thuc Vu, Alon Altman, Yoav Shoham. Sobre a complexidade dos problemas de controle de cronograma para torneios eliminatórios. AAMAS (1) 2009: 225-232.
4. V. Vassilevska Williams. Consertando um torneio. AAAI 2010.

Dê uma olhada na classe TFNP . Tem muitos problemas de pesquisa com um status intermediário.

O problema de isomorfismo do subgrafo induzido apresenta "restrições do lado esquerdo" incompletas em NP, assumindo que P não seja igual a NP. Veja Y. Chen, M. Thurley, M. Weyer: Entendendo a complexidade dos isomorfismos do subgráfico induzido , ICALP 2008.

$NP$$NP$

Problema de bissecção mínima: encontre uma partição do conjunto de nós em duas partes de tamanho igual, de forma que o número de arestas de cruzamento seja minimizado.

Karpinski, Aproximabilidade do Problema Mínimo da Bissecção: Um Desafio Algorítmico

O problema do material de corte com um número constante de comprimentos de objeto. Veja esta discussão para mais informações.

$n$$v$$1$$v$$\beta$$v$$\beta > 1$

$\beta = \sqrt{n}$$\mathsf{NP} \cap \mathsf{coNP}$$\mathsf{NP}$$\mathsf{P}$$\beta$$\beta = n^{o(1/\log \log n)}$$\mathsf{NP}$

$G = (V,E)$$f$$v\in V$$f(v)$$e = uv\in E$$|f(u) − f(v)|$$f : V\rightarrow \{0, 1, 2,\dots, |E|\}$$\{1, 2,..., |E|\}$

1. JA Gallian. Uma pesquisa dinâmica de rotulagem de gráficos. The Electronic Journal of Combinatorics, 2009.
2. DS Johnson. A coluna NP-completeness: Um guia contínuo. J. Algorithms, 4 (1): 87–100, 1983.
3. DS Johnson. A coluna NP-completeness. ACM Transactions on Algorithms, 1 (1): 160-176, 2005.

$P$$NP$$O(n^{\log n})$$NP$$NP$

$a$$b$$a \cdot x+1$$b$

$\gamma$

Garey e Johnson em seu seminal "Computadores e Intratabilidade" dizem que (pp. 158-159):

$\gamma$$R_M$$M$

$$R_M=\{\langle x,y\rangle:there\ is\ a\ string\ z\ such\ that\ on\ input\ x\ and\ guess\ z\ M\ has\ output\ y\}$$

$L_1$$\Sigma_1$$\gamma$$L_2$$\Sigma_2$$L_1\propto_{\gamma}L_2$$M$$x\in\Sigma_1^*$$y\in\Sigma_2^*$$\langle x,y\rangle\in R_M$$\langle x,y\rangle\in R_M$$x\in L_1$$y\in L_2$$M$$x$$x$$x$$L_2$$x\in L_1$

$P$$NP$$O(n^{\log n})$

Acredita-se que o seguinte problema seja NP-Intermediário, ou seja, está em NP, mas nem em P nem em NP completo.

Problema de raiz polinomial exponencial (EPRP)

$p(x)$$\deg(p) \geq 0$$GF(q)$$q$$r$

$\deg(p)=0$

Para detalhes adicionais, consulte minha pergunta e discussão relacionada .

Não sei se o problema de isomorfismo ponderado do hipergrafo proposto na resposta de Thinh D. Nguyen não pode ser simplesmente demonstrado completo como GI. No entanto, existe um problema difícil de GI intimamente relacionado a GI, que ainda não foi reduzido a GI, a saber, o problema de isomorfismo de cordas (também chamado de problema de isomorfismo de cores ). Este é o problema realmente mostrado em tempo quase polinomial por László Babai. É de interesse independente, pois equivale a vários problemas de decisão na teoria de grupos (permutações):

• problema de interseção de coset
• problema de teste de associação com coset duplo
• problema de fatoração de grupo

Um problema que não é conhecido por ser FP ou por NP é o problema de encontrar uma árvore Steiner mínima quando se promete que os vértices de Steiner caem em dois segmentos de linha reta que se cruzam em um ângulo de 120 °. Se o ângulo entre os segmentos de linha for menor que 120 °, o problema é NP-difícil. É conjecturado que quando o ângulo é maior que 120 °, o problema está no FP.

Portanto, o seguinte problema de decisão atualmente parece ser de complexidade intermediária:

$q$
$q$

Obviamente, isso pode realmente estar em P ou ser NP completo, mas parece que teríamos uma dicotomia interessante a 120 ° em vez de um problema intermediário. (A conjectura também pode ser falsa.)

• JH Rubinstein, DA Thomas, NC Wormald, Árvores Steiner para Terminais Restritos a Curvas , SIAM J. Matemática Discreta. 10 (1) 1–17, 1997. doi: 10.1137 / S0895480192241190

Um problema difícil de GI não conhecido como NP-completo pode ser WEIGHTED_HYPERGRAPH_ISOMORPHISM. Você recebe dois hipergráficos$G_1$ e $G_2$ em $n$ vértices com hiper-arestas ponderadas, decida se existe uma permutação de vértice $\pi$ girando $G_1$ para dentro $G_2$. Consulte também: Problema do gráfico GI-rígido não conhecido por$NP$-completo