¿Una categoría de problemas NP-completos?

28

¿Tiene sentido considerar una categoría de todos los problemas de NP completo, con morfismos como reducciones de poli-tiempo entre diferentes instancias? ¿Alguien ha publicado alguna vez un artículo sobre esto, y si es así, dónde puedo encontrarlo?

Paul Allen Grubbs
fuente
1
No estoy seguro de por qué quiere la categoría de solo problemas de NP completo, pero la categoría de todos los problemas de decisión con alguna noción fija de reducciones (como reducciones de tiempo múltiple polinomial) como morfismos parece un objeto razonable a considerar. Sin embargo, no conozco la teoría de la categoría y no puedo adivinar si es interesante o no.
Tsuyoshi Ito
1
No estoy seguro de que esto ayude, pero lo intentaré: sobre isomorfismos y densidad de NP y otros conjuntos completos . Ver también la versión del diario . Ver también el artículo de Mahaney .
MS Dousti
2
Solo quería dar más detalles sobre el comentario de Sadeq. Se ha estudiado el isomorfismo entre los problemas completos de y se ha realizado una gran cantidad de trabajo para probar / refutar la conjetura de Berman-Hartmanis (que establece que todos los problemas completos de N P son "isomórficos" bajo reducciones de tiempo polinomial muchas) . Aquí hay una encuesta realizada por Manindra Agrawal sobre la conjetura del isomorfismo ( cse.iitk.ac.in/users/manindra/survey/Isomorphism-Conjecture.pdf ). NPNP
Ramprasad
1
@ Tsuyoshi: incluso la categoría de problemas de NPC con reducciones de Karp podría ser potencialmente interesante; si realmente entendiéramos incluso esa categoría, tendríamos una mejor comprensión de la complejidad en general (ya que probablemente implicaría una mejor comprensión de Karp). reducciones, por lo tanto del tiempo polinomial). OTOH, no estoy seguro de que verlo como una categoría proporcionará una manera de ayudar a la comprensión. He pensado en este tema en el pasado, y busqué referencias que vean la complejidad de esta manera, y no encontré ninguna. ¡Espero que alguien lo haga!
Joshua Grochow
3
Yo segundo Joshua. Lo importante es no poder definir una categoría, lo importante es encontrar una estructura categórica interesante en ella. Hay estructuras interesantes en el caso de computabilidad, pero por complejidad no lo sé. Andrej debería saberlo mejor y con suerte revisará esta pregunta.
Kaveh

Respuestas:

21

El área que desea observar se llama "teoría de la complejidad implícita". Un puñado de nombres aleatorios e incompletos para Google son Martin Hofmann, Patrick Baillot, Ugo Dal Lago, Simona Ronchi Della Rocca y Kazushige Terui.

La técnica básica es relacionar las clases de complejidad con los subsistemas de lógica lineal (las llamadas "lógicas lineales ligeras"), con la idea de que la eliminación de cortes para el sistema lógico debe completarse para la clase de complejidad dada (como LOGSPACE, TIEMPO, etc). Luego, a través de Curry-Howard, obtienes un lenguaje de programación en el que precisamente los programas en la clase dada son expresables. Como es de esperar de la mención de la lógica lineal, todos estos sistemas dan lugar a categorías cerradas monoidales de varios sabores, lo que te deja con una caracterización puramente algebraica e independiente de la máquina de varias clases de complejidad.

Una de las cosas que hacen que esta área sea interesante es que ni la complejidad tradicional ni los métodos lógicos / PL son completamente apropiados.

Dado que las categorías involucradas generalmente tienen una estructura cerrada, los métodos combinatorios favorecidos por los teóricos de la complejidad a menudo se rompen (ya que los programas de orden superior tienden a resistir las caracterizaciones combinatorias). Un ejemplo típico de esto es el fracaso de los métodos sintácticos para manejar la equivalencia contextual. Del mismo modo, los métodos de semántica también tienen problemas, ya que a menudo son demasiado extensivos (ya que tradicionalmente los semánticos han querido ocultar la estructura interna de las funciones). El ejemplo más simple que conozco aquí es el cierre de LOGSPACE bajo composición: esto es AFAIK solo posible debido a la combinación de cola de milano y la recalculación selectiva, y no puede tratar los problemas como cajas negras puras.

Es probable que también desee familiarizarse con la semántica del juego y la Geometría de interacción de Girard (y su precursor, las estructuras de datos concretas de Kahn-Plotkin-Berry) si se adentra seriamente en esta área, las ideas de representaciones de transferencia de fichas de niveles superiores. Los cálculos de pedidos utilizados en este trabajo proporcionan muchas de las intuiciones para ICC.

Como he señalado el papel central de las categorías monoidales en este trabajo, es posible que se pregunte razonablemente sobre las conexiones con el GCT de Mulmuley. Desafortunadamente, no puedo ayudarte aquí, ya que simplemente no sé lo suficiente. Sin embargo, Paul-André Melliès podría ser una buena persona para preguntar.

Neel Krishnaswami
fuente
16

Es posible clasificar muchas cosas, pero eso no significa necesariamente que sean categorías interesantes. Entonces, la respuesta a "¿tiene sentido" depende de cómo te refieres.

En cuanto a predecir si sería interesante, suponga alguna definición apropiada de reducciones de modo que forme una categoría, NPC. Las preguntas de categoría teóricamente interesantes serían cosas como preguntar si la APN tiene varios límites o límites (por ejemplo, productos, coproductos, retrocesos, rechazos, ...). Por lo tanto, antes de comenzar el trabajo de formalizar las cosas, sería bueno sentarse y pensar en lo que significarían estos co / límites y si sería interesante saber ese significado. Si suponemos que el NPC tiene retrocesos, ¿significa algo especial la capacidad de tomar el retroceso de dos reducciones? Preguntas como estas parecen ser interesantes si quisiéramos averiguar cuáles son los problemas "atómicos" de NP completo, o cómo se pueden combinar múltiples problemas de NP completo (o sus reducciones);

Algunos de los siguientes en preguntas serían cosas como: ¿NPC tiene alguna subcategoría interesante? ¿Es NPC una subcategoría de alguna categoría más grande interesante? Ya sabemos bastante sobre cómo los problemas de NP completo se relacionan con otras clases de problemas, por lo que la respuesta presunta a estas preguntas es "por supuesto". Pero para aclararlo, ¿qué ofrece considerar estas relaciones desde una perspectiva teórica de categoría que otras perspectivas no ofrecen? Una cosa que CT puede ofrecer es la cuestión de si hay adjuntos no triviales entre NPC y otra categoría. Por supuesto, los adjuntos son principalmente interesantes cuando las categorías detrás de ellos son interesantes, por lo que si NPC no tiene mucha estructura especial, entonces conocer los adjuntos de NPC realmente no ofrecerá mucho.

En cuanto a referencias particulares, no sé de ninguna mano, pero los enlaces en los comentarios de Sadeq, Ramprasad, Kaveh deberían proporcionar un lugar para comenzar.

wren romano
fuente