Razones generales por las que hay problemas en P o BPP

Recientemente, cuando hablé con un físico, afirmé que, en mi experiencia, cuando un problema que ingenuamente parece que debería llevar un tiempo exponencial resulta no trivial en P o BPP, generalmente se puede identificar una "razón general" por la que ocurre la reducción. --- y casi siempre, esa razón pertenece a una lista de una docena o menos de "sospechosos habituales" (por ejemplo: programación dinámica, álgebra lineal ...). Sin embargo, eso me hizo pensar: ¿podemos realmente escribir una lista decente de tales razones? Aquí hay un primer intento incompleto de uno:

(0) Caracterización matemática. El problema tiene una caracterización "puramente matemática" no obvia que, una vez conocida, hace que sea inmediato que puede hacer una búsqueda exhaustiva en una lista de posibilidades de poli (n). Ejemplo: planaridad gráfica, para la cual se sigue un algoritmo O (n ⁶ ) del teorema de Kuratowski.

(Como "planar" señala a continuación, este fue un mal ejemplo: incluso una vez que conoces una caracterización combinatoria de la planaridad, dar un algoritmo de tiempo polinómico aún no es trivial. Entonces, permíteme sustituir un mejor ejemplo aquí: ¿qué tal? , digamos, "dada una entrada n escrita en binario, calcule cuántos colores se necesitan para colorear un mapa arbitrario incrustado en una superficie con n agujeros". No es obvio a priori que esto sea computable (¡o incluso finito!). Pero hay una fórmula conocida que da la respuesta, y una vez que se conoce la fórmula, es trivial calcularla en tiempo polinómico. Mientras tanto, "la reducción a menores excluidos / teoría de Robertson-Seymour" probablemente debería agregarse como una razón general por la cual algo puede ser En p.)

De todos modos, este no es el tipo de situación que más me interesa.

(1) Programación dinámica. El problema se puede dividir de una manera que permita una solución recursiva sin una explosión exponencial, a menudo porque las restricciones que deben cumplirse están organizadas en un orden lineal u otro simple. "Puramente combinatorio"; No se necesita estructura algebraica. Podría decirse que la accesibilidad gráfica (y, por lo tanto, 2SAT) son casos especiales.

(2) Matroides. El problema tiene una estructura matroide, lo que permite que funcione un algoritmo codicioso. Ejemplos: coincidencia, árbol de expansión mínimo.

(3) Álgebra lineal. El problema puede reducirse a resolver un sistema lineal, calcular un determinante, calcular valores propios, etc. Podría decirse que la mayoría de los problemas que involucran "cancelaciones milagrosas", incluidos los que pueden resolverse mediante el formalismo de la puerta de enlace de Valiant, también caen bajo el paraguas lineal-algebraico.

(4) Convexidad. El problema puede expresarse como algún tipo de optimización convexa. La programación semidefinida, la programación lineal y los juegos de suma cero son casos especiales comunes (cada vez más).

(5) Prueba de identidad polinómica. El problema puede reducirse a verificar una identidad polinómica, de modo que el Teorema fundamental del álgebra conduzca a un algoritmo aleatorio eficiente, y en algunos casos, como la primalidad, incluso un algoritmo determinista demostrable.

(6) Markov Chain Monte Carlo. El problema puede reducirse al muestreo del resultado de una caminata de mezcla rápida. (Ejemplo: aproximadamente contando combinaciones perfectas).

(7) Algoritmo euclidiano. MCD, fracciones continuas ...

Varios / No es obvio exactamente cómo clasificar: matrimonio estable, factorización polinómica, problema de membresía para grupos de permutación, varios otros problemas en teoría de números y teoría de grupos, problemas de celosía de baja dimensión ...

Mi pregunta es: ¿cuáles son las cosas más importantes que he dejado de lado?

Para aclarar:

• Me doy cuenta de que ninguna lista puede estar completa: cualquiera que sea el número finito de razones que des, alguien podrá encontrar un problema exótico que está en P pero no por ninguna de esas razones. En parte por esa razón, estoy más interesado en ideas que ponen muchos problemas diferentes, aparentemente no relacionados en P o BPP, que en ideas que solo funcionan para un problema.

