¿Qué problemas de decisión de NP no son auto reducibles?

8

Así que acabamos de aprender sobre la auto-reducibilidad en clase. Mi profesor y nuestro libro de texto no se comprometerían a decir que todos los problemas en NP son auto reducibles, pero no parece haber ningún ejemplo de problemas que no lo sean. Me preguntaba si hay algún ejemplo, o si es solo una situación en la que no se puede probar un negativo fácilmente. Wikipedia solo diceIt is conjectured that the integer factorization problem is not self-reducible.

Google encontró un resultado , que parece indicar que el color del gráfico 4 plano no es auto reducible porque el color LF-k para un gráfico plano se reduce a esa reducción, pero no pude seguir la prueba en este momento.

¿Es este un ejemplo real de una auto-reductibilidad a prueba, y hay otros?

complexity-theory reductions decision-problem np Adam Martin
fuente
@DW No, solo auto reductibilidad. Lee el papel.
Yuval Filmus

Respuestas:

3

De hecho, el documento muestra que la coloración gráfica del gráfico cuatro no es auto reducible en el sentido de Schnorr. Hay varios otros sentidos, bajo algunos de los cuales cada problema en P es auto reducible. Vea el documento de seguimiento de Große, Rothe y Wechsung . No conozco ningún otro resultado de este tipo. Al repasar todos los documentos que citan el documento que menciona (esto se puede hacer usando Google Scholar, por ejemplo), ninguno da tales problemas.

Yuval Filmus
fuente
¡Gracias! Pregunta rápida, ¿era correcta mi comprensión de la parte principal de su prueba o no la seguí correctamente? No hemos hecho mucho con las definiciones reales del lenguaje formal, hemos sido un poco más abstractos, por lo que es difícil confiar en este nivel de detalle. (También voy a esperar un poco para aceptar la respuesta ya que tengo un conocimiento mínimo de la materia y me gustaría esperar para ver si otros intervienen.)
Adam Martin
Si un problema es auto-reducible en el sentido de Schnorr y la versión de decisión puede resolverse en tiempo polinómico, entonces puede encontrar la primera solución lexicográfica en tiempo polinómico. Esto se basa en la definición particular de Schnorr. En este caso, la versión de decisión es muy fácil (la respuesta siempre es SÍ), mientras que la versión lex-first es NP-hard, por lo que el problema no es auto-reducible a menos que P = NP.
Yuval Filmus
¡Gracias! Siento que el único obstáculo que todavía tengo son los diferentes sentidos de auto-reductibilidad. ¿Debo hacer otra pregunta, o es una distinción lo suficientemente menor que puedo pedir aquí / editar mi original? Aprendimos en términos generales que un problema es auto reducible si se le da una solución de existencia polytime, puede crear una solución de búsqueda polytime. ¿Existe una distinción técnica aquí de la que depende este resultado?
Adam Martin
1
Eche un vistazo al artículo de Große et al., Que analiza este punto.
Yuval Filmus