(1,0)-Super Solutions of (k,s)-CNF Formula

Area of Science:

• Computer Science
• Discrete Mathematics
• Computational Complexity

Background:

• Super solutions, assignments robust to single variable flips, are crucial for combinatorial optimization and decision problems.
• The study focuses on (1,0)-super solutions within (k,s)-CNF formulas, a specific class of Boolean satisfiability problems.
• Understanding the conditions for super solution existence is key to analyzing the complexity of these problems.

Purpose of the Study:

• To investigate the existence conditions of (1,0)-super solutions for (k,s)-CNF formulas.
• To establish the computational complexity of the (1,0)-super solution problem for (k,s)-CNF formulas.
• To identify a critical function that delineates the boundary between guaranteed super solutions and NP-complete complexity.

Main Methods:

• Introduced a reduction method transforming k-SAT to (1,0)-(k+1,s)-SAT for formulas lacking super solutions.
• Analyzed the complexity of (1,0)-(k,s)-SAT by proving NP-completeness for k > 3 under certain conditions.
• Defined and characterized a critical function, φ(k), related to the variable occurrence bound 's'.

Main Results:

• Established that for k > 3, (1,0)-(k,s)-SAT is NP-complete if a (k,s)-CNF formula without a (1,0)-super solution exists.
• Identified a critical function φ(k) such that for s ≤ φ(k), all (k,s)-CNF formulas possess a (1,0)-super solution.
• Demonstrated that for s > φ(k), the (1,0)-(k,s)-SAT problem becomes NP-complete for k > 3.

Conclusions:

• The existence of (1,0)-super solutions in (k,s)-CNF formulas is critically dependent on the number of occurrences 's' relative to 'k'.
• A phase transition exists, governed by φ(k), where the problem shifts from guaranteed solutions to NP-completeness.
• The findings provide a deeper understanding of the complexity landscape for super solutions in CNF formulas.