• También me doy cuenta de que es subjetivo cómo dividir las cosas. Por ejemplo, ¿deberían los matroides ser solo un caso especial de programación dinámica? ¿Es la solvencia por búsqueda profunda primero lo suficientemente importante como para ser su propia razón, separada de la programación dinámica? Además, a menudo el mismo problema puede estar en P por múltiples razones, dependiendo de cómo lo mire: por ejemplo, encontrar un valor propio principal está en P debido al álgebra lineal, pero también porque es un problema de optimización convexo.

En resumen, no espero un "teorema de clasificación", solo una lista que refleje útilmente lo que sabemos actualmente sobre algoritmos eficientes. Y es por eso que lo que más me interesa son las técnicas para poner cosas en P o BPP que tienen una amplia aplicabilidad pero que no encajan en la lista anterior, u otras ideas para mejorar mi primer intento burdo de cumplir mi jactancia con el físico.

Algunas clases de gráficos permiten algoritmos de tiempo polinómico para problemas que son NP-hard para la clase de todos los gráficos. Por ejemplo, para gráficos perfectos, uno puede encontrar un conjunto independiente más grande en tiempo polinómico (gracias a vzn en un comentario por activar mi memoria). A través de la construcción de un producto, esto también permite una explicación unificada de varios CSP aparentemente muy diferentes que son manejables (como aquellos con estructura de árbol que generalmente se resuelven mediante descomposición jerárquica y la restricción All-Different que generalmente se resuelve mediante una coincidencia perfecta).

Se podría argumentar que los gráficos perfectos son "fáciles" porque permiten buenas formulaciones semidefinidas de programación de los problemas en cuestión (y, por lo tanto, caen en álgebra lineal y / o convexidad). Sin embargo, no estoy seguro de que captura completamente lo que está sucediendo.

• András Z. Salamon y Peter G. Jeavons, Restricciones perfectas son manejables , CP 2008, LNCS 5202, 524–528. doi: 10.1007 / 978-3-540-85958-1_35

• Meinolf Sellmann, El politopo de los problemas de satisfacción de restricciones binarias estructuradas en árboles , CPAIOR 2008, LNCS 5015, 367–371. doi: 10.1007 / 978-3-540-68155-7_39

Como señaló Gil Kalai, las propiedades de los gráficos que forman clases menores cerradas se pueden definir mediante un conjunto finito de menores prohibidos (este es el teorema de Robertson-Seymour ). Otro resultado de Robertson y Seymour es que la prueba de la presencia de un menor se puede hacer en tiempo cúbico. Juntos, estos conducen a un algoritmo de tiempo polinómico para decidir propiedades que están cerradas de forma menor.

• Neil Robertson y PD Seymour, Graph Minors. XIII El problema de los caminos disjuntos , Journal of Combinatorial Theory, Serie B 63 (1) 65–110, 1995. doi: 10.1006 / jctb.1995.1006

Un problema con las propiedades de gráfico cerrado menor es que son "pequeñas"; excluir incluso un menor excluye muchos gráficos. Esta es quizás una de las razones por las que la descomposición estructural de Robertson-Seymour funciona: hay pocas gráficas restantes suficientes para que tengan una estructura agradable.

• Serguei Norine, Paul Seymour, Robin Thomas y Paul Wollan, Las familias cerradas menores apropiadas son pequeñas , Journal of Combinatorial Theory, Series B 96 (5) 754–757, 2006. doi: 10.1016 / j.jctb.2006.01.006 ( preimpresión )

Un intento de ir más allá de las clases menores cerradas es a través de clases definidas por subgrafos prohibidos o subgrafos inducidos prohibidos.

Las propiedades del gráfico definidas por un conjunto finito de subgrafos prohibidos o subgrafos inducidos son decidibles en tiempo polinomial, al examinar todos los subgrafos posibles.

$F$$F$$F$$F$

$F$

$F$$F$$F$$F$

• Maria Chudnovsky y Paul Seymour, Excluyendo subgrafías inducidas , Surveys in Combinatorics 2007, 99–119, Cambridge University Press, ISBN 9780521698238. ( preprint )

$F$$F$$F$

