Revise mi prueba de que Co-NP!= P

Question

Este es un trabajo de nivel de afición, no mi trabajo. Escribí este extracto para compartir algunas ideas sobre CO-NP.

La idea es elegir una categoría de problema en CO-NP, donde la respuesta correcta es difícil verificar debido a la complejidad del circuito, expresarlo como fórmula SAT de 1 en K y mostrar que también existe un certificado corto, cuya La longitud en los bits es exactamente el doble del número de cláusulas. Puede ser verdadero o falso que todos los problemas de CO-NP tengan un certificado tan corto en este formulario (CO-NP?= NP), pero muestro que, independientemente de eso, el certificado corto para este problema se puede hacer arbitrariamente difíciles de encontrar, debido a la relación intercalada con NP. Básicamente, quiero resaltar una dependencia circular particular entre los oráculos de NP y CO-NP. El argumento para pisar contra CO-NP= P es que ningún TM puede esperar atacar el problema de buscar el certificado corto en tiempo de subexponencial, porque la forma en que defino el problema hace que contenga una cantidad arbitraria de "aleatorio real". Básicamente, es una receta específica construir un problema de CO-NP "monstruo" de un certificado simple.

Ahora tengo muchas preguntas para cualquier persona con un entrenamiento más formal que yo:

• ¿Se ha expresado esta categoría de problema con un nombre diferente?
• es este un extremo sin salida obvio o inexplorado?
• ¿Cómo puedo expresar las mismas ideas, pero más formalmente contra las capacidades de TM?

Answer 1

wtlu está en P.

algoritmo:

• Haz que la fórmula SAT Monotone 1 IN-K agregó una cláusula para cada par de literales (x + ~ x)= 1 y reemplazando ~ x con una nueva variable.
• Elija un gran PRIME P, al menos más grande que el número de cláusulas.
• Convierta la fórmula SAT 1 IN-K en un sistema de ecuaciones lineales Modulo P.Cada cláusula original en el formulario (x, y, z ...)= 1 se convierte en una ecuación (x, y, z ...)= 1 mod p.
• realizar la eliminación gaussiana.
• Si la fórmula era una instancia de WTLU, entonces se encuentra una contradicción antes de que se alcance la forma de escalón de la fila, en forma de una ecuación contradictoria 0= k mod p (con k!= 0).

por qué funciona:

Si hay dos conjuntos de cláusulas que cubren el mismo conjunto de literales, de modo que (C1 + C2 + C3 ...)= X y (C1 '+ C2' + C3 '...)= y y x!= Y, entonces es también el modulo p.Por lo tanto, tampoco es satisfactorio el sistema de ecuaciones Modulo P.

Answer 2

Aquí hay un contrapunto. Una estructura de prueba similar, podría usarse fácilmente para demostrar que XOR-SAT es difícil.

1. Tome una fórmula XOR-SAT insatisfiable con un espacio grande. No puedes resolverlo con un algoritmo similar a una resolución.

2. Ahora existe un breve certificado de insatisfacción, porque XOR-SAT está en P.

3. Si no sabe acerca de la eliminación, combina cláusulas aleatorias juntas hasta que dos cláusulas tienen las mismas variables, una fila es igual a cero y la otra fila es igual a una. Alinearse es un caso especial de adición donde las cláusulas no tienen literales en común.

4. Agregue cláusulas y variables aleatorias a la fórmula XOR-SAT para que sea más difícil hacer las cosas al azar.

Pero en realidad puede hacer la eliminación gaussiana en una cantidad polinomial de tiempo y espacio hasta que dos filas se cancelen entre sí para producir 0= 1.

Para ampliar su argumento y hacer que sea interesante, tendría que al menos mostrar que existe una diferencia fundamental con XOR-SAT, para un comienzo que no hay un proceso similar a la eliminación donde puede sacar las variables una por una. durante el proceso de aislar los 2 conjuntos de cláusulas conflictivas al momento de ignorar la información adicional.