SAT significa el problema de satisfacción booleana.
¿Cuáles son los mejores límites inferiores actuales para el tiempo y la profundidad del circuito para
En otro hilo , Joe Fitzsimons preguntó sobre "los mejores límites inferiores actuales en 3SAT". Me gustaría ir a otro lado: ¿Cuál es el mejor límite superior actual en 3SAT? En otras palabras, ¿cuál es la complejidad temporal del solucionador SAT más eficiente? En particular, ¿es concebible...
¿Qué explicaciones teóricas existen para el éxito práctico de los solucionadores de SAT, y alguien puede dar una descripción y explicación "estilo wikipedia" uniéndolos a todos? Por analogía, el análisis suavizado ( versión arXiv ) para el algoritmo simplex hace un gran trabajo explicando por...
En esta pregunta, una fórmula 3CNF significa una fórmula CNF donde cada cláusula involucra exactamente tres variables distintas . Para una constante 0 < s <1, Gap-3SAT s es el siguiente problema prometedor: Gap-3SAT s Instancia : fórmula φ A 3CNF. Sí, prometo : φ es satisfactoria. Sin...
Decidir si una fórmula booleana cuantificada como ∀ x1∃ x2∀ x3⋯ ∃ xnorteφ ( x1, x2, ... , xnorte) ,∀X1∃X2∀X3⋯∃Xnorteφ(X1,X2,...,Xnorte),\forall x_1 \exists x_2 \forall x_3\cdots \exists x_n \varphi(x_1, x_2,\ldots , x_n), siempre se evalúa como verdadero es un problema clásico completo de PSPACE....
Defina ioioio - SUBEXPSUBEXPSUBEXP como la clase de lenguajes LLL modo que haya un lenguaje L′∈∩ε>0TIME(2nε)L′∈∩ε>0TIME(2nε)L' \in \cap_{\varepsilon > 0} TIME(2^{n^{\varepsilon}}) y para infinitamente nnn , LLL y L′L′L' estén de acuerdo en todos los casos de longitud nnn . (Es decir, esta es...
¿Alguien se atreve a intentar aclarar cuál es la relación de estos campos de estudio o tal vez incluso dar una respuesta más concreta a nivel de problemas? Como cuál incluye cuál asumiendo algunas formulaciones ampliamente aceptadas. Si entendí esto correctamente, cuando pasas de SAT a SMT...
He escuchado que existen argumentos heurísticos en física estadística que arrojan resultados en la teoría de probabilidad para la cual se desconocen o son muy difíciles las pruebas rigurosas. ¿Cuál es un ejemplo de juguete simple de tal fenómeno? Sería bueno si la respuesta asumiera pocos...
Los algoritmos clásicos pueden resolver 3-SAT en tiempo (aleatorizado) o 1.3303 n tiempo (determinista). (Referencia: Mejores límites superiores en SAT )1.3071norte1.3071norte1.3071^n1.3303norte1.3303norte1.3303^n A modo de comparación, el uso del algoritmo de Grover en una computadora cuántica...
La publicación de blog de Scott Aaronson hoy dio una lista de interesantes problemas / tareas abiertas en complejidad. Uno en particular me llamó la atención: Cree una biblioteca pública de instancias 3SAT, con la menor cantidad de variables y cláusulas posibles, que tendrían consecuencias...
Considere el problema 3-SAT en n variables. El número de posibles cláusulas distintas es: do= 2 n × 2 ( n - 1 ) × 2 ( n - 2 ) / 3 ! = 4 n ( n - 1 ) ( n - 2 ) / 3 .C=2n×2(n−1)×2(n−2)/3!=4n(n−1)(n−2)/3.C = 2n \times 2(n-1) \times 2(n -2) / 3! = 4 n(n-1)(n-2)/3 \text. El número de instancias...
¿Qué son las "regiones fáciles" para la satisfacción? En otras palabras, condiciones suficientes para que un solucionador de SAT pueda encontrar una tarea satisfactoria, suponiendo que exista. Un ejemplo es cuando cada cláusula comparte variables con algunas otras cláusulas, debido a la prueba...
A menudo puede encontrar métodos de plano de corte, propagación variable, ramificación y encuadernación, aprendizaje de cláusulas, retroceso inteligente o incluso heurística humana tejida a mano en solucionadores SAT. Sin embargo, durante décadas, los mejores solucionadores de SAT se han basado en...
Mientras lee el artículo "¿Es hora de declarar la victoria en el conteo de la complejidad?" en el blog "La carta perdida de Godel y P = NP" , mencionaron la dicotomía para los CSP. Después de seguir algunos enlaces, buscar en Google y escribir en wikipedia, me encontré con el teorema de Ladner :...
Algunos problemas NP-hard que son exponenciales en gráficos generales son subexponenciales en gráficos planos porque el ancho del árbol es como máximo y son exponenciales en el ancho del árbol.4.9|V(G)|−−−−−−√4.9|V(G)|4.9 \sqrt{|V(G)|} Básicamente, estoy interesado si hay algoritmos...
Para una fórmula 3CNF dejó sea el máximo número de cláusulas satisfechos en cualquier asignación a . Se sabe que Max-3SAT es difícil de aproximar (sujeto a P ≠ NP), es decir, no existe un algoritmo de polytime cuya entrada es una fórmula 3CNF , y cuya salida es el número tal que está dentro de un...
Estoy interesado en la densidad 3 satisfacciones críticas (3-SAT) . Se conjetura que tal existe: si el número de cláusulas 3-SAT generadas al azar es más, es casi seguro que no son satisfactorias. (Aquí es cualquier constante pequeña es el número de variables). Si el número es o menos, es casi...
¿Es posible traducir una fórmula booleana B en una conjunción equivalente de cláusulas Horn? El artículo de Wikipedia sobre HornSAT parece implicar que lo es, pero no he podido perseguir ninguna referencia. Tenga en cuenta que no me refiero a "en tiempo polinómico", sino más bien "en...
Considere el siguiente problema: dada una fórmula CNF y una asignación que satisface esta fórmula, ¿hay otra asignación satisfactoria para esta fórmula? ¿Cuál es la complejidad de este problema? (Seguramente está en NP, pero ¿también es NP-hard?) ¿Qué sucede si no se le asigna la tarea y solo...
Una característica bien conocida de las instancias -SAT es la relación del número de cláusulas m sobre el número de variables n , es decir, el cociente ρ = m / n . Para cada k , hay un valor umbral α st \ para ρ ≪ α , la mayoría de las instancias son satisfactorias y para ρ ≫ α la mayoría de las...