Mejor complejidad de tiempo determinista conocida límite inferior para un problema natural en NP

25

¿Esta respuesta a los principales problemas no resueltos en informática teórica? La pregunta indica que está abierto si un problema particular en NP requiere tiempo de .Ω(n2)

Mirar los comentarios a continuación me hizo preguntarme:

Además del relleno y trucos similares, ¿cuál es el límite inferior de complejidad de tiempo más conocido en una máquina RAM determinista (o máquina Turing determinista de cinta múltiple) para un problema interesante en NP (que se establece de forma natural)?

¿Hay algún problema natural en NP que se sepa que no se puede resolver en un tiempo determinista cuadrático en un modelo de máquina razonable?

Esencialmente, lo que estoy buscando es un ejemplo que descarte la siguiente afirmación:

cualquier problema natural de NP puede resolverse en tiempo.O(n2)

¿Conocemos algún problema de NP similar a los del artículo de Karp de 1972 o Garey y Johnson 1979 que requiere tiempo determinista ? ¿O es posible a nuestro leal saber y entender que todos los problemas naturales interesantes de NP pueden resolverse en el tiempo determinista ?Ω(n2)O(n2)

Editar

Aclaración para eliminar cualquier confusión resultante del desajuste entre el límite inferior y no un límite superior : estoy buscando un problema que sabemos que no podemos resolver en . Si un problema satisface el requisito más fuerte de que se necesita u tiempo (para todas las entradas lo suficientemente grandes) entonces mejor, pero infinitamente a menudo lo hará.o(n2)Ω(norte2)ω(norte2)

Anónimo
fuente
55
Los únicos límites inferiores superlineales que conozco para problemas naturales en NP son las compensaciones de espacio de tiempo para SAT ( dl.acm.org/citation.cfm?doid=1101821.1101822 , y hay trabajo de seguimiento por @RyanWilliams, que sabrá mucho más) . y no dicen nada si se permite que el espacio sea lineal.
Sasho Nikolov
@SashoNikolov, los resultados en el espacio de tiempo son para SAT y no hay ninguna reducción de muchos problemas naturales de NP a SAT donde el tamaño de la salida está limitado linealmente en el tamaño de la entrada. Un límite inferior de para algún problema de NP natural no implica necesariamente un resultado más fuerte para SAT del que se conoce actualmente. Ω(norte2)
Anónimo
1
Estoy diciendo que no conozco ningún límite inferior súper lineal para ningún otro problema NP natural
Sasho Nikolov
¿Cómo se utiliza el relleno para obtener un problema artificial en NP con un límite inferior de complejidad de tiempo ? Ω(n2)
Robin Kothari
@RobinKothari, tome un problema en DTIME ( ) y acóplelo. La prueba se basa en el teorema de la jerarquía temporal no determinista y el relleno no era la forma correcta de referirse al ejemplo. Podemos tomar un problema NP en NTIME ( Ω ( n 2 ) ) directamente. Ω(2n)Ω(n2)
Anónimo

Respuestas:

16

Adachi, Iwata y Kasai en una presentación en papel de JACM en 1984 muestran por reducción que el juego Cat and -Mice tiene un límite inferior n Ω ( k ) . El problema está en P para cada k . El problema se juega en un gráfico dirigido. Los movimientos consisten en el gato y luego uno de los k ratones alternando pasos. Los ratones ganan si pueden aterrizar en un nodo de queso designado antes de que el gato caiga en ellos. La pregunta es si el gato tiene una victoria forzada. En realidad, es un problema completo, por lo que el límite inferior se basa realmente en la diagonalización que proporciona la jerarquía de tiempo.knΩ(k)kk

Grandjean demostró que el límite inferior de tiempo de Pippenger, Paul, Szemeredi y Trotter se aplica a una codificación SAT, aunque el resultado de Santhanam puede subsumirlo.

Además de los límites inferiores de compensación de espacio-tiempo para SAT mencionados en otros comentarios, hay un conjunto de trabajos sobre límites inferiores de programas de ramificación que implican compensaciones de espacio-tiempo para máquinas Turing. Para problemas como FFT, clasificación o computación de funciones hash universales, existen límites inferiores cuadráticos de Borodin-Cook, Abrahamson, Mansour-Nisan-Tiwari, pero estos son para funciones con muchas salidas. Para problemas de decisión en P, existen límites inferiores de compensación de espacio-tiempo que se aplican para límites de tiempo que son pero estos son más débiles que los conocidos para SAT.O(nlogn)

Paul Beame
fuente
¿Alguna idea sobre la relación del juego del gato y el ratón con NP?
vzn
12

