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...

Descripción completa

Detalles Bibliográficos
Autores principales: Fu, Zufeng, Xu, Daoyun, Wang, Yongping
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