¿Para qué problemas en P es más fácil verificar el resultado que encontrarlo?

52

Para (versiones de búsqueda) de problemas completos de NP , verificar una solución es claramente más fácil que encontrarla, ya que la verificación se puede hacer en tiempo polinómico, mientras que encontrar un testigo lleva (probablemente) tiempo exponencial.

En P , sin embargo, la solución también se puede encontrar en tiempo polinómico, por lo que no parece obvio cuándo es la verificación más rápida que encontrar la solución. De hecho, diferentes problemas parecen comportarse de manera diferente desde este punto de vista. Algunos ejemplos:

  1. 3SUM: dados números de entrada, encuentre 3 entre ellos que sumen 0. Por lo que sé, el algoritmo más rápido conocido se ejecuta en el tiempo , y este orden se conjetura como óptimo. Por otro lado, la verificación de una solución es mucho más rápida, ya que todo lo que tenemos que hacer es verificar que los 3 números encontrados sumen 0.O ( n 2 - o ( 1 ) )nO(n2o(1))

  2. Rutas más cortas de todos los pares: dado un gráfico con pesos de borde, calcule su matriz de distancia de ruta más corta. Una vez que se proporciona una matriz de este tipo, ¿se puede verificar más rápido que es la matriz de distancia correcta, en lugar de volver a calcularla? Supongo que la respuesta es quizás sí, pero ciertamente es menos obvio que para 3SUM.

  3. Programación lineal. Si se proporciona una solución óptima reclamada, comprobarla es más fácil que volver a calcularla, cuando también se proporciona información auxiliar (una solución dual óptima). Por otro lado, si solo está disponible la solución primaria, no está claro si se puede verificar más rápido, en lugar de resolver el LP.

Pregunta: ¿qué se sabe sobre este tema? Es decir, ¿cuándo es más fácil verificar una solución para un problema en P que encontrar la solución?

Andras Farago
fuente
77
Creo que muchos ejemplos provienen de problemas NP-completos que caen en P cuando arreglamos algunos parámetros. Por ejemplo, verificar si un gráfico contiene una camarilla de tamaño para fijo . La verificación lleva tiempo lineal, pero a menos que P = NP, la complejidad del problema de búsqueda (polinomio) depende dek kkkk
Marzio De Biasi
16
Podemos verificar que una lista de enteros esté ordenada con comparaciones, pero se necesitan comparaciones para ordenar una lista no ordenada. n - 1nn1Θ(nlogn)
Thomas
77
¿Desea que sea fácil verificar las instancias de sí y no para los problemas de decisión? Para 3SUM, si bien es fácil verificar instancias sí en tiempo constante, no sé si es fácil verificar una instancia no. ¿O está pensando más en la línea de problemas donde hay una salida no booleana, como la multiplicación de matrices? (La multiplicación de matrices es un ejemplo de lo que quieres si permites algoritmos aleatorios).
Robin Kothari
3
"Por otro lado, la verificación de una solución es mucho más rápida, ya que todo lo que tenemos que hacer es verificar que los 3 números encontrados sumen 0". - También debemos verificar que los 3 números encontrados son realmente parte de la entrada.
hvd 01 de
3
¿Hay problemas para los cuales sabemos que la verificación no es más fácil?
Raphael

Respuestas:

24

se sabe que, dado un gráfico G y un árbol T, se puede verificar en tiempo lineal que T es un árbol de extensión mínima de G. Pero todavía no tenemos un algoritmo determinista de tiempo lineal para calcular el MST. Por supuesto, la brecha es pequeña (1 vs ), pero sigue ahí :))α(n)

Suresh Venkat
fuente
44
Tal vez sea justo agregar que hay un algoritmo aleatorio que se ejecuta en el tiempo lineal esperado (el algoritmo de Karger-Klein-Tarjan).
Sasho Nikolov
2
Además, en caso de que alguien quiera un enlace, este es el algoritmo de verificación MST de tiempo lineal más simple que conozco: webhome.cs.uvic.ca/~val/Publications/Algorithmica-MSTverif.ps .
Sasho Nikolov
20

Este documento muestra que existen algoritmos de verificación para las instancias YES y NO para 3 problemas, incluidos Max flow, 3SUM y APSP, que son más rápidos por un factor polinómico que los límites conocidos para calcular la solución en sí.

