¿Ya se conoce el tamaño de membresía de los testigos para cada idioma de NP?

La pregunta se me ocurrió cuando recibí la respuesta de Dana Moshkovitz a otro tema .

Sea $L$ un lenguaje NP , y sea $R_L$ la relación NP respectiva . Sabemos que existe algún polinomio $p$ tal que:

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

La declaración anterior solo requiere la existencia de tal , pero no obliga a que se determine explícitamente . En contraste, para cada lenguaje NP que conozco, ya se conoce: $p$ $p$

Para SAT, el tamaño del testigo es igual al número de átomos que aparecen en la fórmula.
Para Hamiltonicity, el tamaño del testigo es , donde es el conjunto de vértices. $O(|V|)$ $V$
Para Graph 3-Coloring, el tamaño del testigo es , donde es el conjunto de vértices. $O(|V|)$ $V$

¿Existe un lenguaje NP (incluso uno artificial), para el cual sabemos que existe algún polinomio limita el tamaño del testigo, pero no podemos determinar explícitamente ? $p$ $p$

cc.complexity-theory np MS Dousti
fuente

Para cualquier lenguaje dado en NP, hay muchas relaciones de NP que dan lugar a él. ¿Está preguntando acerca de los lenguajes

donde se desconoce el polinomio mínimo

(es decir, donde podemos tratar de minimizar el polinomio observando diferentes relaciones que dan lugar al mismo

), o sobre las relaciones donde se desconoce el polinomio

correspondiente (pero sabemos que existe)

L

$L$

p

$p$

L

$L$

p

$p$

Joshua Grochow

@ Joshua: Podría estar malinterpretando su comentario, pero si conocemos el

mínimo sobre todas las relaciones para algún problema de NP completo y si no es cero, ¿eso no significa

p

$p$

P \neq N P

$P\neq NP$

Cong Han

@Cong: Tienes razón. Supongo que me refería al mínimo p que conocemos , por ejemplo, supuestos estándar de módulo / estado actual de la técnica. Por ejemplo, creo que el artículo STOC 2010 de Ryan Williams muestra que si hay una relación para SAT con el tamaño de testigo

, entonces

, por lo que mostrar tal cosa está más allá de la comprensión actual.

o (n)

$o(n)$

N E X P ⊈ P / p o l y

$NEXP \not\subseteq P/poly$

Joshua Grochow

@ Joshua: ¡Claro, por supuesto! Gracias.

Cong Han

Si hay una relación para el Circuito SAT con el tamaño del testigo

, donde

es el número de entradas al circuito

es el tamaño del circuito, entonces sí,

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

Si no le importan los lenguajes artificiales, podemos construir tales problemas utilizando prácticamente cualquier número k cuyo valor sea desconocido para los matemáticos. Por ejemplo, no sabemos el valor de R (5,5) (el quinto número de Ramsey ), o el tamaño del menor excluido más grande de la familia de gráficos sin nudos (este número es finito debido al teorema de Robertson-Seymour ), o el valor de BB (10), donde BB () representa la función Busy Beaver . Sea k igual a cualquiera de estos números. Sabemos que k es finito, pero no sabemos el valor de k.

Ahora construya algún problema en NP donde el testigo es de tamaño $O(n^k)$ . No puedo pensar en una buena manera de hacer esto, pero aquí hay una manera. Deje que la entrada sea una descripción sucinta de un gráfico. Como el tamaño de la descripción es n, el gráfico está en exponencialmente muchos vértices. (Por ejemplo, tal vez la entrada es un circuito que acepta dos entradas x e y y le dice si (x, y) es un borde en el gráfico). La pregunta es determinar si el gráfico contiene una ruta de longitud . Este problema está en NP porque el probador puede enviar la lista de vértices en la ruta en orden, que el verificador puede verificar. El tamaño del testigo es . $n^k$ $n^k$

Robin Kothari
fuente

¿Ya se conoce el tamaño de membresía de los testigos para cada idioma de NP?

Respuestas: