Ejemplos donde la singularidad de la solución hace que sea más fácil encontrar

37

La clase de complejidad consiste en esos problemas que pueden decidirse por una máquina de Turing no determinista de tiempo polinomial que tiene como máximo una ruta computacional de aceptación. Es decir, la solución, si la hay, es única en este sentido. Se cree altamente improbable que todos los problemas estén en , porque según el Teorema Valiant-Vazirani esto implicaría el colapso .N P U P P N P = R PUPNPUPPNP=RP

Por otro lado, no se sabe que ningún problema completo , lo que sugiere que el requisito de solución única todavía los hace más fáciles.N PUPNP

Estoy buscando ejemplos, donde el supuesto de unicidad conduce a un algoritmo más rápido.

Por ejemplo, observando los problemas del gráfico, ¿se puede encontrar una camarilla máxima en un gráfico más rápido (aunque posiblemente todavía en tiempo exponencial), si sabemos que el gráfico tiene una camarilla máxima única ? ¿Qué tal una coloración única, un camino hamiltoniano único, un conjunto dominante mínimo único, etc.k

En general, podemos definir una versión de solución única de cualquier completo , reduciéndolo a . ¿Se sabe para alguno de ellos que agregar el supuesto de unicidad conduce a un algoritmo más rápido? (Permitiendo que siga siendo exponencial).U PNPUP

Andras Farago
fuente
77
Su primera oración da la definición correcta de UP, pero el resto de sus referencias a UP realmente deberían ser PromiseUP (incluido Valiant-Vazirani). De cualquier manera, esta es una pregunta muy interesante. Dos ejemplos: 1) El factoring está en UP y tiene un algoritmo más rápido que los conocidos para problemas NP-completos (pero el factoring también está en coNP e incluso coUP, por lo que no está tan claro que la unicidad subyace al algoritmo rápido aquí). 2 ) Sodoku, como se define tradicionalmente, está en PromiseUP, sin embargo, no conozco ningún enfoque para resolver Sudoku que aproveche la singularidad prometida.
Joshua Grochow
99
La paridad del número de caminos hamiltonianos se puede encontrar en el tiempo ( arxiv.org/pdf/1301.7250.pdf ), mientras que el algoritmo más conocido para el problema de decisión toma casi 2 n tiempo. 1.618n2n
Alex Golovnev
8
Aquí hay un ejemplo de la computación cuántica: considere el problema de búsqueda en n elementos. Si sabe que hay exactamente 1 elemento marcado, puede encontrarlo con un algoritmo cuántico exacto con consultas. Si no conoce el número de elementos marcados, cualquier algoritmo cuántico exacto necesitanconsultas. Θ(n)n
Robin Kothari

Respuestas:

22

3-SAT puede ser uno de esos problemas. Actualmente, el mejor límite superior para Unique 3-SAT es exponencialmente más rápido que para el 3-SAT general. (La aceleración es exponencial, aunque la reducción en el exponente es pequeña.) El poseedor del récord para el caso único es este artículo de Timon Hertli.

El algoritmo de Hertli se basa en el importante algoritmo PPSZ de Paturi, Pudlák, Saks y Zane para -SAT, que creo que sigue siendo el más rápido para k 5 (ver también este artículo de la enciclopedia). El análisis original mostró mejores límites para Unique k -SAT que para k -SAT general cuando k = 3 , 4 ; posteriormente, sin embargo, Hertli mostró en un documento diferentekk5kkk=3,4que podría obtener los mismos límites para el algoritmo PPSZ (un poco ajustado), sin suponer unicidad. Entonces, tal vez la unicidad ayude, y definitivamente puede simplificar el análisis de algunos algoritmos, pero nuestra comprensión del papel de la unicidad para -SAT todavía está creciendo.k

Hay evidencia de que Unique -SAT no es mucho más fácil que el general k -SAT. La hipótesis del tiempo exponencial fuerte (SETH) afirma que no hay δ < 1, de modo que n -variable k -SAT se pueda resolver en el tiempo O ( 2 δ n ) para cada constante k 3 . En un documento de Calabro, Impagliazzo, Kabanets y Paturi se demostró que, si SETH se cumple, entonces la misma afirmación es cierta para Unique k -SAT. Además, si general kkkδ<1nkO(2δn)k3kk-SAT requiere un tiempo exponencial, es decir, hay algunos modo que k -SAT general no puede resolverse en el tiempo O ( 2 ϵ n ) , entonces lo mismo debe ser cierto para Unique 3-SAT. Vea el documento para la declaración más general. k3,ϵ>0kO(2ϵn)

(Nota: la notación suprime los factores polinómicos en la longitud de entrada).O

Andy Drucker
fuente
1
"cierto para Unique 3-SAT" "cierto para Unique k-SAT"
Hola Ricky, no veo ningún problema con lo que está escrito. La última afirmación sobre Unique 3-SAT se encuentra en el resumen del artículo.
Andy Drucker
Ah, veo que se necesitarían diferentes s para lo que estaba diciendo,k lo que solo lo haría confuso.
16

El problema más corto de la ruta disjunta de 2 vértices en gráficos no dirigidos recientemente resuelto (ICALP14) por A. Bjorklund y T. Husfeldt. Pero la solución determinista es para el caso de la existencia de una solución única. En el caso de que haya más de una solución, demostraron que el problema pertenece a RP . Como los autores del artículo mencionan, no se sabe si el problema está en P en el escenario general.

Saeed
fuente
3
Thank you, it is very interesting. The general case, where the solution is not unique, is also a nice example of a natural (or even practical) graph problem, which is now proved to be in RP, but not known to be in P.
Andras Farago
10

Outside of complexity theory and the analysis of algorithms, the assumption that there can be only one solution forms the basis for some of the standard rules used to deduce the solution in Sudoku puzzles. These rules generally involve looking for ways in which parts of the puzzle might be able to have two or more solutions that don't interact with the rest of the puzzle. That can't happen in the actual solution, so if a pattern that threatens to cause this is found, then it must be broken, allowing the solver to deduce constraints on what the actual solution can look like. See http://www.brainbashers.com/sudokuuniquerectangles.asp for some examples of deduction rules based on uniqueness.

David Eppstein
fuente
9

Mencionando otro resultado de Björklund, si tiene la garantía de que hay como máximo un ciclo hamiltoniano en un gráfico, puede decidir si un gráfico sol es Hamiltoniano más rápido de lo que puedes en general.

El supuesto de unicidad significa que la paridad del número de jamón. caminos es lo mismo que decidir si el gráfico es hamiltoniano.

El método de Björklund calcula de manera determinista la paridad del número de ciclos hamiltonianos enO(1.619norte)mientras que el algoritmo aleatorio más conocido para Hamiltonicity no dirigido se ejecuta enO(1.657norte) , y el mejor algoritmo determinista para Hamiltonicity Dirigido (que yo sepa) aún tiene 50 años O(norte22norte) algoritmo de programación dinámica de Bellman, Held y Karp.

RB
fuente