Reducción basada en celosía (algoritmo LLL). Esta es la base para la factorización polinomial de enteros eficiente y algunos algoritmos criptoanalíticos eficientes como la ruptura de generadores lineales congruentes y RSA de bajo grado. En cierto sentido, puede ver el algoritmo euclidiano como un caso especial.

La programación entera de Lenstra en dimensión limitada, el algoritmo Lenstra-Lenstra-Lovasz y los algoritmos posteriores relacionados: el algoritmo de Barvinok para la cantidad de soluciones enteras a un problema de IP en dimensión limitada y el algoritmo P de Kannan para el problema Frobenius / Sylvester se pueden agregar como Una categoría especial. Un problema abierto notable aquí es encontrar un algoritmo P para problemas de orden superior en la Jerarquía de Presburger.

Otra clase de algoritmo P que vale la pena mencionar son los algoritmos P que se dan a los objetos que han demostrado existir mediante pruebas aleatorias. Ejemplos: algoritmos para aplicaciones de Lovasz-Local Lemma; versiones algorítmicas del resultado de discrepancia de Spencer; (de sabor ligeramente diferente) versiones algorítmicas del lema de regularidad Szemeredi.

Existe un gran cuerpo teórico sobre las clases de problemas de satisfacción de restricciones de plantilla fija que tienen algoritmos de tiempo polinómico. Gran parte de este trabajo requiere el dominio del libro de Hobby y MacKenzie , pero afortunadamente para aquellos de nosotros que estamos más interesados ​​en la informática que el álgebra universal, algunas partes de esta teoría ahora se han simplificado lo suficiente como para ser accesibles a una audiencia de TCS.

$\Gamma$$S$$T$$\Gamma$$S$$T$

$\Gamma$$k \ge 3$$k$$\Gamma$$(0,0,\dots,0)$$S$$0$$T$

$\Gamma$$\Gamma$$\Gamma$$\Gamma$; esto significa en la práctica que la clase de problemas contiene todos los subproblemas sucesivamente más simples considerados por un solucionador de restricciones, por lo que el proceso de resolución de restricciones evita generar instancias intermedias "difíciles" mientras resuelve problemas "fáciles".

$\Gamma$$\Gamma$

Los resultados hasta la fecha parecen indicar que debería haber una especie de transformación de potencia general de un espacio de estado de accesibilidad subyacente que pueda convertir tales problemas en problemas con una tupla constante en cada relación, como en el ejemplo anterior. (Esta es mi interpretación personal de la investigación en curso y puede estar completamente equivocada , dependiendo de cómo se desarrolle la búsqueda en curso de un algoritmo para álgebras con términos cíclicos, por lo que me reservo el derecho de retractarse de esto). Se sabe que cuando no hay En tal transformación, el problema es NP-completo. La frontera de la conjetura de la dicotomía actualmente implica cerrar esta brecha; vea la lista de problemas abiertos del Taller de 2011 sobre álgebra y CSP .

En cualquier caso, esto probablemente merece una entrada en la lista de Scott.

Una segunda clase en PTIME permite aplicar técnicas de consistencia local para podar posibles soluciones, hasta que se encuentre una solución o no sea posible. Esta es esencialmente una versión sofisticada de la forma en que la mayoría de las personas resuelve los problemas de Sudoku. Tampoco creo que esta razón aparezca actualmente en la lista de Scott.

$\Gamma$

Finalmente, también hay mucho trabajo emocionante iniciado por Manuel Bodirsky para el caso de dominios infinitos. Algunos de los algoritmos parecen bastante extraños y, en última instancia, pueden dar lugar a más entradas en la lista de Scott.

Veo a Chandra aludido, pero creo que la estructura de una relajación LP (por ejemplo, debido a la unimodularidad total) es una forma generalizada de "estructura" que conduce a la polinomialidad. Representa una gran clase de algoritmos de poli tiempo. Si uno incluye problemas prometedores, también representa una gran clase de algoritmos de aproximación. Las clases más frecuentes de razones que uno encuentra que no se siguen de los LP y / o SDP son la eliminación gaussiana y la programación dinámica. Por supuesto, hay otras como los algoritmos holográficos que no tienen explicaciones simples.