¿Candidato natural contra la conjetura del isomorfismo?

La famosa conjetura del isomorfismo de Berman y Hartmanis dice que todos los lenguajes completos son polinomiales en tiempo isomorfo (p-isomorfo) entre sí. El significado clave de la conjetura es que implica . Fue publicado en 1977, y una evidencia de apoyo fue que todos los completos de conocidos en ese momento eran de hecho p-isomórficos. De hecho, todos eran acolchados , lo cual es una propiedad agradable y natural e implica p-isomorfismo de una manera no trivial. $NP$ $P\neq NP$ $NP$

Desde entonces, la confianza en la conjetura se deterioró, debido a que se han descubierto los idiomas completos candidatos de que probablemente no sean p-isomórficos para , aunque el problema aún está abierto. Hasta donde yo sé, sin embargo, ninguno de estos candidatos representa problemas naturales ; se construyen a través de la diagonalización con el propósito de refutar la conjetura del isomorfismo. $NP$ $SAT$

¿Sigue siendo cierto, después de casi cuatro décadas, que todos los completos de naturales conocidos son p-isomorfos al ? O, ¿hay algún candidato natural conjeturado en contrario? $NP$ $SAT$

cc.complexity-theory complexity-classes p-vs-np np-complete Andras Farago
fuente

Me abstendré de votar negativamente, pero personalmente estoy en contra de todas las preguntas que piden la existencia de algo "natural" sin definir qué es natural. No estoy diciendo que estoy en contra de todas las nociones "difusas", pero creo que lo natural es demasiado amplio y algunas propiedades más concretas deseables / indeseables deberían especificarse más a fondo.

Sasho Nikolov

+1 Buena pregunta. @SashoNikolov, antes de la invención de las máquinas de Turing, la definición formal de algoritmos, la noción intuitiva era conocida y se ha utilizado durante miles de años. La falta de una definición formal del problema natural no debería disuadirnos de usarlo informalmente. El problema natural es un concepto que lo sabes cuando lo ves.

Mohammad Al-Turkistany

Estoy de acuerdo con Mohammad en que normalmente conoces un problema natural cuando lo ves. Sin embargo, "natural" también depende del contexto, y en algunos contextos hay una noción más clara, o tal vez solo un conjunto más grande y bien acordado de ejemplos claramente naturales, que en otros. Creo que este caso particular (NP-completo) problemas cae en la clase anterior. Por ejemplo, la aplicación de una función unidireccional a SAT para obtener otro problema de NP completo (la idea básica detrás de algunos de los candidatos que violan a Berman-Hartmanis) claramente resulta en un problema "antinatural".

Joshua Grochow

El problema con 'natural' en la práctica aquí en teoría. SE es que la pregunta generalmente resulta en una tormenta 'no hay verdadero escocés' donde cada respuesta que no le gusta al OP se considera "antinatural" para un conjunto en evolución / cambio de razones

Suresh Venkat

@Sasho, personalmente leí "natural" sin más aclaraciones como significado: no es un problema artificialmente inventado responder la pregunta (o similares), las personas están interesadas en el problema de forma independiente.

Kaveh

Respuestas:

Creo que la respuesta es sí, incluso hoy no hay ningún problema natural conocido que sea candidato para violar la Conjetura del Isomorfismo.

La razón principal es que los problemas típicamente naturales de NP completo son fácilmente acolchados, lo que Berman y Hartmanis demostraron que es suficiente para ser isomorfo al SAT. Para problemas naturales relacionados con gráficos, esto generalmente implica agregar vértices adicionales que, por ejemplo, están desconectados del gráfico o conectados de una manera muy particular (pero generalmente obvia). Para la versión de decisión de los problemas de optimización, generalmente implica agregar nuevas variables ficticias sin restricciones. Y así.

Joshua Grochow
fuente

Sí, en la mayoría de los problemas de gráficos, el relleno es fácil. Pero esto no siempre puede sostenerse. Un ejemplo: ¿es cierto que el gráfico está libre de triángulos y tiene un camino hamiltoniano? Aquí, para preservar la propiedad, un nuevo vértice de relleno debe conectarse a algún antiguo (para permitir la ruta Hamiltoniana), debe conectarse a un conjunto independiente (para evitar crear un triángulo), y este conjunto independiente debe ser tal que contenga un punto final de al menos un camino hamiltoniano (para hacerlo extensible al nuevo vértice). No me parece obvio cómo lograr esto. Por supuesto, uno podría encontrar otra forma de rellenar, no estoy seguro.

Andras Farago

Para Hamiltonian Path, vea el documento original de Berman-Hartmanis (Thm 7 (5) en la versión STOC, Thm 8 (5) en la versión de la revista: dx.doi.org/10.1137/0206023 ). Su construcción no introduce ningún nuevo 3 ciclos dirigidos. Si desea evitar incluso triángulos no dirigidos , puede subdividir algunos de los bordes en su construcción con nuevos vértices. También puede encontrar interesante su artículo de seguimiento, en el que muestran que las ecuaciones cuadráticas de diofantina son p-iso para SAT: dx.doi.org/10.1016/0022-0000(78)90027-2

Joshua Grochow

@JoshuaGrochow ¿Hay algún ejemplo candidato no natural contra la conjetura de BH?

T ....

@Turbo: Sí, los conjuntos k-creativos ("conjuntos completos encriptados") de Joseph and Young 1985: dx.doi.org/10.1016/0304-3975(85)90140-9

Joshua Grochow