¿Hay problemas de NP completo con soluciones de tiempo esperado polinomiales?

24

¿Hay algún problema de NP completo para el cual se sabe un algoritmo de que el tiempo de ejecución esperado es polinómico (para alguna distribución sensata sobre las instancias)?

Si no, ¿hay problemas para los cuales se ha establecido la existencia de tal algoritmo?

¿O la existencia de tal algoritmo implica la existencia de un algoritmo determinista de tiempo polinómico?

cc.complexity-theory np-hardness Steve Kroon
fuente

66

No entiendo bien cuál es la pregunta. ¿Está solicitando resultados de caso promedio para problemas NP-hard o pregunta si podemos resolver los problemas NP-hard en el peor de los casos en el tiempo polinómico esperado?

Moritz

2

¿Qué quiere decir con "tiempo de ejecución esperado"? ¿Está tomando expectativas sobre alguna distribución aleatoria de entradas (como parece pensar la mayoría de las respuestas), o sobre la distribución de bits aleatorios utilizados por el algoritmo (el significado habitual para algoritmos aleatorios), o ambos?

Jeffε

@ Moritz: estoy preguntando acerca de los resultados promedio de casos para problemas NP-difíciles. Resolver problemas difíciles de NP en el peor de los casos en el tiempo polinómico esperado me parece un resultado aún más fuerte, por lo que también me interesarían dichos resultados. @JeffE Estoy hablando del tiempo esperado con cierta distribución sobre las instancias. Si el algoritmo es aleatorio, también se esperaría más de los bits aleatorios. Pero mi pregunta no es principalmente sobre algoritmo aleatorio.

Steve Kroon el

3

Una técnica de relleno simple le brinda una forma de construirlos a partir de cualquier problema.

Supongamos que es un lenguaje Completo que requiere tiempo para resolver. Entonces deje que sea Entonces se resuelve de la siguiente manera: un algoritmo de tiempo lineal verifica si una cadena de entrada tiene un número par de caracteres de los cuales los primeros son . Si no, rechaza; de lo contrario resuelve $L$ $NP$ $O(2^{n})$ $K$

K = {1^{norte} X El | ‖ X ‖ = norte y X \in L}

$K=\{1^nx\ |\ \|x\|=n \text{ and }x\in L\}$

K

$K$

n

$n$

1^{n}

$1^n$

x \overset{?}{\in} L

$x\overset{?}{\in}L$ . Si

se dibuja de manera uniforme al azar, ¿el tiempo esperado para resolver

es

y \in_{R} {0, 1}^{2 n}

$y\in_R \{0,1\}^{2n}$

y \overset{?}{\in} K

$y\overset{?}{\in}K$

\frac{1}{2^{2 norte}} (2^{norte} \cdot 2^{norte} + (2^{2 norte} - 2^{norte}) O (norte)) = 1 + (1 - \frac{1}{2^{norte}}) O (norte) \in O (norte) .

$\frac{1}{2^{2n}}\big(2^n\cdot 2^n+(2^{2n}-2^n)O(n)\big) = 1+(1-\frac{1}{2^n})O(n)\in O(n).$

es -Completo. Una reducción de es: $K$ $NP$ $L$

X \in {0 0, 1}^{norte} \mapsto 1^{norte} X

$x\in \{0,1\}^n \mapsto 1^nx$

Lieuwe Vinkhuijzen
fuente

13

Existe un algoritmo de tiempo polinómico para encontrar ciclos hamiltonianos en gráficos aleatorios, que tiene éxito asintóticamente con la misma probabilidad de que exista un ciclo hamiltoniano. Por supuesto, este problema es NP-duro en el peor de los casos.

$n$

Referencia: "Un algoritmo para encontrar ciclos de Hamilton en gráficos aleatorios"

Bollobas, Fenner, Friso

http://portal.acm.org/citation.cfm?id=22145.22193

Aaron Roth
fuente

10

Con respecto a su última pregunta sobre si la existencia de un buen algoritmo de caso promedio implicaría la existencia de un buen algoritmo del peor de los casos: esta es una pregunta abierta importante que es particularmente interesante para los criptógrafos. La criptografía requiere problemas que son difíciles en promedio, pero a los criptógrafos les gustaría basar sus construcciones en las suposiciones mínimas posibles, por lo que es de gran interés encontrar problemas en los que la dureza del caso promedio sea demostrablemente igual a la dureza del peor de los casos.

Se sabe que varios problemas de red tienen tales reducciones del peor de los casos al caso promedio. Véase, por ejemplo, Generando instancias difíciles de problemas de red de Ajtai, y un artículo de encuesta de Micciancio.

Ian
fuente

9

$n$ $n$

Referencia:

Alexander D. Scott y Gregory B. Sorkin. Resolver instancias aleatorias dispersas de Max Cut y Max 2-CSP en tiempo lineal esperado Peine. Probab Comput., 15 (1-2): 281-315, 2006. Preprint

Serge Gaspers
fuente

2

Θ (n)

$\Theta(n)$

G (n, c / n)

$G(n,c/n)$

@Bart: podría haber entendido mal la pregunta. Afirmo que Max 2-CSP con un número lineal de cláusulas es NP-hard, pero que existe un algoritmo con tiempo lineal esperado para resolver este problema para instancias aleatorias.

Serge Gaspers

Básicamente, si entiendo su argumento correctamente, está diciendo que Max 2-CSP equipado con la distribución G (n, c / n) sobre los gráficos subyacentes se puede resolver en el tiempo lineal esperado. Estoy de acuerdo con Bart en que la distribución no me parece completamente "sensata" o "natural", pero creo que responde adecuadamente a mi pregunta.

Steve Kroon

@ Steve: Estoy de acuerdo.

Serge Gaspers

7

Esto no responde su pregunta por completo, pero para una encuesta de resultados en instancias aleatorias de 3-SAT puede ver esto: www.math.cmu.edu/~adf/research/rand-sat-algs.pdf

Por lo general, es difícil definir qué significa realmente "distribución sensible". Puede seguir este enlace para leer más sobre esto en la encuesta "Complejidad del tiempo promedio" de Bogdanov y Trevisan: http://arxiv.org/abs/cs/0606037 .

Grigory Yaroslavtsev
fuente

Gracias por los enlaces. Desafortunadamente, los resultados del documento 3-SAT "con alta probabilidad" no son lo suficientemente fuertes (por lo que puedo ver) para afirmar mi consulta. Estoy de acuerdo en que la "distribución sensata" puede ser difícil. En esto, preferiría que la distribución no se elija obviamente para que el "espacio de instancia efectivo" no reduzca simplemente el problema a uno que se sabe que está en P.

Steve Kroon

5

"Colorear gráficos aleatorios en el tiempo polinómico esperado" por Amin Coja-Oghlan y Anusch Taraz

$G \in G(n, p)$ $p < 1.01/n$ $O(√np)$

http://www.springerlink.com/content/87c17d4dacbrc0ma/

Joel Rybicki
fuente

¿Hay problemas de NP completo con soluciones de tiempo esperado polinomiales?

Respuestas: