Heurísticas para la computación cuántica que se ocupan de 3-SAT
Autores: Paulet, Jose J.; LLana, Luis F.; Calvo, Hernán Indíbil; Mezzini, Mauro; Cuartero, Fernando; Pelayo, Fernando L.
Idioma: Inglés
Editor: MDPI
Año: 2023
Acceso abierto
Artículo científico
2023
Heurísticas para la computación cuántica que se ocupan de 3-SAT
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Problema SAT
Problemas NP-completos
Problema 3-SAT
Estrategia incremental
Costos computacionales
Enfoque de computación cuántica
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 21
Citaciones: Sin citaciones
El problema SAT es quizás uno de los problemas NP-completos más famosos. Este documento trata sobre el problema 3-SAT. Seguimos una especie de estrategia incremental para ahorrar costos computacionales en comparación con el enfoque clásico de computación cuántica. Presentamos una heurística que guía esta estrategia, mejorando el rendimiento del esquema incremental puramente aleatorio. Finalmente validamos nuestro enfoque mediante un estudio empírico exhaustivo.
Descripción
El problema SAT es quizás uno de los problemas NP-completos más famosos. Este documento trata sobre el problema 3-SAT. Seguimos una especie de estrategia incremental para ahorrar costos computacionales en comparación con el enfoque clásico de computación cuántica. Presentamos una heurística que guía esta estrategia, mejorando el rendimiento del esquema incremental puramente aleatorio. Finalmente validamos nuestro enfoque mediante un estudio empírico exhaustivo.