Hay una clase de problemas, a saber, los que mejoran el tiempo de ejecución es SETH-hard, cuyo tiempo de ejecución para verificar NO es improbable que sea significativamente más rápido que el tiempo para calcular la solución, de lo contrario, la conjetura de este artículo se llama No determinista La hipótesis del tiempo exponencial fuerte fallaría.

Thatchaphol
fuente
18

Para algunos problemas parece que no hay diferencia. En particular, Vassilevska Williams & Williams muestran:

  • para la multiplicación matricial booleana, calcular el producto matricial y verificar el producto subcúbico equivalente de la matriz, lo que significa que ambos tienen algoritmos de tiempo subúbico o ninguno de ellos tiene.

  • Lo mismo es cierto para el cálculo y la verificación de productos matriciales sobre cualquier "estructura extendida (min, +)" (ver el documento para la definición, pero esto incluye muchos problemas naturales).

(Ahora, por supuesto, es posible que todos estos problemas tengan algoritmos subcúbicos, y luego puede haber una diferencia polinómica entre la computación y la verificación, pero para estos problemas no puede haber una diferencia cúbica. Y me parece plausible que en de hecho, todos requieren esencialmente un tiempo cúbico).

Joshua Grochow
fuente
2
Por otro lado, para la multiplicación de matrices en un campo suficientemente grande, existe un algoritmo aleatorio de tiempo cuadrático para la verificación, mientras que el tiempo de ejecución más rápido para calcular el producto es n ^ omega.
Thatchaphol
2
@Thatchaphol: Sí, aunque muchas personas creen que omega = 2 ... Además, es ampliamente reconocido que la multiplicación de matrices booleanas (es decir, calcular la matriz múltiple sobre el booleano o semianillo) tiene una naturaleza algo diferente a la multiplicación de matrices sobre un campo.
Joshua Grochow
16
  • Decidir si existe un valor en una matriz lleva tiempo (o si la matriz está ordenada).Ω(n)Ω(logn)

    Es posible verificar que una matriz contiene el valor dado en una posición dada en el tiempo .O(1)

  • La ordenación (en el modelo de comparación) lleva tiempo , pero es posible verificar que una matriz o lista esté ordenada en el tiempo .Ω(nlogn)O(n)

Rafael
fuente
2
Similar: determinar si hay un elemento duplicado es en el modelo de comparación, pero, por supuesto, se puede verificar en . Ω(nlogn)O(1)
SamM
@SamM: ¿Quieres decir verificado en ? ¿Qué te dan exactamente? Siento que estás haciendo una comparación injusta. O(n)
Mehrdad el
@Mehrdad buen punto; si se le da el valor (en lugar de los índices) es para verificar. Puedo ver un buen argumento de que esta es la mejor manera de verlo. Θ(n)
SamM
10

Creo que muchos ejemplos provienen de problemas NP-completos que caen en P cuando arreglamos uno o más parámetros .

Por ejemplo, verificar si un gráfico contiene una camarilla de tamaño es NP-completo si es parte de la entrada, tiempo polinomial solucionable si es fijo.kkk

Para cualquier fija , la verificación lleva un tiempo lineal, pero a menos que , la complejidad del problema de búsqueda (polinomio) depende de ( .kP=NPkΩ(nk))

Otros ejemplos: encontrar una ruta hamiltoniana de longitud , colorear en gráficos de ancho de árbol acotado, ...k

Marzio De Biasi
fuente
9

Decidir la primalidad: la variante más conocida de AKS parece decidir la primalidad en el tiempo , mientras que el clásico certificado de primalidad de Pratt implica que la primalidad se puede decidir en un tiempo no determinista .O~(n6)O~(n3)

Joe Bebel
fuente
¡El complemento (composición) es aún más fácil de presenciar!
Yonatan N
3

Un artículo de Abboud et al. recientemente aceptado en SODA 2016 muestra que el isomorfismo de subárbol no puede resolverse en tiempo menos que la hipótesis del tiempo exponencial fuerte sea falsa. Por supuesto, podemos verificar un isomorfismo en tiempo lineal.O(n2ϵ)

En otras palabras, el SETH nos da un problema natural en con una brecha entre encontrar y verificar. Ω ( n 1 - ϵ )PΩ(n1ϵ)

En particular, se conoce un algoritmo para árboles enraizados de grado constante (para los que todavía se aplican los resultados de límite inferior de Abboud et al.). Entonces, bajo SETH, la brecha de búsqueda-verificación casi lineal es esencialmente estrecha para este problema.O(n2/logn)

SamM
fuente