¿De qué se alimentan los teoremas de dicotomía?

10

Es bien sabido que ciertas clases de NP -Problemas Tienes dicotomía teoremas, lo que garantiza que todas las tareas en la clase es o NP -Complete o está en P . El mejor resultado conocido es el teorema de dicotomía de Schaefer , junto con una serie de generalizaciones.

Entiendo que probar estos teoremas de dicotomía no es realmente fácil. Me pregunto si hay una explicación relativamente breve de por qué ciertas clases tienen teoremas de dicotomía, mientras que otras no. ¿Cuál es la estructura del problema esencial que hace posible estos teoremas? ¿O tal vez no existe una estructura tan claramente entendida, sino que es un misterio en cada caso por qué la clase tiene o no un teorema de dicotomía?

cc.complexity-theory np descriptive-complexity Andras Farago
fuente
2
Buena pregunta. Creo que una intuición es que estamos restringiendo los problemas a una clase que tiene descripciones agradables.
Kaveh
55
Esta no es una respuesta, pero quizás señala dónde podría estar (no) una respuesta: si la clase de problemas es lo suficientemente grande como para incluir todo (o incluso solo un subconjunto particular de él), entonces se aplicará el Teorema de Ladner Y no habrá una dicotomía. Entonces, una clase con dicotomía al menos tiene que estar lo suficientemente estructurada para evitar a Ladner ...nortePAG
Joshua Grochow
1
Las dicotomías ocurren cuando el lenguaje es demasiado tosco para hacer distinciones finas.
András Salamon

Respuestas:

2

Para el caso del teorema de la dicotomía de Schaefer, informalmente, el poder expresivo universal de las fórmulas booleanas de CNF construidas a partir de relaciones lógicas no Schaefer está detrás de la dicotomía. Toda relación lógica es definible por dicha fórmula usando un cuantificador existencial. Esto se afirma formalmente en el teorema de expresibilidad de Schaefer (Teorema 2.5).

Mohammad Al-Turkistany
fuente