{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T02:43:57Z","timestamp":1760237037124,"version":"build-2065373602"},"reference-count":16,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2020,2,23]],"date-time":"2020-02-23T00:00:00Z","timestamp":1582416000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["No.61762019,6182051"],"award-info":[{"award-number":["No.61762019,6182051"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>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     ( k , s )    -CNF formula, and give a reduction method that transform from k-SAT to (1,0)-    ( k + 1 , s )    -SAT if there is a (    k + 1 , s    )-CNF formula without a (1,0)-super solution. Here,     ( k , s )    -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)-    ( k , s )    -SAT is a problem to decide whether a     ( k , s )    -CNF formula has a (1,0)-super solution. We prove that for     k &gt; 3    , if there exists a     ( k , s )    -CNF formula without a (1,0)-super solution, (1,0)-    ( k , s )    -SAT is NP-complete. We show that for     k &gt; 3    , there is a critical function     \u03c6 ( k )     such that every     ( k , s )    -CNF formula has a (1,0)-super solution for     s \u2264 \u03c6 ( k )     and (1,0)-    ( k , s )    -SAT is NP-complete for     s &gt; \u03c6 ( k )    . We further show some properties of the critical function     \u03c6 ( k )    .<\/jats:p>","DOI":"10.3390\/e22020253","type":"journal-article","created":{"date-parts":[[2020,2,24]],"date-time":"2020-02-24T03:33:43Z","timestamp":1582515223000},"page":"253","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["(1,0)-Super Solutions of (k,s)-CNF Formula"],"prefix":"10.3390","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6605-2370","authenticated-orcid":false,"given":"Zufeng","family":"Fu","sequence":"first","affiliation":[{"name":"College of Computer Science and Technology, Guizhou University, Guiyang 550025, China"},{"name":"Dep. of Electronics and Information Engineering, Anshun University, Anshun 561000, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daoyun","family":"Xu","sequence":"additional","affiliation":[{"name":"College of Computer Science and Technology, Guizhou University, Guiyang 550025, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yongping","family":"Wang","sequence":"additional","affiliation":[{"name":"College of Computer Science and Technology, Guizhou University, Guiyang 550025, China"},{"name":"School of Mathematics and Statistics, Guizhou University of Finance and Economics, Guiyang 550025, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,2,23]]},"reference":[{"key":"ref_1","unstructured":"Weigel, R., and Bliek, C. (1998, January 23\u201328). On reformulation of constraint satisfaction problems. Proceedings of the 13th European Conference on Artificial Intelligence (ECAI98), Brighton, UK."},{"key":"ref_2","unstructured":"Ginsberg, M., Parkes, A., and Roy, A. (1998, January 26\u201330). Supermodels and robustness. Proceedings of the 15th National Conference on Artificial Intelligence (AAAI 98), Madison, WI, USA."},{"key":"ref_3","first-page":"500","article-title":"Branching constraint satisfaction problems for solutions robust under likely changes","volume":"1894","author":"Fowler","year":"2000","journal-title":"Princ. Pract. Constr. Program."},{"key":"ref_4","first-page":"157","article-title":"Super solutions in constraint programming","volume":"3011","author":"Hebrard","year":"2004","journal-title":"Integr. AI OR Tech. Constr. Program. Comb. Optim. Probl."},{"key":"ref_5","unstructured":"Hebrard, E., Hnich, B., and Walsh, T. (2004, January 22\u201327). Robust solutions for constraint satisfaction and optimization. Proceedings of the 16th European Conference on Artificial Intelligence, Valencia, Spain."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1007\/11402763_14","article-title":"Super Solutions for Combinatorial Auctions","volume":"3419","author":"Holland","year":"2004","journal-title":"Recent Adv. Constr."},{"key":"ref_7","first-page":"848","article-title":"Improved algorithm for finding (a,b)-super solutions","volume":"3709","author":"Hebrard","year":"2005","journal-title":"Princ. Pract. Constr. Program."},{"key":"ref_8","unstructured":"Holland, A., and O\u2018Sullivan, B. (2005, January 9\u201313). Weighted Super Solutions for Constraint Programs. Proceedings of the Twentieth National Conference on Artificial Intelligence & the Seventeenth Innovative Applications of Artificial Intelligence Conference, Pittsburgh, PA, USA."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1016\/j.tcs.2016.04.041","article-title":"A probabilistic study of generalized solution concepts in satisfiability testing and constraint programming","volume":"657","author":"Zhang","year":"2016","journal-title":"Theor. Comput. Sci."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1142\/S0129054119500035","article-title":"On the Lower Bounds of (1,0)-Super Solutions for Random k-SAT","volume":"30","author":"Zhou","year":"2019","journal-title":"Int. J. Found. Comput. Sci."},{"key":"ref_11","first-page":"203","article-title":"One more occurrence of variables makes satisfiability jump from trivial to NP-complete","volume":"22","author":"Tuza","year":"1993","journal-title":"Acta Inf."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1016\/j.tcs.2005.02.004","article-title":"Computing unsatisfiable k-SAT instances with few occurrences per variable","volume":"337","author":"Hoory","year":"2005","journal-title":"Theor. Comput. Sci."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1016\/S0304-3975(00)00036-0","article-title":"DNF tautologies with a limited number of occurrences of every variable","volume":"238","author":"Sgall","year":"2000","journal-title":"Theor. Comput. Sci."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"664","DOI":"10.1145\/2975386","article-title":"The Local Lemma is asymptotically tight for SAT","volume":"63","author":"Gebauer","year":"2016","journal-title":"J. ACM"},{"key":"ref_15","first-page":"523","article-title":"A Note on Unsatisfiable k-CNF Formulas with Few Occurrences per Variable","volume":"20","author":"Hoory","year":"2006","journal-title":"Soc. Ind. Appl. Math."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0166-218X(84)90081-7","article-title":"A simplified NP-complete satisfiability problem","volume":"8","author":"Tovey","year":"1984","journal-title":"Discrete Appl. Math."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/22\/2\/253\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T09:01:02Z","timestamp":1760173262000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/22\/2\/253"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,23]]},"references-count":16,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2020,2]]}},"alternative-id":["e22020253"],"URL":"https:\/\/doi.org\/10.3390\/e22020253","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2020,2,23]]}}}