Cargando…
(1,0)-Super Solutions of (k,s)-CNF Formula
A (1,0)-super solution is a satisfying assignment such that if the value of any one variable is flipped to the opposite value, the new assignment is still a satisfying assignment. Namely, every clause must contain at least two satisfied literals. Because of its robustness, super solutions are concer...
Autores principales: | , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
MDPI
2020
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7516700/ https://www.ncbi.nlm.nih.gov/pubmed/33286027 http://dx.doi.org/10.3390/e22020253 |
_version_ | 1783587061620539392 |
---|---|
author | Fu, Zufeng Xu, Daoyun Wang, Yongping |
author_facet | Fu, Zufeng Xu, Daoyun Wang, Yongping |
author_sort | Fu, Zufeng |
collection | PubMed |
description | A (1,0)-super solution is a satisfying assignment such that if the value of any one variable is flipped to the opposite value, the new assignment is still a satisfying assignment. Namely, every clause must contain at least two satisfied literals. Because of its robustness, super solutions are concerned in combinatorial optimization problems and decision problems. In this paper, we investigate the existence conditions of the (1,0)-super solution of [Formula: see text]-CNF formula, and give a reduction method that transform from k-SAT to (1,0)- [Formula: see text]-SAT if there is a ([Formula: see text])-CNF formula without a (1,0)-super solution. Here, [Formula: see text]-CNF is a subclass of CNF in which each clause has exactly k distinct literals, and each variable occurs at most s times. (1,0)- [Formula: see text]-SAT is a problem to decide whether a [Formula: see text]-CNF formula has a (1,0)-super solution. We prove that for [Formula: see text] , if there exists a [Formula: see text]-CNF formula without a (1,0)-super solution, (1,0)- [Formula: see text]-SAT is NP-complete. We show that for [Formula: see text] , there is a critical function [Formula: see text] such that every [Formula: see text]-CNF formula has a (1,0)-super solution for [Formula: see text] and (1,0)- [Formula: see text]-SAT is NP-complete for [Formula: see text]. We further show some properties of the critical function [Formula: see text]. |
format | Online Article Text |
id | pubmed-7516700 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2020 |
publisher | MDPI |
record_format | MEDLINE/PubMed |
spelling | pubmed-75167002020-11-09 (1,0)-Super Solutions of (k,s)-CNF Formula Fu, Zufeng Xu, Daoyun Wang, Yongping Entropy (Basel) Article A (1,0)-super solution is a satisfying assignment such that if the value of any one variable is flipped to the opposite value, the new assignment is still a satisfying assignment. Namely, every clause must contain at least two satisfied literals. Because of its robustness, super solutions are concerned in combinatorial optimization problems and decision problems. In this paper, we investigate the existence conditions of the (1,0)-super solution of [Formula: see text]-CNF formula, and give a reduction method that transform from k-SAT to (1,0)- [Formula: see text]-SAT if there is a ([Formula: see text])-CNF formula without a (1,0)-super solution. Here, [Formula: see text]-CNF is a subclass of CNF in which each clause has exactly k distinct literals, and each variable occurs at most s times. (1,0)- [Formula: see text]-SAT is a problem to decide whether a [Formula: see text]-CNF formula has a (1,0)-super solution. We prove that for [Formula: see text] , if there exists a [Formula: see text]-CNF formula without a (1,0)-super solution, (1,0)- [Formula: see text]-SAT is NP-complete. We show that for [Formula: see text] , there is a critical function [Formula: see text] such that every [Formula: see text]-CNF formula has a (1,0)-super solution for [Formula: see text] and (1,0)- [Formula: see text]-SAT is NP-complete for [Formula: see text]. We further show some properties of the critical function [Formula: see text]. MDPI 2020-02-23 /pmc/articles/PMC7516700/ /pubmed/33286027 http://dx.doi.org/10.3390/e22020253 Text en © 2020 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/). |
spellingShingle | Article Fu, Zufeng Xu, Daoyun Wang, Yongping (1,0)-Super Solutions of (k,s)-CNF Formula |
title | (1,0)-Super Solutions of (k,s)-CNF Formula |
title_full | (1,0)-Super Solutions of (k,s)-CNF Formula |
title_fullStr | (1,0)-Super Solutions of (k,s)-CNF Formula |
title_full_unstemmed | (1,0)-Super Solutions of (k,s)-CNF Formula |
title_short | (1,0)-Super Solutions of (k,s)-CNF Formula |
title_sort | (1,0)-super solutions of (k,s)-cnf formula |
topic | Article |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7516700/ https://www.ncbi.nlm.nih.gov/pubmed/33286027 http://dx.doi.org/10.3390/e22020253 |
work_keys_str_mv | AT fuzufeng 10supersolutionsofkscnfformula AT xudaoyun 10supersolutionsofkscnfformula AT wangyongping 10supersolutionsofkscnfformula |