El teorema de PCP que no hay algoritmo de tiempo polinómico para MAX 3SAT para encontrar una asignación satisfacer cláusulas de una fórmula 3SAT satisfiable a menos que P = N P .
Existe un algoritmo de tiempo polinomial que satisface trivial de las cláusulas. Así que, ¿Podemos hacer algo mejor que 7 / 8 + ε si permitimos que los algoritmos de super-polinómicas? ¿Qué proporciones de aproximación podemos lograr con algoritmos de tiempo cuasi-polinomiales ( n O ( log n ) ) o con algoritmos de tiempo sub-exponenciales ( 2 o ( n ) )? Estoy buscando referencias a cualquiera de estos algoritmos.
fuente
Para reafirmar de alguna manera lo que Ryan Williams escribió en su último párrafo:
fuente