logo móvil
Contáctanos

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

Descargar PDF

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


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 .

Otros recursos que podrían interesarte

Temas Virtualpro