Problemas naturais de NP completos com testemunhas “grandes”

28

A pergunta sobre a história " O que é NP restrito a testemunhas de tamanho linear? " Pergunta sobre a classe NP restrita a testemunhas de tamanho linear O ( n )O(n) , mas

Existem problemas naturais de NP completos nos quais (sim) instâncias de tamanho nn exigem testemunhas de tamanho maior que nn ?

Claramente, podemos criar problemas artificiais como:

  • L = { 1 n w w  codifica uma fórmula satisfatória e  | w | = n }L = { 1nww encodes a satisfiable formula and |w|=n}
  • L = { φ φ  é a fórmula SAT com mais de  | & Phi; | 2  tarefas satisfatórias }L={φφ is SAT formula with more than |φ|2 satisfying assignments}

Após uma rápida olhada em G&J, todo problema natural de NPC parece ter testemunhas (estritamente) menores que nn .

Existe uma "razão / explicação" para isso?

Marzio De Biasi
fonte
1
Muitos problemas têm tamanho de testemunha Θ ( n log n )Θ ( n logn ) , como isomorfismo de grafos e caminho hamiltoniano. Deseja excluir fatores de polilog ou isso conta como resposta?
27413 Joshua Grochow #: 26414
12
Na verdade, o tamanho testemunha para o Graph Isomorfismo e Caminho Hamiltoniano poderia ser visto como sublinear na entrada (dado que a entrada é o n x n adjacência matriz do gráfico). n×n
Ryan Williams
1
Oh, certo ... d'oh.
Joshua Grochow
1
@MarzioDeBiasi Acho que sua observação de pequenas testemunhas deve ser usada para definir um problema natural de NP completo.
Mohammad Al-Turkistany
1
@MarzioDeBiasi - Concordo que uma lista de tarefas satisfatórias é suficiente, mas você pode provar que não há uma testemunha mais curta para o problema? (talvez uma maneira sucinta de representar as tarefas necessárias).
RB

Respostas:

10

Que tal o número de cores das bordas em um gráfico denso (também conhecido como índice cromático )? Você recebe a matriz de adjacência de um gráfico de n vértices ( entrada de n 2 bits), mas a testemunha natural que descreve a coloração tem tamanho n 2 log n . Certamente, pode haver provas mais curtas para os gráficos da classe 1 no teorema de Vizing .nn2n2logn

Veja também esta questão possivelmente relacionada

Andreas Björklund
fonte
2
Parece um bom exemplo! Apenas uma observação: o problema é NP-completo, mesmo para gráficos cúbicos; nesse caso, temos uma testemunha do tamanho 2 | E | bits é suficiente (dois bits para cada aresta) que é menor que n 2 se usarmos a representação da matriz de adjacência e suspeito que seja menor que o tamanho da instância, independentemente da codificação razoável que usarmos para o gráfico cúbico. 2|E|n2
Marzio De Biasi
8

Eu me deparei com alguns problemas bastante completos de NP que aparentemente exigem longas testemunhas. Os problemas, parametrizados pelos números inteiros C e D, são os seguintes:CD

Entrada: A uma fita TM- M Pergunta: Existe algum n N , de tal modo que H torna mais de C n + D etapas em alguma entrada de comprimento n ?M
nNMCn+Dn

Sometimes the complement of the problem is easier to state: Does a given one-tape TM MM run in time Cn+DCn+D, ie. does it make at most Cn+DCn+D steps on all inputs of size nn, for all nn?

O resultado completo é apresentado aqui . Basicamente, é mostrado que, se queremos verificar se uma TM de uma fita é executada no tempo C n + D , precisamos verificar isso apenas nas entradas de comprimento delimitadas por q O ( C ) , onde q é o número de estados da entrada TM. Portanto, a testemunha seria a entrada do comprimento q O ( C ) pelo qual o tempo limite é violado. Também é mostrado na referência que esses problemas são NP-completos para todos C 2 e D 1 .Cn+DqO(C)qqO(C)C2D1

Agora, se a testemunha é uma entrada que viola o tempo de execução, ela deve ter um comprimento q Ω ( C ) em geral. E a entrada é do comprimento O ( q 2 ) .qΩ(C)O(q2)

David G
fonte
3
Obrigado! Mas, para ser sincero, acho mais "natural" (sei que não é um conceito formal) o problema: "Dada uma fórmula φ , decida se ela tem pelo menos | φ | 2 tarefas satisfatórias" :-)φ|φ|2
Marzio De Biasi
Compreendo :). Por outro lado, o problema sobre φ tem a duração da testemunha na pergunta, enquanto o problema sobre as MTs obtém a duração da testemunha na prova. Além disso, a duração da testemunha não é intencionalmente incorporada ao problema. φ
David G
7

Aqui está um exemplo, que parece um problema natural.

Instância: números inteiros positivos, d 1 , , d n e k , todos delimitados de cima por n .d1,,dnkn

Pergunta: Existe um gráfico colorido k com sequência de graus d 1 , , d n ?kd1,,dn

Aqui, a entrada pode ser descrita com O ( n log n ) bits, mas a testemunha pode exigir Ω ( n 2 ) bits.O(nlogn)Ω(n2)

Observação: não tenho uma referência de que esse problema específico seja realmente NP-completo. Mas o requisito de k- colorability poderia ser substituído por qualquer outra condição NP-complete; o problema provavelmente se tornará NP-completo para alguma condição, se não for para esta.k

