O tamanho da associação de testemunhas para cada idioma NP já é conhecido?

A pergunta me ocorreu quando recebi Dana Moshkovitz responder a outro tópico .

Deixe ser um NP Idioma, e deixá- ser o respectivo NP relação. Sabemos que existe algum polinômio tal que: $L$ $R_L$ $p$

$\forall x \in L, \\, \exists w \in \\{0,1\\}^{p(|x|)} \quad (x,w) \in R_L$

A declaração acima requer apenas a existência de tal , mas não força a sua determinação explícita . Por outro lado, para cada linguagem NP que eu conheço, já é conhecido: $p$ $p$

Para SAT, o tamanho da testemunha é igual ao número de átomos que aparecem na fórmula.
Para Hamiltonicidade, o tamanho da testemunha é , onde é o conjunto de vértices. $O(|V|)$ $V$
Para o Gráfico 3-Coloração, o tamanho da testemunha é , onde é o conjunto de vértices. $O(|V|)$ $V$

Existe uma linguagem NP (mesmo artificial), para a qual sabemos que existe algum polinômio limitando o tamanho da testemunha, mas não podemos determinar explicitamente ? $p$ $p$

cc.complexity-theory np MS Dousti
fonte

Para qualquer idioma no NP, existem muitas relações NP que o originam. Você está perguntando sobre as línguas

onde o polinômio mínimo

é desconhecido (isto é, onde podemos tentar minimizar o polinômio observando diferentes relações que dão origem ao mesmo

) ou sobre relações em que o polinômio correspondente

é desconhecido (mas sabemos que existe)?

L

$L$

p

$p$

L

$L$

p

$p$

Joshua Grochow 18/10/10

@ Josué: Eu posso estar entendendo mal o seu comentário, mas se soubermos o mínimo de

sobre todas as relações para algum problema NP-completo e se for diferente de zero, isso não significa

p

$p$

P \neq N P

$P\neq NP$

Cong Han

o (n)

$o(n)$

N E X P ⊈ P / p o l y

$NEXP \not\subseteq P/poly$

@ Josué: Certo, é claro! Entendi obrigado.

Cong Han

Se houver uma relação para o circuito SAT com tamanho de testemunha , onde é o número de entradas para o circuito é o tamanho do circuito, sim, .

k - ω (\log n)

$k-\omega(\log n)$

k

$k$

n

$n$

N E X P ⊈ P / p o l y

$NEXP \not\subseteq P/poly$

Ryan Williams

Respostas:

Se você não se importa com linguagens artificiais, podemos construir esses problemas usando praticamente qualquer número k cujo valor é desconhecido para os matemáticos. Por exemplo, não sabemos o valor de R (5,5) (o quinto número de Ramsey ) ou o tamanho do menor menor excluído da família de gráficos sem nós (esse número é finito devido ao teorema de Robertson-Seymour ) ou o valor de BB (10), onde BB () significa a função Busy Beaver . Seja k igual a qualquer um desses números. Sabemos que k é finito, mas não sabemos o valor de k.

Agora construa algum problema em NP, onde a testemunha é do tamanho . No topo da minha cabeça, não consigo pensar em uma boa maneira de fazer isso, mas aqui está uma maneira. Deixe a entrada ser uma descrição sucinta de um gráfico. Como o tamanho da descrição é n, o gráfico está exponencialmente em muitos vértices. (Por exemplo, talvez a entrada seja um circuito que aceite duas entradas x e y e diga se (x, y) é uma aresta no gráfico.) A questão é determinar se o gráfico contém um caminho de comprimento . Esse problema está no NP porque o fornecedor pode enviar a lista de vértices no caminho em ordem, que o verificador pode verificar. O tamanho da testemunha é . $O(n^k)$ $n^k$ $n^k$

Robin Kothari
fonte