Problemas que son NP completos bajo reducciones aleatorias o P / poli.

En esta pregunta , parece que hemos identificado un problema natural que es NP completo bajo reducciones aleatorias, pero posiblemente no bajo reducciones deterministas (aunque esto depende de qué suposiciones no comprobadas en la teoría de números sean verdaderas). ¿Hay algún otro problema conocido? ¿Hay algún problema natural que sea NP completo bajo las reducciones de P / poli, pero no se sabe que está bajo las reducciones de P?

cc.complexity-theory np-hardness big-list randomness reductions Peter Shor
fuente

SAT único es

duro bajo reducción aleatoria.

N P

$NP$

Mohammad Al-Turkistany

No veo por qué Unique SAT no debería contar como una respuesta (aunque eso no era exactamente lo que estaba buscando). Creo que cuenta como un problema natural.

Peter Shor

Solo quería agregar que el problema de vector más corto para LLL bajo la norma

para reducciones aleatorias (papel de Ajtai aquí ) es NP-Hard. Hasta donde sé, no se sabe que sea NP-Hard bajo reducciones no aleatorias, por lo que no cumple con sus criterios, pero pensé que debería mencionarse de todos modos.

L_{2}

$L_2$

usuario834

@Joshua: En algunos problemas NP-completos relacionados con rompecabezas (como Sudoku), la singularidad de una solución es una suposición natural. Supongo que esto hace que el SAT con a lo sumo una solución (prefiero llamarlo SAT inequívoco) sea más natural de lo que parece.

Tsuyoshi Ito

¿Por qué todos escriben respuestas en los comentarios? : P

Hsien-Chih Chang 張顯之

Respuestas:

Bajo reducción aleatoria con probabilidad (conocido también comoreducibilidad , sobre la discusión de las reducciones aleatorias, consulte "Sobre la satisfacción única y las reducciones aleatorias") $\frac{1}{2}$ $\gamma$

Divisibilidad lineal
Ecuaciones binarias cuadráticas de diofantina

son NP completos, pero no se sabe lo mismo para las reducciones deterministas (hasta donde yo sé, para una discusión un poco desactualizada de esta situación, ver aquí ). reducibilidad se introdujo en el documento " Reducibilidad, aleatoriedad e intractibilidad $\gamma$ " de Leonard Adleman y Kenneth Manders (también se propusieron pruebas de los problemas anteriores).

Hay otros ejemplos de este tipo en " Un catálogo de clases de complejidad ", pero no he comprobado lo que se sabe sobre su integridad de NP bajo reducciones deterministas.

Oleksandr Bondarenko
fuente

Como sugirió Peter, convertí mi comentario en una respuesta.

Valiant-Vazirani teorema afirma que si Unique SAT entonces . Para probar su teorema, demostraron que el problema prometedor Unique SAT es duro bajo reducciones aleatorias. $\in P$ $NP=RP$ $NP$

[1] Valiant, Leslie; Vazirani, Vijay. "NP es tan fácil como detectar soluciones únicas", Theoretical Computer Science, 47: 85–93

Mohammad Al-Turkistany
fuente

Como sugirió Peter, convertí mi comentario en una respuesta:

$L_2$ $NP$

usuario834
fuente