A Note On The Natural Range Of Unambiguous-SAT

2023/06/26 by Tayfun Pay, Pay, Tayfun
Business, Management and Accounting · Computer Science · #Computational Complexity (cs.CC) #Constraint Satisfaction and Optimization #F.1.0 #FOS: Computer and information sciences #Formal Methods in Verification #Law, logistics, and international trade

paper · pdf · doi:10.48550/arxiv.2306.14779

openalex publication_date 2023/06/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We discuss the natural range of the Unambiguous-SAT problem with respect to the number of clauses. We prove that for a given Boolean formula in precise conjunctive normal form with n variables, there exist functions f(n) and g(n) such that if the number of clauses is greater than f(n) then the formula does not have a satisfying truth assignment and if the number of clauses is greater than g(n) then the formula either has a unique satisfying truth assignment or no satisfying truth assignment. The interval between functions f(n) and g(n) is the natural range of the Unambiguous-SAT problem. We also provide several counting rules and an algorithm that determine the unsatisfiability of some formulas in polynomial time.

Related

• Bounds for variables with few occurrences in conjunctive normal forms
• A criterion for "easiness" of certain SAT problems
• Counting good truth assignments of random k-SAT formulae
• The Asymptotic Order of the k-SAT Threshold
• Necessary and Sufficient Condition for Satisfiability of a Boolean Formula in CNF and its Implications on P versus NP problem