On the Structure of Uniquely
Satisfiable Formulas
Richard Cha*?g*
Jim Kadin
TR 90-1124
May1990
Department of Computer Science
Cornell University
Ithaca, NY 14853-7501
*Department of Computer Science, Cornell University, Ithaca, NY 14853. Supported
in part by an IBM Graduate Fellowship and by NSF Research Grant CCR-88-23053.
**Department of Computer Science, University of Maine, Orono, ME 04469.
On the Structure of Uniquely Satisfiable Formulas
Richard Changt
May 7, 1990
Jim Kadin?
Abstract. This paper presents some new results on the computational complexity of
the set of uniquely satisfiable Boolean formulas (USAT). Valiant and Vazirani showed
that USAT is complete for the class D? under randomized reductions. In spite of the
fact that the probability bound of this reduction is low, we show that USAT captures
many properties possessed by D? many-one complete sets. We show that the structure
of USAT can affect the structure of D? and the entire Polynomial Hierarchy (PH) as
well. That is,
1. if USAT=? USAT, then D? co-D? and PH collapses.
2. if USAT E co-D?, then PH collapses.
3. if USAT is closed under disjunctive reductions, then PH collapses.
The third result implies that the probability bound in the Valiant-Vazirani reduction
cannot be amplified by repeated trials unless the Polynomial Hierarchy collapses. These
results show that even sets complete under "weak" randomized reductions can capture
properties of many-one complete sets.
1			Introduction
USAT is the set of Boolean formulas with exactly one satisfying assignment. The investi-
gation on the computational complexity of USAT in relation to D? began when Papadim-
itriou and Yannakakis showed that USAT was in D? [PY82]. The class D?, co-D?and the
canonical ?m? -complete languages for these two classes are defined below.
Definition
D? --H(L1nT2IL1,L2?NP1
SATASAT = ?(F?,F?) IF1 e SAT and F2 ? SAT 1
co-D? = (T1UL2 L1,L2 ? NPJ
SATVSAT = f(F1,F2) P1 c SAT or F2 ? SAT 1
tDepartment of Computer Science, Cornell University, Ithaca, NY 14853. Supported in part by an IBM
Graduate Fellowship and by NSF Research Grant CCR 88-23053.
?Dep&tment of Computer Science, University of Maine, Orono, ME 04469.
psAT[1]
P
Figure 1: USAT and related complexity classes.
`Apparently USAT was once conjectured to be <? -complete for ??2:
We note here that the precise complexity of UNIQUE SAT is a persistent
open question. Our observation that it is in I)? casts doubt on the recurring
conjecture that it is complete for A?2 [PY82?.
This motivated Blass and Gurevich [BG82] to show that there exist oracle worlds where
USAT is not <? -complete for D?, hence not <rn??complete for A?2.1 Thus, there is some
evidence that USAT may not be ?? -complete for D?. Nevertheless, Valiant and Vazirani
went on to prove that USAT is complete for D? under randomized reductions [VV86]. We
define some standard reductions formally below.
Definition [VV86] A is random reducible to B, written A ??Wm B, if there exists a proba-
bilistic polynomial time function f and a polynomial p such that
x ? A			Prob[f(x) ?			> l/p(IxI)
x ? A ? Prob[f(x) ? = 1.
Definition [LLS75] A is disjunctive reducible to B, written A ?<?s II, if there is a polyno-
mial time function f such that for all x, f(x) = (yi,. . . ,ym) and
x ? A			a?, 1 ? i ? ni, y? ?
We abuse the terminology and say that a set B is closed under disjunctive reducibilities
if A ??? B ? A ?? B. Similarly, A is conjunctive reducible to B, written A <c?0n B,
`From recent work [Kad88], we have more convincing evidence that USAT is not <? -complete for A2? if
it were, the Polynomial Hierarchy would collapse.
2
if there is a polynomial time function f such that for all x, f(x) = (yi,. . , ym) and
x ? A ? Vi 1 ? i < in, y? ?
One would expect the definition of <rP -reductions to be different from the one used
by Valiant and Vazirani, because it is more natural to consider the definition where x Ei A
implies Prob?[ f(x) c			> 1/2. However, the definition they use is strong enough to give
the corollary USAT E RP ?			--H NP = RP. Furthermore, if A <? B and B is closed
under disjunctive reductions, then the results of polynomially many <rP -reductions can be
joined into one <r') -reduction to B. So, the <?P -reduction A to B can be amplified i.e.,
for any polynomials p, there exists f' such that
x ? A ? Prob?[ f'(x) E B] > 1 --H
In any case, the following theorem shows that USAT is <`Pm -complete for D?
Fact 1 (Valiant, Vazirani [VV86]) There is a polynomial time function f such that
x ? SATASAT Pwby[ f(x,y) ? USAT] > 1/(41x1)
x?SATASAT ? Prob?[f(x,y)?USAT]=1.
From this result, one would be tempted to say that USAT is "almost" many-one com-
plete for DF. However the <`P-reduction does not reduce strings in SATASAT to USAT
with high probability. In fact, the probability tends toward zero as the length of the for-
mula increases. At first glance, it is not clear how closely this completeness result relates
the structure of USAT to the structure of D?. For example, it is not clear whether USAT
can be in co-D?, or even psAT[1]?2 Thus, the "precise complexity" of USAT is still open.
In this, paper we make another step towards resolving this open question and show that
USAT does indeed behave like D? <? -complete sets in several ways.
First, we show that if USAT is equivalent to its complement under many-one reductions,
then D? = co-D?. This quick theorem was our first piece of evidence that the structure of
USAT can affect the structure of all the languages in D?. Note that D? = co-D? implies
that the Polynomial Hierarchy (PH) [Sto77]_collapses to A?3 [Kad88,CK89]. So, one should
consider it very unlikely that USAT =? USAT.
Our second theorem, suggests that USAT is not in co-D?. We show that if USAT e
co-D?,_then PH c ??3. This parallels the result of Kadin [Kad88], which showed that if
SATASAT e co-D?, then PH C A3?. We conclude that the structure of USAT can affect
the structure of the entire Polynomial Hierarchy in the same manner that SATASAT does.
In our third theorem, we investigate the structure of USAT under conjunctive and
disjunctive reductions. NP and co-NP are known to be closed under c9njunctive and
disjunctive reductions. D?, on the other hand, is closed under conjuncti?e ?eductions, but
not under disjunctive reductions unless PH C ?3? [CK9o]. Also, DeMorgan's Law implies
that co-D? is closed under disjunctive reductions, but not conjunctive reductions (with the
same caveat). It is easy to show that USAT is closed under conjunctive reductions, and
in our third theorem we show that USAT is not closed under disjunctive reductions unless
2We write psATIk] for the set of languages accepted by polynomial time machines that query the SAT
oracle only k times.
3
PH c ??3. Thus, compared to the <? -complete languages of the four complexity classes
surrounding USAT, we find that the structure of USAT under conjunctive and disjunctive
reductions is most similar to that of the D? <? -complete languages.
The third theorem also suggests that the probability bound of the Valiant-Vazirani
reduction cannot be amplified in the standard way (repeating and combining the result
of many reductions), because USAT is not closed under disjunctive reductions unless PH
collapses. So, this is evidence that there may not exist an <? -reduction from SATASAT
to USAT with high probability bound. Yet, USAT does capture some properties of <? -
complete sets desp?te the fact that the probability bound is so low.
The intuitive thread behind the last two theorems begins with the Valiant-Vazirani <rp -
reduction from SATASAT to USAT. Using_this reduction one can show that if USAT E
co-D?, then_every set in D? <?-reduces to SATVSAT (the canonical co-D? <? -complete
set). Since SATVSAT is closed under disjunctive reductions this <rP -reduction can be am-
plified._We know from Kadin's "hard/easy formulas" proof that if SATASAT <? -reduces
to SATVSAT, then PH collapses. By extending this_proof to <r') -reductions with high
probability bounds, it can be shown that if SATASAT <wrn?reduces to SATvSAT, then
PH collapses. Similarly, if USAT is closed under disjunctive reductions, there is an ___ -
reduction from SATVSAT to USAT which can be amplified. Since USAT <m? SATASAT,
this gives an <? -reduction from SATvSAT to SATASAT with high probability bounds.
Again, this collapses PH using a generalization of the "hard/easy" proof.
2 Unique Satisfiability and co-D?
In this section, we investigate structure of USAT in relation to co-D?. In the follow-
ing theorem, the hypothesis that USAT =? USAT is stronger than the assumption that
USAT Ei co-D?, but the consequences are stronger, as well.
Theorem 1 If USAT =? USAT, then D? = co-D? and PH c
Proof: One can show that SAT ?? USAT by constructing a function which adds ex-
actly one satisfying assignment to a Boolean formula. Hence, SAT <? USAT. Assuming
USAT =? USAT, both SAT and SAT ?m? -reduces to USAT. Since USAT is closed under
conjunctive reductions, SATASAT <? USAT. So, USAT is <? -complete for D?. How-
ever, we assumed that USAT =? USAT, so = co-D? and the Polynomial Hierarchy
collapses to A?3 by Kadin [Kad88].
The following lemma shows the standard way of amplifying the probability bounds of
<? -reductions.			a
Lemma 1 If A <? B and B is closed under disjunctive reductions, then for all polynomials
p'(n), there exist a polynomial time function f' and a polynomial q'(n) such that
x E A			Prob?[ f'(x, z) E			> 1 --H
x ? A ? Prob?[ f'(x,z) ?			= 1'
4
where n = Ixi and z is chosen uniformly over fO, 11q'(n)
Proof: Let f be the <rP -reduction from A to B. That is, there are polynomials p and q
such that
x E A			Pwbz[ f(x,z) E B]			> 1/p(n)
x ?A			Prob?[ f(x,z) ?			= 1,
where n = Ixi and z is chosen uniformly over f0, 1J?(n) Consider the set
D=t(Xi,...,xm) Ia?, 1<i<m, xj?B?.
Clearly, D <?s B. So, by assumption, D <? B via some polynomial time function g. Now,
define r(n) = p(n) .p'(n) and q'(n) = r(n).q(n). We construct the new ??-reduction f' as
follows. On input (x, z), where z ? fO, 11q'(n) and n = lxi, f' divides z into r(n) segments
Zr(n) of length q(n). Let
f'(x,z) =g(f(x,z1),f(x,z2),... ,f(x,zr(n))),
where 9 is the <? -reduction from D to B. Clearly, if x ? A then for all ?, f(x, zi) ?
So,'
x ? A ? Vz E tO, 1)q'(kI), f'(x, z) ? B Prob?[ f(x, z) ? B ] = 1.
Suppose x ? A, then Prob?[ f(x, z) ? B ] > 1/p(n), where z is chosen uniformly over
??, 1?q(n) So, the probability that for some i 1 <z < r(n), f(x, zi) c B is bounded below
by:
1--HProbz1,.. ,Zr(n)[V?? 1<i?r(n), f(x,z?)?B]
> 1 --H (1 --H i/p(n))r(n)
> 1 --H ((1 --H
Since (1 --H 1/p(n)?(?) converges to e?', we have
x E A ? Prob?[ f'(x,z) ? B ] >1 --H g?P'(fl) >1 --H2--H?1???
where z is chosen uniformly over ?0, 1?q'(n)
Before we go on, we need to define some probabilistic and nonuMform classes.
Definition For any dass C, A ? BP?C if there exists B E C and a const?nt; E such that
Vx, Prob?[ x ? A ? (x,y) ? > 1/2+?.
E]
Definition Let C be any class of languages and let f a polynomially bounded function
(i.e., there exists k such that If(?)I ? 1y1k + k). A E C/f if there exists B ? C such that
Vx, x E A			(x,f(11x)) E B.
5
f is called the advice function and f(1IZI) the advice string. Note that the advice string
depends only on the length of x. Also, we write C/poly for the union of C/f over all
possible polynomially bounded advice functions.
The "hard/easy formulas" proof, which showed that D? = co-D? implies PH collapses,
used the following line of reasoning. Suppose D? --H co?D?, then there is a many-one
reduction from SATASAT to SATVSAT. With the help of an advice function f, this
reduction can be converted into a reduction from SAT to SAT. Thus, SAT E NP/f. Then,
by a theorem due to Yap [Yap83], PH collapses_to ?3?. In the next theorem, we will
show that the <? -reduction from SATASAT to SATvSAT can be converted into an <rp -
reduction from SAT to SAT (with help from an advice function). It follows that SAT is
contained in the rather awkward class BP.(NP/f). A generalization of a theorem due to
Sch5ning relates BP.(NP/f) to nonuniform Polynomial Hierarchies.
Fact 2 (Sch5ning [Sch89])			____
For all polynomially bounded f, if SAT ? BP.(NP/f) then ?P2/f --H 11P/f.
Now, we are ready to show that if USAT were in co-D?, then the entire Polynomial
Hierarchy would collapse. This consequence 15 weaker than the one in Theorem 1, since it
does not imply that D? = co-D?
Theorem 2 If USAT E co-D?, then PH c ??
Proof: Suppose USAT ? co-D?. Since SATVSAT is ?? -complete for co-D?, there is a
<? -reduction from USAT to SATVSAT. Moreover,_SATASAT<?USAT, so there is an
<`? -reduction from SATASAT to SATvSAT. Since SATVSAT is closed under disjunctive
reductions, the probability bound of this ?? -reduction can be amplified by Lemma 1.
(Recall that the original probability bound was 1/(4n).) That is, using the disjunctive
reduction to combine the results of polynomially many <? -reductions, we can construct
a polynomial time function h and a polynomial q such that
(F1, F2) E SATASAT ? Prob?[ h(F1, F2, z) E SATvSAT] > 1 --H
(F1,F2) ? SATVSAT ? Prob?[ h(F1,F2,z) ? SATASAT] = 1
where n = j(F1, F2)I and z is chosen uniformly over fo, 1?q(n)
To prove the theorem, we will construct an advice function f computable in ?3? such
that SAT ? BP.(NP/f). Then, by Fact 2 ?P/f --H 11P2/f which implies that ?P3/f c ?2P/f
However, f is computable in A3?, so a ?3? machine can compute the advice for itself. Thus,
?c??/f--H?/f c??3			So,PH???.			___
Now, we construct the advice function f. We call F easy if F ? SAT and
?x,y such that Ixi = IF, y ? fo,1)?(n), r2(h(x,F,y)) E SAT,
where 7r? is the jth projection function (i.e., 7rj(X1,. . . ,Xm) = xi). F is called easy in this
case because there is "existential evidence" that F is unsatisfiable. If F ? SAT and F is
not easy, then we call F a hard string. On input 1?, the advice function simply outputs
the lexically smallest hard string of length n if it exists. Otherwise, it outputs the empty
6
string, ?. From the definition of easy, it is clear that checking whether a string is hard is
a co-NP question. So, using binary search and an NPNP oracle, the advice function f can
be computed in A3?.
Now, consider the following NP program. On input (F, H, z), N treats F as a Boolean
formula of length n, takes H as an advice string of length 0 or n, and parses z into a q(n)
bit long guess string. (If the input does not conform to this syntax, N rejects outright.)
Then, N does the following.
1. If the advice string H is the empty string, then accept if and only if
?x,y such that Ixi = n, yE f0,11q(n), r2(h(x,F,y)) E SAT.
2. If IHI = n, then accept if and only if 7r1(h(F, H, z)) E SAT.
CLAIM: The NP program above shows that SAT E BP.(NP/f). That is,
Prob?[ F e SAT ? N(F, f(1?), z) accepts ] > 1 --H
Note that whether there is a hard string of length n does not depend on the guess string
z. So, we can analyze the program in two cases.
CASE1: Consider the case where all the strings in SAT of length n are easy i.e.,
= e. If the input F E SAT, then F must also be easy which means the appropriate
x and y would be found in step 1. So,
FE SAT ? Prob2[ N(F,&,z) accepts] = 1.
If F E SAT, then for all x, (x, F) E SATVSAT. So, by the description of the reduction h,
Prob?[ h(x,F,z) E SATASAT] = 1.
But, h(x,F,z) E SATASAT implies that_?(h(x,F,z)) E SAT. So, N must reject in step
1. Thus, in the easy case Pwbz[ FE SAT N(F,?,z) accepts] = 1.
CASE2: Suppose the advice string H is a hard string of length n. If F E SAT, then
(F, H) E SATvSAT. By the description of the reduction h,
Prob?[ h(F,H,z) E SATASAT] = 1.
So, for all z, ir1(h(F, ii, z)) E SAT. Therefore, for all z, N will accept in step 2 and
F E SAT .` Prob?[ N(F, H, z) accepts] = 1.
If F E SAT, then (F,H) E SATASAT because H is hard implies th?t.Th E SAT. Also,
since H is hard,
Vx, Ixi --H n Vz z E fo, 1??(n), ?2(h(x, H, z)) E SAT.
So, for all choices of z, h(F,H,z) E SATASAT ? iri(h(F,H,z)) E SAT. Moreover, by
the description of h and the fact that (F, H) E SATvSAT,
Pwbz[ h(F,H,z) E SATASAT] < 2-?.
7
So, Prob?[ 7ri(h(F,H,z)) ? SAT] < 2-? Thus,
F ? SAT ? Pwbz[ N(F, H, z) accepts] ?
Since USAT plays no special role in this proof, this theorem holds for all D? <? -
complete sets.
Corollary 1
Let A be ??-complete for D?. If A E co-D?, then PH c A3?.
3 Unique Satisfiability and Disjunctive Reductions
In this section, we show that USAT is not closed under disjunctive reductions unless the
Polynomial Hierarchy collapses. At first glance, the proof of this theorem may appear
to be symmetric to the proof of Theorem2,because the intermediate step constructs an
<? -reduction from SATvSAT to SATASAT (cf. SATASAT <?P SATVSAT in Theorem
2). As it turns out, this theorem is much harder. Nevertheless, we can push the proof
through using a "hard/easy formulas" argument and another theorem from Sch6ning.
Definition [Se182] A is polynomial time positive reducible to B, written A <p?os B, if A
L(MB) where M is a polynomial time machine which has the additional constraint that
x c y ? L(Mx) c
Fact 3 (Sch5ning [Sch89])
For any class C closed under -reductions BP?C c CIpoly.
In the following proof, we will use the fact that for all polynomially bounded f, NP/f
is closed under <--Hp?os -reductions. Therefore, BP.(NP/f) c (NP/f)/poly = NP/poly.
Theorem 3 If USAT is closed under disjunctive reductions, then PH c
Proof: First, we note that if USAT is closed under disjunctive reductions, then the prob-
ability bound in the Valiant-Vazirani ?? -reduction from SAT to USAT can be amplified
by Lemma 1. That is, there is a polynomial time function f and a polynomial q such that
x ? SAT Pwb?[ f(x,y) e USAT] > 1 2?n2
xCSAT Pwby[f(x,y)?USAT]=1
where n = Ixi and y is chosen uniformly over (0, 11q(n) a
Also, USAT_being closed under disjunctive reductions implies that there is an <rp -
reduction from SATvSAT to USAT. However, USAT ? D?, so there is an <">rn-reduction
from SATV SAT to SATA SAT. Combined with the observation on amplifying the Valiant-
Vazirani reduction, this implies that there exist a polynomial time function h and a poly-
nomial q such that
8
(F1,F2) e SATVSAT Prob?[ h(F1,F2,z) e SATASAT] > 1 --H 2?n2
(F1,F2) E SATASAT ? Prob?[ h(F1,F2,z) E SATVSAT] = 1
where n = I(F1,F2)I and z is chosen uniformly over ?O, 11q(n)
As in the proof of Theorem 2, we define hard and easy_strings and construct an advice
function f. In this proof, we call a string F easy if F E SAT and
?x,Ixi = PI, Pwbz[ r2(h(x,F,z)) E SAT] > 2/3,
where 7rj is the jth projection function. As before, if F E SAT and not easy, we call F a
hardstring. We construct an advice function f which on input 1?_outputs the lexically
smallest hard string of length n, if it exists. Then, we show that SAT ? BP.(NP/f). In
this case, however, we do not know thatfcan be computed in ?3?. However, Fact 3 implies
that BP.(NP/f) C NP/poly. Thus, SAT ? NP/poly and by Yap [Yap83] PH c ?3?.
Consider the NP program N. On input (F, H, z?), N treats F as a Boolean formula of
length n, H as an advice string, and parses z = (zi, Z2, Z?? into three q(n) bit long guess
stnngs. Then, N does the following.
1. If the advice string H is empty, then accept if and only if
?x, such that lxi = n,ir2(h(x,F,z1)) ? SAT.
2. If HI --H n then accept if and only if
for each i 1,2,3, 7ri(h(F,H,zi)) ? SAT.
Note that step 1 in this program is different from the one in Theorem 2. The string z1 is
not guessed existentially in step 1, but taken from z
CLAIM: The NP program above demonstrates that SAT ? BP.(NP/f). That is,
Prob?[ FE SAT ? N(P,f(1n),j) accepts] >2/3.
CASE1: Consider the case where all the strings in SAT of length n are easy (f(1?) =
If the input F E SAT, then F must also be easy. Let x be the witness that F is easy.
Then, by the definition of easy,
Prob?1[ r2(h(x,F,z1) E SAT] > 2/3.
So, Prob?1 [ 3x, IxI = n, r2(h(x,F,zi) E SAT] > 2/3. So the pwbability that the existential
search in step 1 will be successful is greater than 2/3. Thus,
FE SAT ? P?ob?[ N(F, e, z) accepts] >2/3.
On the other hand, if FE SAT, then for all x, (x,F) E SATVSAT. Thus,
Prob?1 [ h(x,F,zi) E SATASAT] > 1 --H 2?n2.
So, Prob??[ r2(h(x,F,z1)) E SAT ] ? 2?fl2. However, 2--Hfl2 is so small, we can move an
existential quantifier inside the probability
9
Prob?1[ ?x, Ixi = Fl, r2(h(x,F,z1)) ? SAT] <1 --H (1 --H 2?n2)2n
Then, the following calculations give us
1 --H (1 2?n2)2 = 2?n2
--H 2?n2)i?1 < 2??2 2" = 2n?n2
s=1
Thus, F ? SAT ? Prob?[ N(F,e,z) accepts] <2n?n2.
Case2: Suppose there is a hard string H = f(1"). If F E SAT, then (F, H) ? SATVSAT.
So, by the description of h
Pwbz[ h(F,H,z) ? SATASAT] > 1 2?n2.
This means PWbz[ ?i(h(F?H,z)) ? SAT] >1 --H 2?n2. So,
Prob??,22,?[ for each i = 1,2,3, 7r1(h(F, H, zi)) ? SAT ] > (1 --H 2--H"2? > 1 --H 3. 2?n2
So, the probability that all three trials checking if 7r1(h(F, H, zi)) E SAT in step 2 are
successful is greater than 1 --H 3 2?fl2. Thus,
F ? SAT? Prob?-[ N(F,H,i) accepts] >1 --H 3 2?"
On the other hand, if F ? SAT, then (F, H) ? SATASAT. From the description of h, this
means Pwbz[ h(F, H, z) e SATVSAT] = 1. However, H is hard, so
Pwbz[ ir2(h(F, H, z)) E SAT] > 1/3.
Note that (G1,G2) ? SATVSAT and G2 ? SAT implies that G1 ? SAT. So,
Prob?[ 7r1(h(F, H, z)) ? SAT] > 1/3.
This yields the relation
Prob?1?2?3[ for each i = 1,2,3, 7ri(h(F,H,zi)) ? SAT] ? (2/3)? < 1/3.
Thus, F ? SAT Prob?[ N(F, H, z) accepts] ? 1/3.
As in Theorem 2, USAT plays no special role in the proof. With minor modifications,
the preceding proof will also show the following corollary.
Corollary 2
Let A be <? -complete for D? If A is closed under disjunctive reductions, then the
Polynomial Hierarchy collapses to ?3?.			a
Proof: (Sketch) In Theorem 3, we implicitly used the <m? -reduction from SAT to USAT
to construct an ??-reduction from SATVSAT to USAT. For a D? <?P?complete set A,
there may only be an <? -reduction from SAT to A. However, the <?P -reduction can
be amplified by Lemma 1, because we are assuming that A is closed under disjunctive
reductions. Thus, there exist a polynomial q and two polynomial time functions f and g
such that
10
x E SAT			?			Prob?[ f(x,y) ? A] >1 2?n2
x?SAT			?			Pwby[f(x,y)?A]=1
x ? SAT			?			Prob?[g(x,y) ? A] >1 ?2?n2
x?SAT			Pwb?[g(x,y)?A]=1
where n = Ixi and y is chosen uniformly over to, 1)q(n) Consider the set
D = ((i??,F?? F1 E A or F2 ?
Since D <? A, there is a <? -reduction t from D to A._Using t, the two <? -reductions
f and g can be combined into one <? -reduction from SATVSAT to A:
(F1,F2) ? SATVSAT ? Pwby[ t(f(F?,y),g(F2,y)? E A] > 1 2?n2
(F1,F2) E SATASAT Prob?[ t(f(F1,y),g(F2,y)? ? A] = 1
The rest of the proof would proceed in the same way as the proof 0 Theorem 3. E]
4 A Technical Discussion
One way to remember Theorem 2 is:
SATASAT ??P USAT <m? SATVSAT ? PH collapses.
We would like to say that the intuition behind these proofs is that not only does D? c co-D?
collapse PH, but so does D? c BP?co-D?. Then, we could draw an analogy with the
Polynomial Hierarchy, since both ?: c 11k? and ??k ? BP.ll: collapse the Polynomial
Hierarchy [Sch89]. However, to prove this is the correct intuition, we would also have to
show that co-D? C BP?D? collapses PH. We are unable to prove this statement, because
both the "hard/easy formulas" argument and the Valiant-Vazirani random reduction are
one-sided that is, there is an easy case and a hard case. When the easy cases match,
everything works out (as in Theorem 2). When the cases do not match, life becomes
difficult. So, we leave as an open question:
SATVSAT <? USAT ?m? SATASAT # PH collapses.
(Note that the hypothesis is weaker than the one in Theorem 3.) Such a theorem may
very well resolve some open questions about the Counting Hierarchy des?flbed by Cal and
Hemachandra [CH85].
5 Conclusion
We have shown that the complexity of USAT affects the structure of D? and of the entire
Polynomial Hierarchy in much the same way that D? <? -complete sets do. This happens
11
despite the fact that the Vahant-Vazirani <r') -reduction has a low probability bound. In
fact, Corollaries 1 and 2 apply to all D? <rP -complete sets. So, these results show that
--H<m? -complete sets can capture some of the properties of <m? -complete sets even when the
definition of <rP allows reductions with low probabilities. It would be interesting to see if
the <r') -complete sets of other complexity classes have this behavior.
6 Acknowledgements
The authors would like to thank Vijay Vazirani and Desh Ranjan for sitting through various
versions of our proof, Steve Mitchell and Christine Piatko for helpful hints on probability,
and Juris Hartmanis for his unwavering guidance and support.
References
[BG82] A. Blass and Y. Gurevich. On the unique satisfiability problem. Information and
Control, 55(1--H3):80--H88, 1982.
[CR85]
[CK89]
[CK9o]
J. Cai and L. A. Hemachandra. The Boolean hierarchy: Hardware over NP.
Technical Report TR 85-724, Cornell Department of Computer Science, December
1985.
R. Chang and J. Kadin. The Boolean hierarchy and the polynomial hierarchy: a
closer connection. Technical Report 89-1008, Department of Computer Science,
Cornell University, May 1989. To appear in Proceedings of the 5th Structure ?n
Complexity Theory Conference.
R. Chang and J. Kadin. On computing Boolean connectives of characteristic
functions. Technical Report 90-1118, Department of Computer Science, Cornell
University, May 1990.
[Kad88] J. Kadin. The polynomial time hierarchy collapses if the Boolean hierarchy col-
lapses. SlAM Journal on Computing, 17(6):1263--H1282, December 1988.
[LLS75] R. E. Ladner, N. A. Lynch, and A. L. Selman. A comparison of polynomial time
reducibilities. Theoretical Computer Science, 1(2):103--H123, 1975.
[PY82] C. II. Papadirnitrion and M. Yannakakis. The complexity of facets (and some
facets of complexity). In A CM Symposium on Theory of Computing, pages 255-
260, 1982.			a
[Sch89] U. Sch5ning. Probabilistic complexity classes and lowness. Journal of Computer
and System Sciences, 39(1):84--H100, 1989.
[Sel82] A. L. Selman. Reductions on NP and ?sdective sets. Theoretical Computer
Science, 19(3):287--H304, 1982.
12
[Sto77] L. Stockmeyer. The polynomial-time hierarchy. Theoretical Compnter Science,
3(1):1--H22, 1977.
[vv86j L. G. Valiant and V. V. Vazirani. NP is as easy as detecting unique solutions.
Theoretical Computer Science, 47(1):85--H93, 1986.
[Yap83] C. Yap. Some consequences of non-uniform conditions on uniform classes. Theo-
retical Computer Science, 26(3):287--H300, 1983.
13