El resultado clásico que conozco se debe a Paul, Pippenger, Szemeredi y Trotter (1983) y separa el tiempo lineal determinista del no determinista.

Luego, está el resultado más reciente de Fortnow, Lipton, van Melkebeek y Viglas (2004) que ya se mencionó. La singularidad de este resultado es que es un resultado de compensación espacio-tiempo, que limita tanto el espacio como el tiempo.

Sin embargo, también estoy al tanto de un resultado debido a Santhanam (2001) que demuestra un límite inferior de . Este resultado es ligeramente más fuerte para las limitaciones de tiempo que el anterior, pero no proporciona ninguna garantía de espacio.ω(nlogn)

Teniendo en cuenta lo anterior y mi conocimiento del campo, diría que probar que hay un problema completo de que no se puede resolver en el tiempo determinista O ( n 2 ) sería un gran paso. Hasta donde yo sé, este resultado se considera altamente no trivial y es probable que requiera nuevas técnicas de límite inferior.NPO(n2)

Nota: Mi redacción del problema en el último párrafo es diferente a la de su pregunta. Podría ser quisquilloso (y quizás no de mucha ayuda) y decirte que trivialmente hay un número infinito de problemas en y, por lo tanto, en N P que no se pueden resolver en el tiempo determinista O ( n 2 ) , por el tiempo determinista Teorema de la jerarquía.PNPO(n2)


Editar: Después de pensarlo más, así es como puede encontrar un problema en que se adapte a sus necesidades:NP

  1. Cualquier problema natural con un límite inferior de , donde f ( n ) = Ω ( n 2 log n ) . Según el teorema de la jerarquía DTIME, requiere tiempo ω ( n 2 ) . Creo que existen algunos de estos.DTIME(f(n))f(n)=Ω(n2logn)ω(n2)
  2. Cualquier problema natural con un límite inferior de , donde f ( n ) = ω ( n 2 ) , mediante el uso de la jerarquía NTIME. No estoy al tanto de ninguno de estos problemas naturales.NTIME(f(n))f(n)=ω(n2)
  3. Cualquier problema natural con un límite inferior de , donde f ( n ) = ω ( n 2 / log n ) . Esto se justifica por la separación TIEMPO-ESPACIO. Yo creo esoSPACE(f(n))f(n)=ω(n2/logn)

Los límites inferiores anteriores deberían ser válidos para la complejidad de bits del problema.

Una vez más, si restringe su atención a los problemas completos de , no tengo conocimiento de tales límites inferiores.NP

chazisop
fuente
3
la pregunta se refiere a un problema natural
Sasho Nikolov
Gracias pero no estoy preguntando sobre el tiempo determinista frente al no determinista: puede tomar cualquier problema en NTIME ( ) siempre que requiera un tiempo determinista Ω ( n 2 ) . Ni el segundo resultado responde mi pregunta no porque restrinja el espacio sino porque es solo para SAT, vea mi respuesta a Sasho Nikolov debajo de la pregunta. Y hay problemas NP-completos que no se pueden resolver de manera determinista Ω ( n 2 ) mediante relleno, estoy buscando ejemplos naturales . nkΩ(n2)Ω(n2)
Anónimo
@ Anónimo ¿Estás diciendo que SAT no es un problema natural?
Sasho Nikolov
@SashoNikolov, SAT es un problema natural. Sin embargo, el resultado no responde mi pregunta positivamente. Por lo tanto, lo interpreté como diciendo que no se conoce una mejor respuesta a mi pregunta. Ese no tiene por qué ser el caso. En ese sentido, no responde mi pregunta.
Anónimo
2
Lo intentaré por última vez: si bien tiene razón en que no existe tal implicación, estoy bastante seguro de que no existe un límite inferior cuadrático incondicional conocido contra el tiempo determinista para ningún problema natural de NP. No se sigue de los resultados del SAT; es solo el estado de cosas
Sasho Nikolov
2

Quizás un ejemplo bastante natural proviene de la complejidad de Kolmogorov limitada en el tiempo :

kf(n)nxM|M|<f(|x|)Mx|x|k

Marzio De Biasi
fuente
Gracias, no es completamente artificial, pero no me parece un ejemplo natural satisfactorio.
Anónimo
2
Ω(nk)
@SashoNikolov: eliminé la parte de Ramsey ... necesita una prueba formal :-(
Marzio De Biasi
-7

Esto es simplemente plantear la misma pregunta de P = NP de una manera diferente, si puede demostrar que no se puede resolver en el tiempo cuadrático o encontrar un límite inferior absoluto, estaría demostrando que P! = NP

Alex Gonopolskiy
fuente
11
¿Por qué un límite inferior cuadrático para un problema natural en NP muestra P! = NP?
Robin Kothari