Transcript Phase Transitions of PP-Complete Satisfiability Problems

Phase Transitions
of
PP-Complete
Satisfiability Problems
D. Bailey, V. Dalmau, Ph.G. Kolaitis
Computer Science Department
UC Santa Cruz
Phase Transitions
A phase transition is an abrupt change in
the behavior of a property of a “system”.
 Extensive study of phase transitions in
physics (statistical mechanics).
 Extensive study of phase transitions in the
behavior of asymptotic probabilities of NPcomplete problems during the past decade.

Motivation and Goals
Understand the “structure” of NP-complete
complete problems.
 Relate phase transitions to the average-case
performance of particular algorithms for
NP-complete problems.
 Ultimately, understand the average-case
complexity of NP-complete problems.

Boolean Formulas
Literal: x,  x, with x a Boolean variable
 Clause: disjunction of literals
 k-Clause: disjunction of k literals
 k-CNF formula: conjunction of k-clauses
 Example: 3-CNF formula
(x   y  z )  ( z  w   u)  (x  y  z)
 ( x   y   u)

NP-Completeness of kSAT
kSAT is the following decision problem:
given a k-CNF formula , is it satisfiable?
(i.e., is there an assignment of values 0/1 to
the variables, so that  evaluates to 1).
 Theorem: (S. Cook – 1971)
kSAT is NP-complete, for every k  3.
In particular, 3SAT is NP-complete.

Random Boolean Formulas




Fk(n,r): space of all k-CNF formulas with n
variables and rn clauses.
Random k-CNF formula: rn clauses of length k
are picked independently & with replacement.
pr(k,n,r): probability that a random k-CNF
formula is satisfiable.
Fixed clauses-to-variables ratio model introduced
and studied first by Franco et al. in the 1980s.
Phase Transitions for k-SAT
Ratio r of clauses-to-variables measures the
“constrainedness” of a k-CNF formula.
 Conjecture (Chvatal and Reed – 1992):
For every k > 1, there is a ratio r*(k) s.t.

– If r < r*(k), then pr(k,n,r)  1;
– If r > r*(k), then pr(k,n,r)  0.
Phase Transitions of kSAT



Theorem: 2SAT has a phase transition at r*(2)=1.
Chvatal and Reed (1992), Goerdt (1996)
Open Problem: Phase transition of kSAT, k > 2.
Current state of affairs:
– Analytical upper and lower bounds for
the value of r*(k), if it exists.
– Experimental results providing evidence
that r*(k) exists and estimates for its value.
Phase Transition of 3SAT


Lower and Upper Bounds for r*(3)
3.26 < r*(3) < 4.571
Lower: Achlioptas & Sorkin (2000);
Upper: Kaporis, Kirousis, Stamatiou, Vamvakari,
Zito (2001).
Experimental estimation of r*(3)
r*(3)  4.3
Mitchell, Selman and Levesque (1992).
Phase Transition and Hardness
Davis-Putnam (DP) Procedure for SAT
Unit Propagation + Splitting Rule
 Mitchell, Levesque and Selman (1992):
The average number of recursive calls
in the DP-Procedure for 3SAT peaks
near the critical ratio 4.3

Phase Transition Phenomena

Observed in other NP-complete problems
Experimental Results for
-- Graph Coloring Problems
-- Constraint Satisfaction Problems
-- Number Partitioning
Provable Phase Transition at 2/k(k-1) for
-- 1-in-kSAT Achlioptas et al. (2001)
Phase Transition Phenomena

Observed experimentally in problems that
are complete for higher complexity classes.
In particular, PSPACE-complete problems:
-- QBF: Cadoli et al. (1997),
Gent and Walsh (1999)
-- SSAT: Littman (1999),
Littman, Majercik, Pitassi (2000)
Hardness of Random #3SAT
Birnbaum and Lozinskii (1999)
Counting Davis-Putnam Procedure (CDP)
The average number of recursive calls
for #3SAT peaks near the ratio 1.2
 Bayardo and Pehoushek (2000)
CDP with connected components
The average number of recursive calls
for #3SAT peaks near the ratio 1.5

Counting vs. Decision Problems



#3SAT is a function problem, not a decision
problem.
Thus, is not meaningful to relate the peak in
average running time of algorithms for #3SAT
to a structural phase transition of the asymptotic
probability of #3SAT.
However, there is a class of decision problems
that “captures” the complexity of #P.
PP: Probabilistic NP


PP: there is a polynomial time NTM such that
an input is accepted iff at least half of the
computations are accepting.
Simon (1975), Gill (1977).
Prototypical PP-complete problem:
MAJSAT: given a CNF formula , is it satisfied
by at least half of the possible truth assignments?
PP vs. Other Complexity Classes
PP contains both NP and coNP.
 PP is contained in PSPACE.
 P PP = P # P (Angluin -- 1980)
PP “captures” the complexity of counting
 PH  P#P (Toda -- 1990)
PP is considered to be highly intractable.

