Estoy seguro de que alguien ha pensado en esto antes o lo descartó de inmediato, pero ¿por qué la teoría de la dicotomía de Schaefer junto con el teorema de Mahaney sobre conjuntos dispersos no implican P = NP?
Aquí está mi razonamiento: crear un lenguaje que sea igual a SAT intersectado por un conjunto escaso infinitamente decidible. Entonces también debe ser escaso. Como no es trivial, afín, 2 sat o Horn sat, según el teorema de Shaefer, debe ser NP completo. Pero luego tenemos un conjunto completo de NP escaso, así que según el teorema de Mahaney, P = NP.
¿Dónde me estoy equivocando aquí? Sospecho que estoy malentendido / aplicando mal el teorema de Shaefer, pero no veo por qué.
Respuestas:
fuente