The Relationship Between Unique Satisfiability And Np-Completeness

The SAT Problem and Its Variants

The boolean satisfiability problem (SAT) aims to determine if there exists an interpretation that satisfies a given boolean formula. In formal terms, we are given a boolean formula Ï† with n variables x1, x2, …, xn that can take on true or false values. The goal is to find an assignment of true/false values to the variables that makes the entire formula Ï† evaluate to true, or determine no such assignment exists.

Unique SAT is a restricted version of SAT where the formula Ï† must have at most one satisfying assignment. This contrasts with general SAT where there may exist multiple satisfying interpretations. For example, the formula (x1 OR x2) has two satisfying assignments: {x1 = true, x2 = false} and {x1 = false, x2 = true}. If instead we have the formula (x1 XOR x2), there is only one satisfying solution where x1 and x2 take on opposite truth values.

As an example SAT formula, consider Ï† = (x1 OR x2) AND (NOT x1 OR x3). There are three satisfying solutions:
{x1 = false, x2 = true, x3 = true}
{x1 = true, x2 = true, x3 = false}
{x1 = true, x2 = false, x3 = true}

Table of Contents

For the unique SAT case, the formula Ïˆ = (x1 XOR x2) AND (x1 XOR x3) has only one satisfying assignment: {x1 = true, x2 = false, x3 = true}. We will see that restricting SAT to have unique solutions intrinsically ties it to the concept of NP-completeness.

Unique SAT at the Heart of NP-Completeness

NP-completeness theory deals with the computational complexity of decision problems with yes/no solutions. The Cook-Levin theorem established SAT as the first NP-complete problem – any problem in NP can be efficiently reduced to SAT. Importantly, this implies if we can solve SAT in polynomial time, we can do the same for any problem in NP.

The NP-completeness of general SAT stems from transformations that produce SAT instances with a large number of satisfying assignments. However, adding uniqueness constraints facilitates connections to other NP-complete problems. In particular, by controlling SAT assignments we can encode solutions to problems like Hamiltonian cycles and vertex cover.

We now sketch a proof that unique SAT is NP-complete. First, it is clear unique SAT is in NP since we can verify in polynomial time if a given variable assignment satisfies Ïˆ with only one solution. To prove NP-hardness, we reduce an arbitrary SAT formula Ï† to a unique SAT formula Ïˆ that has a single satisfying assignment iff Ï† is satisfiable. The key ideas are:
1) Introduce additional variables to remove duplicate assignments
2) Add constraints ruling out all cases except one solution.

While the full proof is more intricate, this demonstrates how enforced uniqueness allows SAT formulations of other NP problems.

Algorithms for Solving Unique SAT

A basic approach for solving unique SAT is to use backtracking search. We recursively assign truth values to variables and propagate constraints to prune portions of the search space. We can further optimize this by leveraging properties of unique solutions.

One heuristic is to guess variable assignments that minimize the chance of finding multiple solutions. For example, setting a variable that appears in many clauses can quickly detect inconsistencies. Random restarts and intelligent backtracking schemes also help avoid wasteful exploration of fruitless branches.

As an example, here is some C++ code for a simple unique SAT solver using these ideas:

bool solve(Formula F) {

  if (F has empty clause)
    return false; 
  
  if (F fully assigned) 
    return verify_unique(F);  

  Var x = next_var_to_assign();
  
  if (solve(F with x = TRUE))
     return true; 
  
  if (solve(F with x = FALSE))  
     return true;

  return false;
}

There exist many refinements like conflict-driven clause learning that empower modern SAT solvers to tackle extremely large formulae.

Open Questions and Future Directions

While we have focused on standard Boolean variables, there are avenues for exploring alternate SAT mappings. For example, we can consider satisfiability modulo theories (SMT) where atomic propositions include real linear constraints and integer equations. Instead of true/false assignments, solutions involve finding values from relevant domains that satisfy a logical formula.

On the applications side, the NP-completeness of unique SAT enables one-way trapdoor functions useful in cryptography. By hiding the unique solution, we can generate puzzles that are hard to solve but easy to verify. This also connects to hash functions and blockchain technologies reliant on asymmetric proof-of-work protocols.

Conclusion: The Intrinsic Difficulty of Unique Satisfiability

We have shown deep links between the unique satisfiability problem and NP-completeness – unique solutions enable SAT formulations of other difficult problems. While catering constraints to enable a single satisfying assignment, this core complexity remains firmly resistant to efficient solving techniques.

The quest for polynomial-time algorithms remains a holy grail of computer science. By codifying the hardness of uniqueness constraints, we appreciate the difficult road ahead while illuminating directions that spur future progress.