Phase Transitions in PP Problems

Study PP-complete satisfiability problems
under the fixed clauses-to-variables model.

First natural choice to study: MAJ 3SAT
Phase Transitions in PP Problems
However,
 MAJ 3SAT is not known to be PP-complete.
 MAJ 3SAT has no phase transition:
for every r, almost all random 3CNF
formulas are satisfied by less than half
of all possible truth assignments.
Square Root 3SAT

Square Root 3SAT - #3SAT(  2n/2 ):
given a 3-CNF formula f, is it satisfied by
at least 2n/2 truth assignments?

Intuitively, #3SAT(  2n/2 ) asks whether at
least one of the first n/2 bits of the number
of satisfying truth assignments is equal to 1.
Square Root 3SAT

Square Root 3SAT - #3SAT(  2n/2 ):
given a 3-CNF formula , is it satisfied by
at least 2n/2 truth assignments?

Intuitively, #3SAT(  2n/2 ) asks whether at
least one of the first n/2 bits of the number
of satisfying truth assignments is equal to 1.

Theorem: #3SAT(  2n/2 ) is PP-complete.
Phase Transition Conjecture

F3(n,r): space of all 3-CNF formulas  with
n variables and rn clauses.

X: random variable on F3(n,r) such that
X() = number of satisfying assignments of  .

Conjecture: There is a ratio r* such that
– If r < r*, then Pr[ X  2n/2 ]  1;
– If r > r*, then Pr[ X  2n/2 ]  0.
Evidence for the Phase Transition

Analytical results that yield upper and lower
bounds for r*.

Experimental results suggesting that
r*  2.5
Upper and Lower Bounds for r*
Theorem: 0.9227  r*  2.595
Hint of Proof:
– Upper Bound: Markov’s inequality.
– Lower Bound:
-- Covering partial assignments.
-- Achlioptas’ differential equations
technique.
Upper Bound for r*
From Markov’s inequality,
Pr[ X 2n/2 ] E(X)/ 2n/2
 E(X) = 2n(7/8)rn
 Pr[ X 2n/2 ] 2n/2(7/8)rn
 If 21/2(7/8)r <1, then Pr [ X 2n/2 ] 0.
 So, if r >2.595, then Pr [ X 2n/2 ] 0.

An Approach to Lower Bounds
Show that, if r is small enough, then a
random formula (x1,…,xn) has  2n/2
satisfying assignments by finding a
partial assignment with  n/2 variables
covering .
 Covering means: the partial assignment
makes the formula true, regardless of the
truth value of the un-assigned variables.

Finding Covering Partial
Assignments
To show r* , use a known lower
bound for r*(3) to derive the existence of a
covering assignment for a random .
 To show r* use Achlioptas’
technique to analyze a simple randomized
algorithm, called the Extended Unit Clause.

1/2 Lower Bound for r*
Random 3-CNF  with m clauses, n
variables, and such that m/n 1/2.
  has at least one satisfying assignment s
by lower bound for r*(3) .
 Build partial assignment pwith n/2
variables that covers  :for each of
the n/2 clauses in , choose some literal
in the clause that is true under sand set p
to also make that literal true.

Experimental Results
Implemented a threshold version of
Birnbaum & Lozinskii’s CDP algorithm.
 Experiments on random 3CNF-formulas
with n = 10, 20, 30, 40, and 50 variables.
 Probability curves cross at r  2.5
 The average number of recursive calls
peaks near 2.5

Birnbaum & Lozinskii’s CDP
recursive function CDP(, n)
 if  is empty, return 2n
 if  contains an empty clause, return 0
 if  contains unit clause {t},
return CDP( ,n-1), where

–  contains all clauses in fthat do not contain
t;
– the literal t is removed if present.
CDP (continued)

otherwise choose any variable x in 
return CDP(  ,n-1) + CDP(  ,n-1),
where
–  contains all clauses in  that do not contain
x, with the literal x removed if present.
–  contains all clauses in  that do not contain
x, with the literal x removed if present.
Threshold CDP
Accumulate partial counts in recursive calls
of CDP.
 Return “yes”, when accumulated count
equals or exceeds threshold.
 Return “no”, otherwise.
 Can also use upper bound tracking to
terminate and return “no” earlier.

Summary

Evidence for a phase transition in a natural
PP-complete satisfiability problem.

Analytical upper bound 2.595 obtained via
Markov’s inequality is quite close to the value 2.5
of the critical ratio suggested by the experiments.

Open Problem: Obtain tighter upper and
lower bounds.
Work in Progress


Investigation of phase transitions of
#3SAT(2n), 0 <  < 1.
Experimental Findings:
-- Each such problem has a phase transition.
However,
-- The peak in the average number of recursive
calls does not always occur at the critical ratio.
The Bigger Challenge



Develop a theory of phase transitions
of algorithmic problems.
Are there structural properties that imply
the existence of phase transitions?
Is there a descriptive complexity theory
of phase transitions?