Andras Farago
fonte
Para mim, esse problema tem o tipo errado de estrutura para ser NP-completo, a menos que P = NP. As classes de gráficos definidas por cada sequência de graus podem ser muito grandes e muitos deles podem ter elementos n- coloridos por um motivo trivial. n
András Salamon
@ AndrásSalamon De fato, não sei qual é a complexidade desse problema, ou se ele pode ser completado por NP, escolhendo uma condição apropriada em vez de k- colorability. Por outro lado, ficaria surpreso se, para todas as propriedades verificáveis ​​em polytime Q, o seguinte problema estivesse em P : existe um gráfico com uma determinada sequência de graus, de forma que também tenha a propriedade Q ? kQQ
Andras Farago
Concordo que parece improvável que a sequência de graus + a propriedade esteja sempre em P, mas talvez algumas delas sejam candidatas ao status intermediário de NP?
András Salamon
@ AndrásSalamon Sim, posso muito bem imaginar que alguns deles tenham status de NPI.
Andras Farago
6

Talvez esta seja uma "razão / explicação" boba, mas para muitos problemas do NP-Complete, uma solução é um subconjunto da entrada (mochila, capa de vértice, clique, conjunto dominante, conjunto independente, conjunto independente, corte máximo, soma do subconjunto, ... ) ou uma permutação ou atribuição a um subconjunto da entrada (caminho Hamiltoniano, vendedor ambulante, SAT, isomorfismo de gráfico, coloração de gráfico, ...).

Poderíamos tentar ler mais sobre isso ou sugerir uma razão mais extravagante, mas não tenho certeza se há algo mais profundo acontecendo ou não.

usul
fonte
Eu acho que essa é uma boa "primeira idéia" de fato. Às vezes, os problemas não podem ser classificados sem ambiguidade. Por exemplo, o SAT também pode ser um problema de subconjunto ("escolha um subconjunto de variáveis ​​verdadeiras"). Ou HAMCYCLE é um problema de permutação em vértices ou um problema de subconjunto em arestas? (BTW, talvez os "problemas de atribuição" possam realmente ser "problemas de partição", pense em dizer 3 cores).
Juho
3

Quanto à sua primeira pergunta, Allender afirma (em Ampliando limites inferiores por meio de auto-redutibilidade ) que nenhum problema natural de NP-completo é conhecido por estar fora do NTIME (n). Isso significa que todos os conjuntos NP-completos naturais conhecidos têm testemunhas de tamanho linear.

Mohammad Al-Turkistany
fonte
1
Observe que o comprimento do caminho de aceitação mais longo na máquina de Turing não determinística corresponde ao tamanho da testemunha.
Mohammad Al-Turkistany
1

Considere a seguinte variante do problema MAXCLIQUE .

Instância: Um circuito C com 2 n bits de entrada e tamanho polinomialmente limitado em n . Esse circuito determina implicitamente um gráfico em 2 n vértices, de modo que cada vértice seja identificado com uma sequência de n bits, e dois vértices serão conectados com uma aresta se a sequência de 2 n bits obtida pela concatenação dos dois IDs de vértices for aceito pela C . Seja G ( C ) denotado este gráfico. Note-se que ele tem muitas vértices exponencialmente em N , mas ainda é determinada pelo tamanho descrição polinomial de C .C2nn2nn2nCG(C)nC

Pergunta: Does L ( C ) conter um clique de tamanho n k , onde k é uma constante fixa?G(C)nkk

Notas:

  1. O problema é NP-completo. A contenção em N P é óbvia. A completude pode ser comprovada pela observação de que, se o circuito aceitar apenas pares de vértices nos quais cada ID é no máximo N = 2 n k , então G ( C ) pode ser um gráfico N- vértice arbitrário, além de muitos vértices isolados. (Qualquer gráfico desse tipo N- vertex pode ser codificado em C , pois é permitido que C tenha tamanho polinomial em n e também em N ). Então a pergunta se torna: existe uma camarilha de tamanho N / 2 em um NNPN=2nkG(C)NNCCnNN/2N-vertex graph? This is known to be NP-complete, for general NN. The issue that NN is not arbitrary, it is restricted to N=2nkN=2nk, can be eliminated by appropriate padding.

  2. The natural witness for the original problem is the nknk-sized clique, which can be described by an O(nk+1)O(nk+1) long string (an nn-bit string for each of the nknk vertices). Note that kk can be a very large constant, so the witness can be much longer than linear. (Even if the input size is the description of CC, rather than nn, this witness can be still much longer, because kk can be chosen independently of CC.)

  3. The problem can be viewed as natural, since it is a variant of MAXCLIQUE.

  4. When Allender wrote "no natural NP-complete problem is known to lie outside of NTIME(n)NTIME(n)," (see Amplifying Lower Bounds by Means of Self-Reducibility, Section 7), he may have had a narrower concept of naturalness in mind. For example, natural could be narrowed to something that people really want to solve on the grounds of independent, practical motivations. It is not enough if the problem is not constructed via diagonalization.

Andras Farago
fonte
I am not sure I follow your reduction of Half-Clique to this problem, to establish completeness in NP. Given an nn-vertex instance of Half-Clique, what circuit does it map to?
András Salamon
@AndrásSalamon Let GG be an N=2nkN=2nk-vertex graph, serving as input graph of Half-Clique. Then CC is the circuit that accepts any node pair (u,v)(u,v), if uN,vNuN,vN (as binary numbers), and (u,v)E(G)(u,v)E(G), otherwise CC rejects. (This CC can be implemented as a polynomial sized circuit.) Then G(C)G(C) will contain GG on the first NN nodes, plus 2nN2nN additional isolated nodes. The graph G(C)G(C) has a clique of size nknk precisely when GG has a half-clique.
Andras Farago