El fenómeno de transición de (1,0)--Regular (, )-SAT
Autores: Fu, Zufeng; Wang, Haiying; Liu, Jinjiang; Zhou, Jincheng; Xu, Daoyun; Pi, Yihai
Idioma: Inglés
Editor: MDPI
Año: 2022
Acceso abierto
Artículo científico
2022
El fenómeno de transición de (1,0)--Regular (, )-SAT
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería Eléctrica y Electrónica
Palabras clave
Fórmula CNF regular
Super solución
Cláusulas
Variables
Algoritmo
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 26
Citaciones: Sin citaciones
Para una fórmula -CNF regular, un problema es determinar si tiene una (1,0)-súper solución. Si es así, se llama (1,0)-SAT regular. Una súper solución (1,0) es una asignación que satisface al menos dos literales de cada cláusula. Cuando se cambia el valor de cualquiera de las variables, la súper solución (1,0) sigue siendo una solución. Las súper soluciones han ganado una atención significativa por su robustez. Aquí, una fórmula -CNF regular es una fórmula CNF especial con cláusulas de tamaño exactamente , en la que cada variable aparece exactamente -veces, y la diferencia de frecuencia absoluta entre ocurrencias positivas y negativas de cada variable es a lo sumo un entero no negativo . Obviamente, la estructura de una fórmula -CNF regular es mucho más regular que otras fórmulas. En este artículo, certificamos que, para , hay una función crítica tal que, si , todas las fórmulas -CNF regulares tienen una (1,0)-súper solución; de lo contrario, (1,0)-SAT regular es NP-completo. Mediante la Lema Local Desigual, obtenemos una condición de existencia de súper soluciones (1,0) y proponemos un algoritmo para encontrar el límite inferior de .
Descripción
Para una fórmula -CNF regular, un problema es determinar si tiene una (1,0)-súper solución. Si es así, se llama (1,0)-SAT regular. Una súper solución (1,0) es una asignación que satisface al menos dos literales de cada cláusula. Cuando se cambia el valor de cualquiera de las variables, la súper solución (1,0) sigue siendo una solución. Las súper soluciones han ganado una atención significativa por su robustez. Aquí, una fórmula -CNF regular es una fórmula CNF especial con cláusulas de tamaño exactamente , en la que cada variable aparece exactamente -veces, y la diferencia de frecuencia absoluta entre ocurrencias positivas y negativas de cada variable es a lo sumo un entero no negativo . Obviamente, la estructura de una fórmula -CNF regular es mucho más regular que otras fórmulas. En este artículo, certificamos que, para , hay una función crítica tal que, si , todas las fórmulas -CNF regulares tienen una (1,0)-súper solución; de lo contrario, (1,0)-SAT regular es NP-completo. Mediante la Lema Local Desigual, obtenemos una condición de existencia de súper soluciones (1,0) y proponemos un algoritmo para encontrar el límite inferior de .