Pregunta sobre el P contra problema de NP

Question

Parece ser aceptado creencia basada en décadas de experiencia que ingenuo algoritmos no son adecuada para resolver problemas del tipo NP-completo de los problemas en una cantidad de tiempo razonable. Incluso aquellos que creen que P = NP parecen estar buscando un algoritmo con una muy inteligente representación, hasta ahora sin éxito.

Puede que las observaciones por encima de formalizarse? Vamos a usar la plena y sin restricciones de una Camarilla problema como un ejemplo. Supongamos que se pudiera demostrar que no inteligente representación existe para el problema de la Clique. Es decir, suponga que podría ser probado para cada algoritmo que sea:

1. el algoritmo es correcto y utiliza una representación interna tal que no hay dos distintos entrada de camarillas, conduce a la misma representación interna, o
2. el algoritmo es correcto.

Sería una pena el resultado? Lo importante sería? O es malo?

Hay ya una prueba de que la CAMARILLA o el SAT, por ejemplo, no pueden ser resueltos en el polinomio de tiempo mediante la realización de operaciones en camarillas o expresiones Booleanas, respectivamente?

Las referencias con su respuesta sería de gran ayuda. Gracias

Answer 1

Pregunta:

supongo que podría ser probado para cada algoritmo que sea:

1. el algoritmo es correcto y utiliza una representación interna de tales que no hay dos distintos entrada de camarillas conducir a los mismos internos la representación, o
2. el algoritmo es correcto.

Sería una pena el resultado? ¿ importante sería? O es malo?

Lo que está mal. Siempre se puede tomar un algoritmo correcto para la camarilla y agregar un paso de preprocesamiento que elimina los bordes, que claramente no son en ningún máxima de la camarilla. Este seguirá siendo un algoritmo correcto para la camarilla, y obviamente no satisface (1) o (2).

Answer 2

Hay formal nociones de Pruebas Naturales (Razborov-Rudich) y de las pruebas que relativizar (Baker-Gill-Solovay) y ambos son conocidos por no trabajo para mostrar $P \neq NP$ . Usted está preguntando acerca de relativizable algoritmos, debido a que cualquier algoritmo que funciona sólo en la "cáscara" o "superficial interfaz" de SAT o Max-Camarilla probablemente va a funcionar igualmente en entornos donde las máquinas de Turing son conectados a un oráculo, y P=NP puede ser true o false dependiendo de oracle. Al menos para los oráculos con P < NP el algoritmo no se ejecutará en el polinomio de tiempo, y creo que esto es cierto para el azar oráculos, por lo que las posibilidades para los SAT solvers que utilizan sólo visible externamente características para trabajar en el polinomio de tiempo son bastante limitadas.

También hay problemas en los que los algoritmos que utilizan sólo la interfaz externa está superado por los algoritmos que desarmar la representación interna de los datos. Por ejemplo, la clasificación por comparaciones requiere de $n \log n$ operaciones en comparación con el lineal de tiempo base de la clasificación.