Supongamos que consideramos 3-SAT con variables y cláusulas . Estoy investigando un método que parece tomar tiempo / espacio para resolver cualquier problema SAT que se ajuste a esta descripción, dentro de un error que se puede ajustar a una cantidad arbitraria. Sin embargo, hay una trampa.O ( v 2 + log c )
Este método requiere un conjunto de valores calculados previamente, después de lo cual puede resolver un problema arbitrario de 3-SAT que se ajusta a la descripción anterior. Los valores calculados previamente son un conjunto de tamaño y cada valor ocupa espacio . El verdadero problema es que cada uno de estos valores podría tomar tiempo para calcular. Existe la posibilidad de que pueda encontrar una manera de acelerar estos cálculos.O ( 1 ) O ( 2 v )
Estoy pensando que los límites en sí mismos superan los límites superiores presentados en esta pregunta (para la pequeña ). Entonces me pregunto, ¿hay una manera trivial de alcanzar los límites superiores que describo si permitimos las precomputaciones ?O ( v 2 + log c )
Me gustaría continuar esta investigación y, con suerte, publicar mis resultados si todo funciona, pero primero me gustaría saber si hay una manera trivial de hacerlo tan bien o mejor.
ACTUALIZAR
He estado estudiando problemas relacionados además de investigar este algoritmo. Hice esta pregunta en el sitio de seguridad de TI de StackExchange en relación con el descifrado de contraseñas y SAT, si está interesado. Al menos una de las respuestas refleja esto.
fuente
Respuestas:
Si lo que estás estudiando funcionó, definitivamente no sería trivial.
Implicaría que 3SAT tiene circuitos (no uniformes) de tamaño . Entonces, cada lenguaje en N P (y la jerarquía de tiempo polinomial) tendría circuitos de tamaño cuasi polinomiales (es decir, n O ( log c n ) ).norteO ( logn ) nortePAG norteO ( logCn )
Incluso si tomara tiempo de preprocesamiento para producir una estructura de datos de solo 2 O ( log 2 n ) que luego podría responder correctamente consultas arbitrarias 3SAT de tamaño n en 2 O ( log 2 n ) tiempo aleatorio con alta probabilidad, 3SAT tendrían circuitos de tamaño cuasi polinomial, utilizando la traducción conocida de algoritmos aleatorios a circuitos. Esto no mejoraría los límites de tiempo del algoritmo conocido debido al preprocesamiento, pero aún sería extremadamente interesante como resultado no uniforme.22norte 2O( log2n ) norte 2O (log2n )
¿Qué quiere decir con "dentro de un error que puede ajustarse a una cantidad arbitraria"? ¿El algoritmo es aleatorio?
fuente
No sé si su resultado, si es válido, sería un avance no trivial, pero aquí hay un tipo de problema en el que podría probarlo:
Problema. Arregle una función . Dado y ∈ { 0 , 1 } n , encuentre x ∈ { 0 , 1 } n tal que f ( x ) = y .F: { 0 , 1 }norte→ { 0 , 1 }norte y∈ { 0 , 1 }norte x ∈ { 0 , 1 }norte F( x ) = y
Si puede calcularse eficientemente (digamos, por un pequeño circuito), su resultado implica algún tipo de solución a este problema.F
fuente