BIB-VERSION:: CS-TR-v2.0
ID:: CORNELLCS//TR93-1386
ENTRY:: 1993-10-14
ORGANIZATION:: Cornell University, Computer Science Department
LANGUAGE:: English
TITLE:: On Properties of Random Reductions
AUTHOR:: Rohatgi, Pankaj 
DATE:: September 1993
PAGES:: 99
COPYRIGHT:: Pankaj Rohatgi 1994 - All Rights Reserved
ABSTRACT::
Randomness is widely accepted as a powerful computational resource because 
the most elegant and efficient solutions to several computational problems 
are randomized. A recurrent theme in the theory of randomized computation is 
the notion of a random reduction. Random reductions are similar to many-one 
($\leq^{P}_{m}$) reductions except for the fact that they are carried out by 
probablistic transducers which may make errors with small probability. Such 
reductions are used explicitly in many basic results in complexity theory and 
implicitly in several randomized algorithms.

This thesis investigates the properties of random reductions as a tool 
towards understanding the power and limitations of randomness. We first prove 
some startling results which indicate that random reductions can be quite 
successful in reducing harder problems to simpler ones. We then propose the 
thesis that in many situations there is a sharp {\em probability threshold} 
which governs just how successful random reductions can be in this regard. As 
evidence, we prove that for several complexity classes ${\cal C}$, under 
standard assumptions, there exist corresponding {\em probability 
thresholds\/} ${\cal C}_T$, such that random reductions with success 
probability below ${\cal C}_T$ can reduce the hardest languages in ${\cal C}$ 
to simpler ones but reductions with success probability above ${\cal C}_T$  
cannot do so. Based on these thresholds, we then propose a meaningful 
definition of completeness under random reductions which resolves several 
anomalies caused by the traditional definitions which did not place much 
emphasis on the success probability.

The results described above depend on standard but unproven 
complexity-theoretic assumptions. In order to show that such behavior is 
inherent to random reductions and not an artifact introduced by these 
assumptions, we also prove that it is present in very high complexity classes 
{\em without any assumptions}. In this thesis we also examine other basic 
aspects of random reducibility. We prove several {\em absolute} separation 
results between the notions of completeness under various polynomial-time 
random reductions with different success probabilities and between various 
random reductions and deterministic polynomial-time reductions. In addition, 
we also prove new results on the consequences of having random reductions 
from NP-complete sets to sparse sets.
END:: CORNELLCS//TR93-1386
BODY::
On Properties of Random Reductions
Pankaj Rohatgi
Ph.D Thesis
93-1386
September 1993
Department of Computer Science
Cornell University
Ithaca, NY 14853-7501
ON PffOPERTIES C)F' ffANDOM R?EDVCTiONS
Dissertation
Presented to the E)?c??lty of the Graduat?? Scho(?l
of (??c?rnell University
in Partial Fulfi?lment of the Requirei?ents for fhe Degr?e of
Do?,t??r of Philosophy
by
I??'tnkaj R?ohatgi
Ja?uary 19cj4
e Pank?tj R?oliatgi 1994
ALL R[GHTS RESERVED
ON PROPERTILS 0'? RANDOM REDUCTIONS
Pankaj Rohatgi, Ph.D.
Corn??ll University 1994
Randomness is widely accepted as a powerful computational resource because the
most elegant and efficient solutions to several computational problems are random-
ized. A recurrent thenie in tlie thcory of randomized computation is the nt)ti?)n of
a random reduction. Randoni reductions are similar to many-one (?m?) reductions
except for the fact that they are carried out by probablistic transducers which may
make errors with small probabi[it? Such reductions are used explicitly in ma?y
basic results in complexity theory ?lld implicitly in several randomized algorithrn?;.
This thesis investigates the I)roperties of random reductions as a tool towards
understanding the power and liniitations of randomness. We first prove son?e
startling results which indicate that random reductions can be quite successful in
reducing harder problenis to simpler ones. We then propose the thesis that in many
situations there is a sharp pro1?(?b'tizt?J th?esho1d which governs just how successfiil
random reductions can be in this regard. As evidence, we prove that fi?r several
complexity classes C, under stand?ird assumptions, there exist corresponding pcob-
abzlzty thresholds CT, such that raiid??m reductions wfth success probability below
CT can reduce the hardest laugu<tg??s in C to simp[er ones but reductions with
success probability above CT cannot do so. Based on these thresholds, we then
propose a meaningful definition of completeness under random reductions which
resolves several anomalies caused by the traditional definitions whicb did not place
much emphasis on the success probability.
The results described above depend on standard but unproven complexity-
theoretic assumptions. In order to show that such behavior is inherent to random
reductions and not an artifact introduced by these assumptions, we also prove
that it is present in very high complexity classes without any assumptions In
this thesis we also examine other basic aspects of random reducibility. We prove
several absolute separation results between the notions of completeness un?ler var-
ious polynomial-time iandom reductions with different success probabilities and
between various random reductions and deterministic polynomial-time reductions.
In addition, we also prove new resul? s on the consequences of having ran?lom re-
ductions from NP-complete sets t() sparse sets.
BIOGRAPHICAL SKETCH
Pankaj Rohatgi was born on July 5,1967 in the older section of Delhi which is
a few miles north of the capital city of New Delhi. He attended St. Xavier's
School in Delhi for sev?ral years before moving to Kuala Lumpur, Malaysia where
he obtained his GCE `0' Levels from the University of London. He thei? returned
to Delhi to complete hiS schoohug and in 1984 he joined the Indian Institute of
Technology at New Delhi where he received his Bachelor's degree in (?ornpuI'er
Science and Engineering in May 1 988. He then joined the graduate school at
Cornell University and obtained 1LiS Master's degree in computer science in May
1991 and a Ph.D. in September 1?)93.
iii
To my parents
iv
ACKNOWLEDGEMENTS
First of all, I would like to express my gratitude to Prof. Juris Hartmanis for
introducing me to research and guiding me through this thesis. It would have
been impossible for me to complete this work without his constant encouragement
and support. An outstanding researcher, teacher and a very warm human being, he
has been both a source of inspiration and a guide on acadenjic and non-academic
matters.
I thank Prof. Gerard Salton artd Prof. Anil Nerode for serving on iny special
committee and providing many hel$ul suggestions. I thank Prof. Dexter Ko,?en
and Prof. 5. N. Maheshwari for intrnducing me to the mathematical beauty of
Theoretical Computer Science.
It has been a pleasure working with my coauthors Jim Kadin, Richard Chang,
Desh Ranjan, Suresh Chari and Aravind Srinivasan and their coittributions are
gratefully acknowledged. Special thanks to Richard for introducing me to the the
intricacy of the Boolean and Quei?y hierarchies and collaborating with me on the
central theme of this thesis. I have also benefited greatly from discussions with
Bill Gasarch, Radhaknshnan Jagadeesan, Dexter Kozen, Steve Mitchell, David
Shmoys and Vijay Vaziran'.
I would like to thank all my friends who helped me endure five long winters in
v
Ithaca. Special thanks to Capt. Sofokhs Eften?idis who has been rny offlcemat?,
for the past five years.
I gratefully acknowiedge the generous financial support pr?wided by the Na-
tional Science Foundation (Researcb Grants #CCR?-8823o53 and ? CCR?-9 123730),
the IBM Graduate Fellowship aud the Mathematical Sciences Institute of Cornell
University.
Last but not the least, I thank my family for their support.
vi
TABLE OF CONTENTS
1 Introduction
2 Preliminaries
2.1 Reductions Defined
3
4
5
Saving Queries with Randomness
3.1 Background
3.2 Summary of Results
3.3 The Reductions
3.4 Proofs of Optimality
3.4.1 An Example
3.4.2 Proof for a General Case
3.4.3 Other cases
Randomization and Bouii??e?I Query Functions
Open Problems
7
8
12
16
23
23
28
29
38
46
3.5			. .			. .			47
3.6			. .			. .			. . .			.			52
53
o+ .			54
o+ .			. .			57
58
59
60
64
Completeness under Random Reductions: Absolute Separations 67
5.1			Preliminaries			. .			. . .			. .			. . .			. .			.			71
5.2			Separation results in exponential time			71
5.3			Separation resufts for on(' sided random reductions			. . .			.			74
5.3.1			Deterministic but not <rP????p???? sets .			75
5.3.2			Separations of different probability			f?rP?reductjons			. .			78
5.4			Separations ft?r ?bpp?rediictions .			81
5.5			Discussion .			.			.			. .			. .			. .			. .			87
Threshold Behavior
4.1 USAT and Random Reductions
4.2			Anomalous Behavior
4.3			Threshold Behavior .			. .
4.3.1			Examples of Threshold Behavior			. .
4.3.2 Threshold Behavior in the classes D? and co-D?
4.3.3 Threshold behavior in the Boolean and Query Hierarchies
vii
6
Random Reductions and Sparse Sets
6.1			Definitions .			. .			.
6.2 Main R?esult
6.3 Open Probleins .
Bibliography
viii
88
89
9:3
94
LIST OF FIGURES
3.1 The structure of the floolean and Query Hierarchies
3.2			Optimal ?rp and ?bpp reductions . .			.
4.1			USAT and related complexity classes.			. .
ix
22
55
Chapter 1
Introduction
The aim of complexity theory is to characterize the inherent difficulty of problems
in terms of the computational resoitrces required for their solution. Thus, identif?-
ing important computational resources and expl??ring relationships between them is
a fundamental area of iesearch in this field. In the early days, research in compl??-
ity theory focused on tradition;?J c()ini)utational resources such as Time, Space and
Nondeterminism. Moie recently, however, research on non?traditional resour(?es
such as Randomness, Queries to 0 c?cles and Interaction with all powerful provers,
has turned out to be very fruitful. For instance, very recently, the st'idy of the
interaction between two non-trad ttional resources: Randomness and Int??raction
with a prover, led to several breakthrough results which imply that even obtaining
good approximations to many NF'-Optimization problems such as the ?Yavelhng
Salesman Problem on a plane, th(. Maximum Chque and the Chromatic Number
of a Graph, is as hard as solving these problems exactly [FGL+91,A592,ALM+92,
LY93J
A key resource that has recei?ied much attention lately is access to a source
of randomness. It has proved to l?e a valuable computational resource because
some of the most elegant and efi[ci??nt solutions to several coniputational problen?s
are randomized. In several casEs, e.g., solving the connectivity problem in undi-
2
rected graphs in loganthmic space (LOGSPACE) [ANL+79], testing primality in
polynomial time (P) [R?ab8O] or ?iidh?g a perfect matching iii a graph in parallel
using polylogarithmic 4ime and polynomial number of processors (NC) [KUW86,
MVv87,CRS93j, the use of randomness is the only known tool which allows these
problems to be solved in the given resource bounds. Sometimes, as is the case
with interactive protocols [Bab85,GMR?89] between a polynomial time machine
(a verifier) and an all powerful prover, the introduction of randomness results in
a dramatic increase in computational power. If the verifier is deterministic then
these protocols capture the class NP (Nondeterministic Polynomial time) but if
the verifier is allowed access to randomness then these protocols capture the much
larger complexity class PSPACE (l?olynomial Space) [Sha9O].
Due to the importance of rai?domness as a computational resource, a lot of re-
search has focussed on characterizing the the power and limitations of randomness
by studying its interaction wftb other computational resources. The interaction
between R?andomness and tradi-tioiial resources such as Nondeterminism, Time and
Space has been well studied. Siuct-: tlie existence of true sources of ranciomness is
still the object of an ongoing philc?sophical debate and sources which are believed
to random are quite sl(?w, there has also been extensive research on optimizing ilie
amount of randomness required to solve problems efficiently and several techniques
such as the use of limited independence between random variables and the use of
smaller sample spaces which apprC??mate the behavior of larger distributions have
been developed.
A recurrent theme which appears explicitly and implicitly in the literature
dealing with randomized comput:?i-ions is the notion of a randoni reduction. A
random reduction is quite similar to I he classical polynomial time many-one (? ?
reduction except for the fact that it is carried out by a probablistic (ratber than
deterministic) transducer which may make mistakes with very small probability.
These type of reductions were introduced by Adleman and Manders [AM77] to
3
resolve the complexity of several number theoretic problems. For a long time,
it was suspected that these number theoretic problems were NP-complete but no
one was able to come ni) with the r?quired deterininistic polynoniial time reduction
from SAT (the canonical NP-coinl)lete Boolean Satisfiability problem) ()? provide
any other evidence that these problems were intractable. Although, Adleman and
Manders did not succeed in obtaining a deterministic reduction, they were able
to reduce SAT to these problems using a ?andom reduction This immediately
established that these number-theoretic problems cannot have efficient solutions
unless all problems in NP also have efficient randomized solutions. A similar
approach was also successfully applied by Valiant and Vazirani tVV8GJ to settle
the comple?ty of the Unique S;tti?flability problem (USAT) i e., the problem of
deciding whether a given boolean formula has exactly one satisfying assignmenI?.
They succeeded in obt?'dning a random reduction from SAT to ??SAT, even though
Blass and Gurevich [BG82? ha?[ ??1ier proved that most techniques wili fail to
produce a ?? reduction. Subs?q'i?ntly, random reductions such as the Valiani-
Vazirani reduction have also tuin??d ?)ut to be very useful in resolving sonte basic
issues in complexity theory snch a? tite complexity of counting problems based on
the number of accepting paths of NP machines [Tod89,TO91,RF9()i.
Apart from these explicit uses in complexity theory, random n?dtictions have
also been used implicitly in the design of several randomized algorithjns. As an
example, consider the prnblein of finding a maximal matching in a graph. Although
polynomial time sequential algorithms were developed for this i?roblem deca?les
ago, it is still open whether this problem can be solved in NC, i.e., in parallel
using polylogarithmic time and j?olynomial number of processors. However if
randomness is allowed then this c?? be done [KUW86,MVV?7?CRS93J. Although
not explicitly stated in the hter<itiire these algonthms actually work by randomly
reducing the given instance of th ntatching problem to an instance ()f a matrix
inversion problem for which efficient NC algorithms are known.
4
In this thesis we provide fresh insights into the the power and limitations of
randomness by investigating the properties of random reductions. Intuitively, if
a problem A deterrnznzstically many-one (?m?) reduces to a problem 1? in poly-
nomial time then we know that ?? is not much harder than I?. Thus it is not
possible for ??m reductions to reduce a hard problem to a substantially simpler
one. However, in Chapter 3 (the technical backbone of this thesis) we will prove
several surprising results which show that random reductions can succeed in reduc-
ing harder problems to simpler ones with good probability of success. For instance,
we will show that by using randomness with good probability one can recognize
languages in bounded query classes such as pSATii[ki (languages recognizable in
polynomial time using k nonadaptive queries to a SAT oracle) using fewer than k
nonadaptive queries. This is in sh??rp contrast to the results of Kadin [Kad88] and
Chang and Kadin [CK9Da? which state that under a reasonable hypothesis, one
cannot save even a single query dcterministically. We argue that tltese surprising
results, instead of being anomalies, iii fact demonstrate the po??r of randomness.
In Chapter 3, we also show under ucasonable hypothesis that certain problems do
not randomly reduce t() simpler on(s beyond a certain success probability and this,
we argue, demonstrates the limitations of randomness.
Based on the technical results presented in Chapter 3, in Chapter 4 we propose
the thesis that, in several situations, the power and limitations of randontuess
is precisely characterized by a p??ba?i1it? threshold for random reductions. As
evidence, we will show that for sev?ral comple?ty classes, under standard assunip-
tions, there exist couesponding probability thresholds such that random reductions
with success probability below the threshold can reduce the hardest languages in
these classes to simple? ones bnt r<tiidom reductions with success probability above
the thresholdcannot do so. We believe that the thresh old is afundarnerital attribute
of every complexity class which pi??cisely chara?:terizes the tradeoff involved in the
use of randomness to reduce thy? ?on?plexity of probfrms within it, i.e., it qualiti-
5
fies the minimal amouiit of error tbat must be introduced in order to reduce the
complexity of the hardest problen?s in the class using randomness. Our results
on probability thresholds also highlight for the first time the crucial role played by
the success probability of random reductions. Traditionally randoni ieduciions
were defined without giving mitch consideration to the success probability of the
reduction. Our results immedia?ely imply that any meaningful definition of com-
pleteness under random reductions must take into account the success pi?babilfty:
languages complete under random reductions with success probability above the
threshold behave almost like the hardest languages in the class whereas languages
complete under lower probability reductions could be much simpler.
The notion of probabilfty thresholds developed in this thesis also fits well with
some earlier results of Graham and Yao [GY89] on probabilistic protocols for the
Byzantine Generals Agreement Problem. It is well known that no deterministic
protocol can solve the n-processoi Byzantine Generals Agreement Problem if the
number of faulty processors t is fl/13 ()? more. However, randonbzed proto?'ols can
succeed in solving this problem wii?h good probability of success. Graham arid Yao
were the first to prove tight bounds on the success probability of some ()f th??se
randomized protocols in terms ?)f ?? and t and thus were able to e?a?ftly quantify
the tradeoff involved in the use of raitdomness to solve this class of problems.
The results presented in Chapters 3 and 4 are based 011 the assumption ihat the
Polynomial Time Hierarchy (PH) does not collapse to its third level. Alihough this
is a standard assumption in comple'?ity theory and in fact, it is widely believed that
the PI' does not collapse at all. still, the validity of our conclusioits in Chapters
3 and 4 can be questioned on this account. So, in Chapter 5. we pmve that
random reductions exhibit simit,ir l?eltavior in very high complexity classes without
any assumptions. This provides strong evidence that such behavior is inherent to
random reductions an?l not a consequence of some quirk in our assumptions.
Apart from threshc?ld behavioi this thesis also examines sever<il basic aspects
6
of random reducibility. In Chapter 5, we also prove several u?so?te separation re-
suits between the notions of completeness under various polynomial-time random
reductions with different success probabilities and between various random reduc-
tions and deterministic polynomial-time reductions. This work can be seen as a
natural extension of the seminal work of Ladner, Lynch and Selman [LLS75] and
Watanabe [Wat87] who provided the first absolute separation results for various
deterministic reductions. In Chap?er 6 we prove some new results on the conse-
quences of having random reductions from NP to sparse sets which builds upon
earlier work by Mahaney [Mah82j, Ogiwara and Watanabe [ow90] and others on
deterministic reductions from NP to sparse sets and improves upon prior work of
Mahaney and Simon [MS81] on rand??m reductions to sparse sets.
Chapter 2
Preliminaries
In this chapter we will go over tl?e definitions of various types of deterministic
and random reductions that will be used in this thesis. We will also use this
as an opportunity to fix some notation. We assume that the reader is alr0ady
familiar with classes such as polynoinial time (P), polynomial space (PSPACE),
nondeterministic polynomial time (NP) and its complementary class co-NP the
NP-complete set SAT and the f)olynomial time Hierarchy (PH). If not, then any
of the standard texts on Theory of Computing or Comple?ty Theory would ser?e
as an excellent reference [HU79,LP8l,BDG9O]. In this thesis we will also deal with
other complexity classes in the Boolean, Bounded Query and Weak Exp??nentiJ
Hierarchies but we will defer the definitions of these classes to later chapters wheie
they are used.
We also assume that the reader is familiar with the Turing machine niodel arid
in particular with the notion of oracle Turing machines. We shall distinguish b&
tween two types of access mechanisms to the oracle, the usual adaptivemechanism
and the more restrictive nonadaptivemechanism. In the usual adaptiveniechanisni,
the Turing machine makes queries to its oracle sequentially and eacb query can
depend on the answers provided l)y the oracle to prior queries. In the case of the
nonadaptiveaccess mechanism, the Turing machine is forced to make all its queries
7
8
to the oracle at the same time. That is, the machine computes independently for
some time, then it asks a vector of queries to the oracle and upon receiving the
corresponding vector of responses its access to the oracte is terminated. Thus. the
queries made by the machine are independent of the response of the oracle an?i
hence the use of the term nonadaptive to describe this access mechanism.
Notation We will denote the output of an oracle Turing machine A/I on input x
and adaptive access to oracle 0 ? iV0(x).
Notation We will denote the output of an oracle Turing machine ?[ oil input x
and nonadaptive access to oracle 0 as AJ0?(x).
Sometimes we will be dealing with Turing machines with furtber restrictions
on the oracle access to their oracl?. A common restriction is to liniit the number
of queries allowed to the oracle and in this thesis we will be dealing with severaJ
instances where the number of adap?ive or nonadaptive queries allowed to the oracle
are bounded by some constant k. In such cases we will denote the output of an
oracle Turing machine M on input x with a bound k on the number of adapPve
or nonadaptive queries to its oracl? 0 as MO[k](x) and MO?[ki(x) respectively.
Since this thesis deals with tite ])roperties of random reductions we fl()w go o?Ter
the definitions of various deterininistic and random polynomial-time reductions.
2.1 Reductions Defined
One of the most basic concepts in recursion theory as well as in complexity theory
is the notion of reductions between languages. First let us review various deter-
ministic polynomial time reductiorts. The classical polynomial time deterministic
reductions are the Many-one (?i' ), Truth-Table (??tt) and Turing ( ??T) reductions
which are defined as follows:
Definition We say that A?'? ]?` if there exists a polynoniial tinie computable
9
function f such that
x ? il			f(x) E I?.
Definition We say that A?ft B if there exists a polynomial time mad?ne ?J
such that
x E A ? MB?i(x) accepts.
Definition We say that A ?T? B, if there exists a polynomial time machine A/I
such that
x ? A ? MB(x) accepts.
It is obvious from these definitions that if A?? B then that imphes that A?ft B
which in turn implies that A ?? 1?. In seminal work, Ladner Lynch ai?d Selman
[LLS75] showed that, in E (expom?ntial time), ffim? -reduction? are strictly stronger
than <ft-reductions which are in turn strictly stronger than ?T? -reductions, i?e.,
there are languages A, B, C and I) such that A?ft B but A ??m ? and (? ??T 1)
but C ?ft D. Apart from separatilig these basic reducil?litie?, Ladner, Lynch and
Selman also defined and separated several specialized instances of ?ftreductic?ns
such as the the k-truth table (ft?k--Htt)' conjunctive ( ??conj ) and disjunctive ( S?disj )
reductions. Since we will also be deating with these specialized ?ft reductions we
shall define them here.
A k-truth table reduction (for any constant k) is a special case of a
reduction in which the machine carrying out the --H??tt reduction makes no more
than k nonadaptive queries to i?s oracle. More formally:
Definition We say that A?)'?ft !?, if there exists a polynomial time machine Ail
such that
x C A ?-? AIB!I[ki(x) accepts.
We now define the conjunctive ;?nd disjunctive reductions. These can b( viewed
as specialized <ft reductions in wl?ich the polynomiai time oracle machine carrying
10
out the reduction accepts if and only if all (or at least one) of its oracle queries are
answered as yes respectively.
Definition We say that A --H??coiij B, if there exists a polynomial tinte machine M
which on input x outputs a non-empiy set Mx such that
x C A ? Mx fl B
x A ? Mx fl B #
Definition We say that A ffi?disj B, if there exists a polynomial time machine A/I
which on input  outputs a nowe'itpty set Mx such that
w C A -;> Mx n B ?
x A ? Mx n B --H--H
We now define various types of raitdo?n reductions between sets. These definitions
are based on the definitions givt?n ill [AM77,VV86] and can be viewed as general-
izations of the notion of a ?? -r?ditction. Depending on the type of error allowed,
three types of random reductions (the ??rP, ?mco?rP and <bmPP reductions) have
been defined in the lit??rature. Th( ?rp and ?co--Hrp random reductions are ont
sided error reductions whereas th? ?bpp -reduction is a two-sided error reducti??'t.
Definition We say that A ?rp R with probability ?, if there exists a polynomial
time function f such that
x ? A ? Probz[ f(x,z) C > ?
x ? A --H--H? PThI)z[ f(x, z) ? 1,
where z is chosen uniformly at ra&qdom from ?0, 11q(IxI), for some polynomiat q.
Definition We say that A ?co-rp 1? with probability ?, if there exists a polyn??mial
time function f such that
x E Am-> Prol)z[ f(x,z) ? B j --H--H 1,
x ? A -> Frob?[ f(x, z) ? B ] > ?
11
where z is chosen uniformly at random from ?0, 1?q(Ixj), for some polynomial q.
Thus a ?CmO?W -reduction is qttite similar to a ?rp -reduction except for the
fact that it errs on the opposite side. Next we define a ?bpp -redu?,tion in whiU?
the error may occur on either si?Ie
Definition We say that A <bpp B with probability 6, if there exists a polynomial
time function f such that
Prnb[xc-A ? f(x,z)cB]>?6,
where z is chosen uniformly at random from fo, 11q(Jxj), for some polynomial q
and 6> 1/2.
With these definitions in place we can now proceed to the rest of this thesis
with a good understanding of various lypes of deterministic and random reductions.
However, before we proceed let us also fix some additional notation that we will
use throughout the thesis.
Notation Let fo, 1J? denote tile set of n-bit strings. For any set ??. let A=?
denote the set of n-bit strings in A. Similarly, let A--H<? and A>? denote the suose-ts
of strings in A of length less than or equal to n and greater than n respectiv??Ly.
Notation Let r? denote ?th prc?ection function, and 7r(i,j) denote the ft'nction
that selects the jth through 1th elements of a k-tuple. For exaniple,
rj(( Wi, . . , Xk Xj and 7r(i,j)(( Wi,..., Xk ?) --H ( Xj, ..., W5 ?.
Chapter 3
Saving Queries with
Randomness
Randomness is a useful comput?t?nal resource due to its ability to enhance the
capabilities of other re,ources. N7ei?? ?ften, the best known randon'ize? ;ilgorfthrns
are faster than the b(?st knowit :?t?rministic solutions. Iii several cas(?s, e.g.,
solving the connectivity prnl)lem iF undirected graphs in LC)GSPACE [AKL+ 7C)]
or finding a perfect matcbing in a o;r?tph in NC [KUw86,Mvv87,CR?93I, the iise
of randomness is the (?nly known tool for solving problems in the given iesource
bounds. In some cases, the intr??diiction of randomness results in a dramatic
increase in cornputati??nal power. For instance, interactive protocols beiwee't a
polynomial time deterministic ma?hine (a verifier) and an all powerftil prover aie
as powerful as NP whereas protoc??ls in which the verifier has access to randomness
are as powerful as PS1?ACE [Sha9()].
The interaction between raiid??rnness and resources such as time, space and
interaction with provers has l?een studied extensively. In this chapter we will
investigate how randomness interacts with another well studied coinputational
resource - the number of queries ill??wed to an NP-complet ??rac]e. The resuli;s
1The results presented in this chapt(?t h.we been drawn from [CKRc?iJ and [Roh92]
12
13
proved in this chapter will lorni the technical backbone for the thesis proposed in
Chapter 4.
Treating the number of queries to SAT as a computational resource gained
acceptance with Krentel's work ?Kre88] on NP Optimization problems. tt is well
known that there is a wide variation in the complexity of typical NP Optiniiza-
tion problems. For instance, solving the Traveling Salesman Pwblem (TSP), i.e.,
finding the length of the shortest tour in a given weighted graph, appears to be
much harder than finding the size of the largest clique in a graph. However. the
decision versions of these problems, i.e., deciding whether there is a tour of a given
length in a weighted graph or deci?ling whether there is a clique of a certain size in
a graph, are all NP-complete and have the same complexity. Thus, the theory of
NP-completeness does not adequately explain the complexity of optimization prob-
lems. Krentel resolved this issue by characterizing the complexity of optimization
problems by the number of SNi???qiieries required by a polynomial time ma?hine to
find the optimal solution. For inst<ince, solving TSP requires 0(n) quefles ?vher??as
computing the size of the largest clique requires only O(log n) queries. Krentel also
proved that problems requiring 0(n) queries cannot be solve?l using only O(l(?gi?)
queries unless P --H NP thus establishing the validity of the number of queries as
a complexity measure.
Often, one is only interested in finding out whether the optinial solution satisfies
some predicate. For instance, Papa?limftnou and Yannakakis [PY84] linked I he
complexity of the facets of the TSP polytope to the class D? which consists of
languages expressible as a differenc? o[ two NP languages. A canonical example of a
language in D? is ? ( I., k ) F(I k) ) where I is an instance of an NP Optiniization
pwblem and P(I, k) is the simple predicate Optimum(I) k. As an example, tbe
language CLIQUE(1) consisting of all tuples ( C, k ) such that k is the size of the
largest clique in the graph G? is D?-c.omplete. One can easily construct language
based on more complex predicates e.g., we could define CLIQUE(5) to l?e the set
14
of all 6-tuples ( C, a?, . . . , a? wh??re the size of the largest clique ilt the gaph C
is one of the five integers a1a? Intuitivdy both CLIQUE( 1) and CLIQUE(5)
appear to be more complex than the typical languages in NP or co-NP and ijt
fact one can easily show that this is indeed the case unless NP co-NP. Also,
CLIQUE(5) appears to be more complex than CLtQUE(1) since it is based on a
more complex predicate. Furtherm??re, since both CLIQUE(5) and CLIQUE(1) are
based on simple predicates, one would also suspect that their complexity shouhi
be less than the complexity of first computing the maximum clique size and then
checking the predicate.
A systematic study of such predicate based languages began with the work
of Cai, Hemachandra [C1186] aiid Wagner [Wag86?. Wagner extended Krentel's
approach to these languages by characterizing their complexity by the number of
nonadaptive SAT-queries requiied to evaluate the predicate Thus, a language
which requires k nonadaptive queries to SAT i.e., a language which ?????tt?reduces
to SAT is placed in the compl??Ix. class pSAT??[ki which is the k'th level of (he
Bounded Query Hierarchy. Thus, ?he complexity of CLIQUE(5) and CLI(?UE(i)
can be characterized by the fact thai the lowest Bounded Query classes iii which
these languages can be placed ar? p5ATIi[1OJ and pSATiI[2] wspectively. An??tlier
closely related way of measuring the complexity of such languages is (0 see how
they can be expressed as a set theoretic combination of a tuinimum number of
NP languages (CLIQUE(5) is a nested difference of 10 NP languages). This can
be viewed as a generalization ol the definition of D? (which consists of languages
expressible as nested difference of 2 NP languages) and it gives rise to the closely
related Boolean Hierarchy [CGII+S8] [Bei91j.
Subsequently, the robustness ?)f these two complexity measures was investi-
gated by many researchers [Kre8S.,Kad88,Bei9l,Bei88,ABG9Oj. Research waC also
conducted on how the usefulness ?)f bounded queries as a resource was affected by
the complexity of the oracle itseli'. [AG88, Bei, GJY87, Bei9 1) C?ha89, ABC 90J.
15
particular significance 10 this work are results that state that, for all constants k,
under usual comple?ty theoretic assumptions, k nonadaptive (adaptive) queries to
SAT are more powerful than k 1 nonadaptive (adaptive) queries [Nre88,lKad88j.
For instance, these results imply that CLIQUE(5) is not in p5ATII[91, unless PIt
collapses.
In light of these separation results, it is natural to ask whether randomization
can be used to bridge these gaps and if so, to what extent. This this chapter we
resolve this question by providing tight bounds on the ability of randomness to
save a nonadaptive query to SAT. We do this by providing tight bounds on the
success probability of random reductions between successive levels of the Query
and Boolean llierarchi?.s. For instance, we will show that any language in J)SAT??[kl
?rmP -randomly to a language in 1)SATII[k--H1] with probabihty of 1 1/[k/2?. If
two-sided error ( ?bpp ?reduction) is allowed then we show that the success j?rob-
ability can be increased to 1 --H 111(k t 1). We will prove that this is the best
that randomization can achieve by proving that it is not possible to increa?3e these
probabilities even by l7po!?, unles? the Polynomial time hierarchy (Pli) collapse?,.
Notice that as k increases, the eri?or probability decreases, thus giving a precise
mathematical justificat ion to otir intuition that, for language recognition, tlie value
of an additional nonadaptive query decreases as the number of queries 1llcre;is(?.
It was not possible to formalize this intuition without randomness because the
deterministic result states that Vk, p5ATt?[kJ ? pSATIJ[k--H1J, unless PH collapses
[lKad88j. Our proof technique is based on the rich structun within the Boolean
and Query llierarchies and relies (?n the important observation that it is possible
to convert arbitrary random reductions between classes in the Boolean llierarchy
into reductions which have very nice structural properties.
Thus, CLIQUE(S) can be rec??ginzed correctly with probability 10/11 using
randomness and only 9 nonadapiwe queries to SAT. Moreover the ran?iomized
computation of CLIQUE(S) ?? p5?TI![9i is simple and elegaut and it is surprising
16
that more complex coniputations c:an't decrease the error significantly, unless PH
collapses.
The results described above hold for languages computable using bounded
queries to SAT. For the sake of completeness, we also examine the ability of ran
domness to save a query in bounded query functioncomputations and prove strong
negative results about the ability of randomness to do so.
The rest of the chapter is organized as follows. In Section 3.1, we provide
the necessary background and state the important properties of the Boolean and
Query Hierarchies. In Sec?ion 3.2 we state our main results. In Section 3.3 we will
show how randomization can be used to reduce harder languages in the Boolean
and Query Hierarchie' to simpler ones. In Section 3.4 we will prove that our
results in Section 3.3 are optimal. First, in Section 3.4.1 we will illustrate the
main ideas behind the optimalfty results by means of an example; the complete
proof for a general case will appear tn Section 3.4.2 and in Section 3.4.3 we state the
results for the other cases wfthout proof. In Section 3.5, we study the (non)alAhty
of randomness to save a query in bounded query function computations and in
Section 3.6 we list some open pi?l?leias.
3.1 Background
First we formally define the Bounded Query Hierarchy.
Definition We write p5AT!I[kJ foi the kth level of the Bounded Query Hierarchy.
The class p5ATII[ki consists of al? languages recognized by polynomial tinie Turing
machines which are allowed at inost k parallei (or non-adaptive) queries to the
SAT oracle.
From the above definition it is easy to see that the k'th level of the Bounded
Query Hierarchy is actually the class of all languages which ??k--Htt-reduce to SAT
In this chapter, we will deal with tlie Query Hierarchy based on nonadaptive queHes
17
and not with the Query Hierarchy based on adaptive queries because the nonadap-
tive Query Hierarchy is just a finer version of the adaptive Query Hierarchy. Infact,
a beautiful result due to Beigel [Bei91j shows that the k'th level of the adaptive
query hierarchy, i.e., pSAT[k] is e?actly PsAT?l2k?iJ.
Results about Bounded Query classes often rely on the structural properties of
the closely related Boolean Hierarchy [CGH+88] which is a natural generalization of
the class D?. Most uninitiated readers, when first confionted with the definitions
of the the Boolean Hierarchy find them to be quite nonintuitive and arbitrary.
However, behind these nonintuitive definitions lies a very rich theory which often
gets overlooked when one uses properties of a specific definition of the Boolean
Hierarchy to prove restilts. Thus, before we provide a specific definition of this
hierarchy which will bE useful in oiir proofs we would first like to give the general
picture of what the Boolean Hierai?ty is all about.
Consider the complexity cl;?s pSATlilk] consisting of languages recognized by
polynomial time machines whid? itiake at most k nonadaptive queries to SAT. In
general, when a machine has niade its k queries to the oracle, then the future
behavior of the machine (acceptance or rejection) can be completely chara??terized
by a boolean function of the n?sj?onses to the oracle queries (or more f?rnially
a truth-table condftion). For a machine making k queries on some input the
acceptance function or truth-table condition could be any one of the 22k boolean
functions on k boolean variables representing the oracle responses to its k parallel
queries! However SAT is a vei? robust oracle language and it is close?l under
boolean operations su?h as ANDs and ORs, i.e., given any collection of bo?Aean
formulae, ??.?? ?k, one can construct a single reasonably sized boolean forniula
? which is satisfiable if and only if aJl (or at le??t one) of the formulae ..... . ,
are satisfiable, respectively. Thus, many of the 22k truth table conditions happ?'i to
be equivalent in the se?se that wii h very little (polynomial time) effort a machine
asking queries P1,.. , ?k with tri?th?table condition T1 could be made to ask a
18
slightly different set of queries ..... Qk and truth table conditioii T2 (where
T2 is in T1,s equivalence class) without changing it acceptance/rejection l?ehavior.
As an example, if a machine asks queries ?..... , Fk and accepts if all the queries
are answered yes then another machine could ask only one query ? constructed as
above and accept if it is answered yes and the acceptance behavior of both machines
would identical. In fact, a beautiful theory based on Hausdorff's theorems on
the boolean closure of set rings shows that, in fact, the 22k possible truth-table
conditions can be partitioned iilt() only 2k different equivalence classes tHau14,
WW85]! These 2k classes are actually composed of k different classes and their
complements. It is these equivalence classes which form the basis of the t3oolean
Hierarchy. For a general p5ATI?[k] computation, the actual equivalence class that
the truth-table will fatl into will depend on the input. However, if a language
in pSAT??[ki is recognized by a machine which uses a truth table from the same
equivalence class on all inputs then we say that the language is also in the l3o?)lean
Hierarchy class defined by that equivalence class. We now formally pr?wide one
definition of the Boolean Hierarchy which will prove to be useful in our resuits.
It is important to remember that his defiuftion actually picks out one i?articuiar
representative from each equivalence class of truth-tables, there are many ??tJier
ways of defining this iderarchy based on other representatives. Let L1, .. ,
denote arbitrary languages. Define tiie operator C as
C(L1) %ef
C(L1, ..., Ln) %ef			C(L1,. .. , Ln?1) U L? if n is odd,
C'(L1,... ,Ln?i)flTT otherwise.
Definition We write BH(k) and co-BH(k) for the kth Jevels of the Boolean
hierarchy, defined as:
BH(k) def fL L C(L1,. . . , Lk) for some L1,. , Lk C NPJ,
def
co-BH(k)			fL L ?
19
Thus BH(1) corresponds to NI? and BH(2) corresponds to D'?. Among the
prominent members of the class 1)P is the language CLIQUE(1) defined earlier
which is <? -complete and the iaitguage of uniquely satisfiable boolean formulas
(USAT) which is easily seen to be in D? but not known to be ?? -complete. Iii
fact, every level of the Boolean Hierarchy has ?? -complete languages including
languages based on important NP Optimization problems [CGH?r88]. For example,
the language CLIQUE(5) defined earlier is ?? -complete for BH(10). From the
definition of the classes BH(k) and co-BH(k) it follows that tbe foliowbig languages
are ?m? -complete for t]ie respective levels of the Boolean Hierarchy:
Definition We write BLk for t'ie canonical complete language for BH(k) and
co-BL? for the complete language for co-BH(k):
def
BL1			SAT,
BL2k def t( x1,.. ,X2k I (w1,,.. ,X2k?1 ) C BL2k?l and X2k C SAT1,
BL2k+l def ?? Xl,...,X2k+[			( xl			,x2k E BL2k orx2k+i c SATf,
def
co-BL1 = SAT,
co-BL2? def t( x1,.. ,x2k ?			Xl,... ,X2k?1 ? E co-BL2k?[ or x2k SAT?,
co-BL2?+1 def ?? ?1,, ,2k+? ?, I ( xl,.. .,X2k ? C C0-BL2k and X2k+I ?
Since NP and co-NP are closed under boolean ANDs and Olis, one can akco prove
the following interesting fact about ianguages in the Boolean flierarchy over NP
sets [CGH+88J.
Fact 3.1 In the definition of tke class Bll(k) we can also assume that the NP
languages L1, ..., Lk are such tbat Lk C Lk??1 C ... G E2 G t1
One of the interesting consequencEs )f Fact 3.1 is the following:
20
Fact 3.2 Let L be any language in BH(k). Then L ?? -reduces to BLk via a
reduction h which has the following property:
Vx,i, (2 < i ? k) 7rjoh(x) ? SAT ? irj?1oh(x) c SAT.
One such It can be obtained by observing that L = C(L1, ... ,Lk), where
L1, ... ,Lk are NP languages such that Lk C Lk?1 C ,.. C L2 c L1. We
can therefore define h(x) = ( Iti(x),... ,hk(x) ) where Itj(x) is the boolean formula
obtained by applying Karp's reduction to the x C Lj? question.
Another fact about tbe Boolean ?ierarchy which will be useful in some of our
proofs is:
Fact 3.3 ([CGH+88], Thin 2.1.2
fLIL=C(Ti,...,T?)for somel?,...,L??NP1=
BH(k)			k even,
co-BH(k)			k odd.
Using Fact 3.3 and the earlier d??iiitftion of the Boolean Hierarchy we can obtain
the following useful charactenzati??n of the classes co-BH(2k ? 1) and co-BH(2k).
Fact 3.4
co-BH(2k) def f L E = il U B u C
where A c BH(2k 2), B E co-NP and C c NP ?,
co-BH(2k t 1) def ? L L = A u B where A c BH(2k) arid 1? E co-NP J.
Proof: From Fact 3.3 it follows that a language L is in co-BH(2k + 1) if and only
if it can be expressed as Gr(L1L2k+1) for some NP languages ...... ,L2k?i.
By definition of the operator C it follows that L c co-Bll(2k + 1) if ai?d only if
L = C(L1,. .. ,T2k)UT2k+l for soi(Le NP languages L1,. . . ,L2k+1. But by Fact 3.3,
c(T1,... ,T2k) is an li?guage in Bfl(2k). Thus, alanguage L c co-BH(2k+ 1) if
and only if L = A u P, where ? BH(2k) an?l B e? co-NP. Xow [et us consid?r
the class co-Bli(2k). J3y definition, a language L E co-BH(2k) if and only if L =
21
psATj[kJ
M
BH(k)			coBH(k)
M
AM			PsATIi[k-1i
Figure 3.1: Tite structure of the Boolean and Query Hierarchies
L2k) for some NP languages ...... , L2k. By definition of operator C is
follows that L ? co-BH(2k) if and only if L C(L1,... ,L2k?1)UL2k ftr NP lan-
guages ..... . , L2k. But C(L1, ffl. ,L2k?1) represents a language in co-BH(2k --H 1)
which can be decomposed into a ltM()n of a language A c BH(2k --H 2) and a laii-
guage B E co-NP as proved eailiet. rf'hU5, a language L c co-BH(2k) if and only
if it can be expressed as a union of a language in BH(2k --H 2), a languag?? in co-NP
and a language in NP.			E
As we mentioned earlier, the l3oi'n?ted Query Hierarchy and the Boolean Hierarchy
are closely related [Bei91]. Iii fact
BH(k) u co-BH(k) c pSA?'?I[ki G BH(k + 1) n co-BH(k + 1).
Figure 3.1 shows the relationships between the various levels of the Boolean and
Query Hierarchies. Both hierarchies are proper unless PH collapses [Kad88]. A
beautiful result due to Beigel [Bei91J shows that the ?? -complete language for
pSATIJ[kJ is just the tag?,?d unioit of the canonical ?? -complete languages of the kth
level of the Boolean Hierarcity, t.e., BLk and co-BLk. We shall call the canonical
p5ATII[k] ?P -complete language BLk ? co-BL?.
(2k + 2)
pSAT II [ 2k+i
A
BH(2k t 1)			_____
22
$
A
M
M
_____			coBH(2k t 1)
A
ATj[ [2k
A
pSAT II [2k--Hi
probability 1 --H			? rp -reduction
k+1 --Hm
probability 1 --H			?`m? -reduction
k
pSAT
Figure 3.2: Optii?ial ?rp and ?bpp reductions
v ?-
pSAT [ki
probability 1 --H k+f
?bpp -reduction
23
3.2 Summary of Results
In this section, we present a summ;u'y of our results on the power and limitation of
randomization in reducing harder languages in the Query and Boolean Hierarchies
to simpler ones. We considered both ?rp and ?bpp reductions between nearby
classes in the Boolean and Bounded Query Hierarchies (26 reductions in all) and
in each case we provide a tight bound on the success probability that can be
achieved by the reduction. Figure 3.2 summarizes these bounds. To obtain each of
these bounds we first proved that reductions achieving these success probabilities
exist. Some of these proofs will be presented in Section 3.3. Then we showed that
there cannot exist reductions which achieve significantly higher (higher by l/po'?)
success probability unless the ?)()lyflo?ial time hierarchy (PH) collapses. Some of
these proofs will be presented in Section 3.4. Our bounds also pmvide upper and
lower bounds on the success probabilities of random reductions between classes
which are further apart. We conj(cture that tight performance bounds exist for
those reductions as well.
3.3
The Reductions
We now show that random reductions can reduce harder languages to simpler ones
with the probabilities shown in Figure 3.2. The ?rp -reductions are simpler than
the <mbPP -reductions l?nt their success probabilities are lower, Lemmas 3.1, 3.2
and 3.3 are sufficient to derive all the ?rp -reductions in Figure 3.2. The basic
idea behind these reductions is to express the harder language as a union of J sets
such that excluding aiiy one of tlies(,' sets from the union gives rise to a simpler
language. Then by randomly excluding one of the sets from the union w( get an
?rp -reduction to a simpler language with error
Lemma 3.1 For any k > 2, BL2k ?rmP BL2k?2 with probability 1--- 1/k.
24
Proof: For all k, it is well known that a language L is in BH(2k) if and only
if it can be expressed as a union of k D? sets tCGH+88]. h? fact this result has
been used as a basis for defining the class BH(2k) in the past. An easy way
to see this is by means of an example. Consider the BH(10)-complete language
CLIQUE(5) described earlier. Just by looking at its definition it is obvious that
it can be represented as a union of the 5 D? sets (Maxcliquesize(C) a?) for
1 ? ? 5. Thus, in general we can decompose a language in BL2k as a union of
k D? sets. If we omit one of the k D? sets in the union, we will be left with a
language in 1311(2k --H 2) which ?rn -reduces to the complete language 13L2k?2. We
can therefore reduce BL2k to BL2k?2 by randomly omitting one of tlie k D? sets
from the union. This type of reduction has a one-sided error of up to 1/k. In the
case of CLIQUE(5), one would randomly exclude one of the 5 D? sets from the
union to reduce CLIQUE(S) to the simpler language CLIQUE(4) with one sided
error of 1/5.			E
Lemma 3.1 immediately im??hes that for any two languages L'i and L2 such
that L1 --H?m? BL2k and BL2k?2 ???`? L2 we have that L1 ?rmP j?2 with ??mbability
1 --H 1/k. Thus, we get the foflowii?g corollary.
Corollary 3.1 BL2k+2 ?rp flL2k, BL2k+2 ?rmP BL2k+1
BL2k+2 ?mrP BL2k+l ? co-BL??4 ?, BL2k+l E); co-BL??+i ?1I?P BL2k+I,
BL2k+l ?co-BL??+1 <:rmp co-BL??+1, BL2k+l ?co-BL??+1 ffil?'P BL2k ? co-BL??,
BL2k+l ?mrP co-BL2?+1, 13L2k4.1 ?mrP BL2k,
BL2k+l ?mrP BL2k ? co-BL??, c()-BL2k+1 ?mrP BL2k+l,
co-BL2?+1 ?mW BL2A ? co-BL2? BL2k ? co-BL?? ?rp BL2k
and co-BL?? ?rmP BL2k with prol?ab?hty 1--H1/(ktl). Also, BL2k ?mrP BL2k?1(?
co-BL???1 and BL2k ??mrP co-BL?? with probability 1 --H 1/k.
Lemma 3.2 For any k ? 1 c&13JJ2k ?mrP BL2k?1 (Th co-BL????i with prnbabiiiiy
1--H			1/(k+1).
25
Proof: For all k > 1 we know fr()m Fact 3.4 that a language L is in co-BH(2k)
if and only if it can be expressed as a union of k --H 1 D? sets (whidi form a set
in BH(2k --H 2)), an NP set and a co-NP set. As an example consider the language
CLIQUE(S) which is co-BH(1D)-coinplete. Assuming that the integers ..... . , a5
are in increasing order, it is easy to see that CLIQUE(S) is the union of 4 D? sets ([
? Maxcliquesize(G) ? a?+1 ] for 1 ? i ? 4), an NP set (Maxcliquesize(G) > a5)
and a co-NP set (Maxcliquesize(C) ? at). From the definition of the Boolean
llierarchy it is not hard to show that omitting one of the k t 1 sets from the union
results in either a language in co-l311(2k --H 2) (a D? set is omitted) or a language
in Bll(2k --H 1) (the co-NP set is omftted) or a language in co-BH(2k --H 1) (the NJ?
set is omitted). Thus, in all case.'?, the language will be in pSAT ![2k--H1] We can
therefore reduce co-BL2? to BL2k I ? co-BL2??i by randomly omitting one of the
k t 1 sets from the union. This type of reduction has a one-sided er?r of up to
1/k t 1. In the case ()f CLIQLF(S) this means that it can be recognized using
randomness and only 9 nonadapti?? queries SAT with one-sided error of 1/6. L
The ?rP?reductions from pSA?II[2k] to co-BL?? and to BL2k?l ? co-BL???i
are based on the fact that the [<.tngiiage BL2k D co-BL?? is complete for pSATJ!12k1
[Bei91l. If a given instance of a pr?blem in pSATlI[2k1 ?? -rediic??s to an instance of
BL2k then we can use the generic reductions from BL2k to co-BL?? and BL2k?] (?
co-BL???i respectively If, on the other hand, the given instance ?? -reduces to an
instance of co-BL?? then the reduction to co-BL?? is trivial and the reductic?n to
and BL2k?1 ? co-BL???i can be obtained by applying the genefle reduction from
co-BL?? to this class. Thus, as a ?or??llary to Lemmas 3.1 and 3.2 we also have:
Corollary 3.2 BL2k (? co-BL2? ?r?P? co-BL2? with probability 1 --H 1/k and BL2k ?D
co-BL?? <mrP BL2k?1 ? co-BL2??i with probability 1 --H 1/k.
Lemma 3.3 For any k > 1 co-Bi???+i ?rmP co-BL2? with probability [ --Ho+
26
Proof: For alt k > 1 we know ftom Fact 3.4 that a language L is in co?BH(2k $ 1)
if and only if it can be expressed as a union of k D? sets (which forni a set
in Bll(2k)) and a co-NP set. Also we know that the class co-BH(2k) consists of
languages expressible as a union of k --H 1 D? sets (which form c? set in BH(2k --H 2)),
a co-NP set and an NP set. Thus, the random exclusion of one of the k D? sets
in the expression for co-BL??+i gives us a probability 1 --H 1/k <?rp -reduction froni
co-BL??+1 to co-BL2?.			E]
Random reductions with tw??-sided error (?bmPP -reductions) are better at re-
ducing harder languages to simplir ones because they are less constrained. The
following lemma along with simple properties of the classes can be used to derive
the ?bpp -reductions in Figure 3.2.
Lemma 3.4 BLk ?bmPP BLk?l Q c??BL??1 with probability 1 --H 1/(k t [).
Proof: Let A denote ihe langu?tg? BLk and let B denote l3Lk??1 t c(?BL??i The
analysis for odd k and even k i., slightly different and we will only deal witlt the
even case. The same i?leas are ap??iicable to the odd case.
Case1: k is even: Let k 2t. Then by Lemma 3.1 we know that A <r?P B via a
reduction R1 with prnbabilfty 1 --H 1 /t. Also by Lemma 3.2 we know that $4 ?rmP R
with probability 1 --H 1/(? t 1) via a reduction R2 Since, R?? B because 5 tlie
class p5AT?i[k?i] is closed under complementation, this also means that -A <rp ?,
i.e., A ?co--Hrp B with probability 1 1/(t t 1) via some reduction !?3.
Now the ?bM)P -reduction 1? fi?m A to B will work as follows: On input w,
with probability t/(2t ? 1), R uses the reduction R1 on x and with the remaining
probability [ (1 + 1)/(2? + 1) ] I? ?tses R3 on x.
Analyszs: If x E A then R can nia1? an error oitly when it chooses to use Ri. If it
chooses R?, then it will err with pr??bability at niost 1/?. So the probability of error
is at most t/(2t + 1) * --H [/(`)t -F l). If x ? A, then 1? can only make an error if
27
it chooses to useR3. So the error probability is at most (t+1)/(2t+1)*1/(t+1)
1/(2t t 1). Thus, 1? is a probabihty 1 --H 1/(k t 1) ?`??? -reduction.
Case2: k is odd. Similar to Case I, details omitted.
Example: Consider the BII(10)-coinplete language CLIQUE(S) which is a union
of the 5 D? sets (Maxcliquesize((;) a?) for 1 ? i ? 5. We can obtain five
simpler languages L1,... , L5 by removing a set from this union. Also as men-
tioned before, assuming that the integers a1,.. . , a5 are in increasing order, the
language CLIQUE(5) is the union of 4 D? sets ([?: ? Maxcliquesize(C) ? a.?+1 ] for
1 ? i ? 4), an NP set (Maxcliquesize(C) > a5) and a co-NP set (Maxcliquesize(C)
? ai). If we take the union of CLIQUE(S) and any one of these six sets then th
resulting language is actually simpler than CLIQUE(5) (in fact it is in PsAT?![9])!
To see this, note that checking thai Maxcliquesize(G) is in a given contiguous
range of values takes 2 queries Checking whether Maxcliquesize(G) is greater
or less than a particular vahie t;ikes 1 query. Thus, CLIQUE(S) requires 10
queries because 5 ranges of siz 1 each (a? --H a?, 1 ? ? 5) have t() t?e checked
simultaneously. The union of CI?[QUE(S) with any of the four D? sets a?
Maxcliquesize(G) ? Q+t has onkv fr?ur ranges that have to be checked and this
requires only 8 queries. If we t??ke the union of CLIQUE(S) with the NP set
Maxcliquesize(C) > a5 then inste?'? of using two queries to check in the range
a5 --H a?, we just need to dieck if Maxcliquesize(G) > a5 and thus we save a
query, Similarly the union of CL!QUE(S) with the co-NP set Maxcliquesize(C)
< a1 requires one less query thaii CLIQUE(S) because the a1 --H al range check
is replaced by the test Maxcliquesize(C) ? al. Thus, we can form six simpler
languages ..... . , R6 by taking tite union of CLIQUE(S) with one of the six sets
whose union constitutes CLIQ1W?'(s). The ?bpp -reduction from CLIQUE(S) to
a language in pSAT??[9J would be to randomly choose one of these eThven simpler
languages ?..... , L5, R1,...,
28
As mentioned befor??, by using I?emma 3.4 and simple relationships between th(?
classes in the Boolean and Query Hierarchies we can get all th? ?bpp -reductions
shown in Figure 3.2. By definition, the ?bpp -reduction of Lemma 3.4 is also (t
reduction from BLk to BLk?1 (I) co-BL??1. Since co-BL? --H?m? BLk and
BLk?1 ? co-BL??i ?m? BLk?1 0 (o-13Lk?1, we get the required ?bpp -reduction
from co-BLk to BLk?1 ? co-BL??1. Also since BLk?i ? co-BL? 1 ?? -reduces to
both BLk and co-BL?, the ?bpp -reductions from BLk to co-BL? `?d vice-versa
are actually ?mbPP -reductions to BLk?1 ? co-BL??1 followed by a ??m -reduction
to the appropriate language. Also, as in the case of ?rp -reductions, the <bpp -
reductions from languages in tiie dass pSATII[k are based on tbe fact that the
language BLk ? co-BL? is ?? -complete for it. Thus, for any given instance of
a problem in pSATII[ki the either tbe generic reduction from I3Lk or the reductio?u
from co-BL? is used. Thus, we caii state as a corollary:
Corollary 3.3 BLk fbmPP co-BLk, co-BILk ?mbPP BLk, co-BL? ??bmPP BLk?lD
co-BLk?l, BLk ? co-BL? ?mbPP i3Lk, BLk ? co-BL? ?bmPP co-BILk and
BILk ? co-BIL? ?bpp BILk?1 0 co-BIL??1 with probability 1-- 1/(k 4 1).
3.4 Proofs of Optiinality
We now prove that the reductft?ns presented earlier are almost optin?al. By almost
optimal we mean that there cannot e?ist reductions whose correct ness probability
is better by l/poly, un[ess the PH collapses. Minor variants of the same techitique
and the relationships between th? various classes can be used to derive all tlie
bounds in Figure 3.2. Since th(? j)roofs of the general cases are qufte tedious we
will first illustrate our technique by means of an example and then provide the
complete proof for a general case.
29
3.4.1 An Example
In this section, we wili prove that the probability 2/3 <rmp -reduction from the
PSAT11[5]?complete language to a language in pSATiI[4J is almost optimal. From the
structure of the Boolean and Query flierarchies (see Figure 3.1), it suffices to prove
that the probability 2/3 ?rp -reduction from BL5 to co-BL5 is almost optimal. The
following theorem asserts that this is the case.
Theorem 3.1 Let L be any language in co-BH(5). tf BL5 ?rmP L with prnbability
2/3 t 1/p(n), for some polynomial p, then the Pli collapses to ??3.
We need some definitions and Jemmas before we can prove this theoreni. Note
that the hypothesis of Theorem 3.1-implies that there erists a probability 2/3 *
1/p(n) ??rnP?reduCti0n from BL5 to co-BL5. Arbitrary ??rnP?reductions from BL5
to co-BL5 are difficult to work with because they may lack structure. However,
we can establish that if there is some ?rmP -reduction to co-BL5 then there is a
<rp -reduction which has very nice structural properties. We call such reductions
nested ?rp -reductions. In general `ve define such reductions as follows:
Definition Let h be a ?mrP -reduction from some language A to BLe (co-BL?) for
some ?. We say that h is a nested .?rp -reduction from A to BLe (co-BL? resp.) if
the following condition holds: For all x, z, i, (2 ? i <:
irjch(x,z) ? SAT ? lri--Hioh(X,Z) E SAT.
The following lemnia based on Fact 3.2 allows us to work with the much nicer
nested ?rp -reductions instead of ?.rbitrary ?rp -reductions.
Lemma 3.5 Let A be any set and let L be an arbitrary language in BH(?)
(co-BH(?)). If A ?rp L with probabihty ?, then there exists a nested ?`m? -reduction
h such that A <?mrP BL? (A ?rp co-BLe, respectively) via h with probability ?.
Thus, if the hypothesis of Thec?rem 3.1 is true, then there exists a ??robabiiity
2/3 t 1/p(n) nested ?rp reduction from BL5 to co-BL5.
30
Notation Henceforth we will ??f??r to this nestedred?ctiou from I?L5 [0 co-BL?
as h. Let r(n) be the size of the random input to h and let q(n?) be the size of
5-tuples of strings in ?O, 11m Let z denote a randomly and uniformly chosen string
of size r(q(m)) and let s denote 17p(q(n?)). For inputs I ( x1x5 ?. where
X5 C ?O, lJm aiid random string z, let hi(I, z) denote rio/i(I. z), i.e., the
i'th component of the 5-tuple h.(I, ?).
Using this notation we can say that for any 5-tuple I ( .......,x5 ?, where
,x5 ? 10,11m,
I ? BI?5 ? Prob,, [h(I, z) c co-BL5] > 2/3 + ,
I c coBL5 ? Probz[h(I,z) ? BL5] 1.
and since h is a nested reductb?n, in addition we can say that for 1 <: z ? 5
hj(I,z) ? SAT			11i(1, ..... ,hj(I,z) c SAT.
The reason for using nestedieductions is that their structural properties allow
us to prove the following poweifil] lemma (Pr??babilfty Recovery [?emma whic?
plays a crucial role in our proofs.
Lemma 3.6 [ Probabilfty Recovery Lemma 1 Suppose BL5 ffiN?mP co-BL5 via h (le-
fined above. Let H2, 113, H4, ft be aiw collection of 4 formulas in ThSATT=? and iet
xl, x2, X3 be any collection of 3 strings in ?O, l???. Then the following propositioi)s
hold:
o+ P1: Let I ( xi,x2,x3,Jh, fJ5 ?, then
( xl,x2,x3 \) ? co-BL3 --? i?r(bz[( h1(J, z), h2(I, z), h:'(f, z) ? ? BL3]
o+ P2: Let I = ( x1,x2,113,L14, H5 ?, then
( x1,x2 ? E BL2 ? Prol)z[( hi(1, z), h2(I, z) ? ? co-BL2] > 2/3 # a.
31
o+ ??: Let I ( x1, H2, H3, H4, H5 ?, then
x1 c co-BL1 ? Prob?[hi(I,z) c BL1i			1.
Proof:
?1: Suppose (xl,x2,x3 ? E co-13L3. Consider I ( xl,x2,x3, U4,H5 ?. By
definition of co-BL5 we know that I c co-BL5 if and only if
( ( (x1,x2,x3')Eco-BL3 or H4cSAT) and H5cSAT).
Since H4, H5 c SAT we know that I c co-BL5. Therefore, by definition of h, we
know that Prnb?[h(I,z) ? BL5] I. Fix land z. For 1 ? i ? 5, let Jj hj(I,z).
We prove the result by showing that /i(I,z) c BL5 implies ( ti,t2,t3 ? c Blj3.
Assume !i(I, z) ? BL5. Then by definition,
( ( ( (t1,t2,t3 \) ? BL3 ) and t4 ? SAT) or ? c SAT).
From the above characterization, if t5 c SAT then ( t1,t2,t3 ? mitst be in
If t5 ? SAT, then since Jt is a n('sfr? reduction, t3 must be in SAT and hence
( t1,t2,t3 ? ? BL3 sinc(?
( t1,...,t3 \) ? BL3 ? ( t1,t2 ? c 13L2 ort3 ? SAT
??: Suppose ( xl,x2 \) E BL2. From the definition of BL5 and tiie fact that
H3, H4, H5 ? SAT, it follows that I ( x1, x2, H3, H4, H5 ? E BL5. Therelou
Prob?[h(I, <%) ? co-BL5] > 2/3 + ?.
Fixanyland zsuchthat 1?(f,z) cco-BL5. For 1 ?? ? 5 Thttj hi([,z) ??
prove the result by showing that ( ti t2 ? ? co-BL2. By definition,
h(I,z) C co-BL5 ? tiK ? C co-BL4 and t5 E SAT
? ( ti14 ? ? co-BL4
? ( ( ( ( 14, ? ? co-BL2 ) and [3 ? SAT ) or 14 ? SAT ).
32
Thus, if t4 ? SAT then ( t1,t2 ? ?nust be in co-13L2. If t4 E SAT, th?n 5inc? It is a
nestedreduction, t2 must be in SAT and hence ( ti,t2 ? Ei co-BL2 since
( tl,t2 ? ? co?RL2			ti C SAT or t2 C SA?.
?3 The proof of ?3 is similar to the proof of `P1 once ?i has been established. E3
Now we can proceed with the prn??f of Theorem 3.1.
Proofof Theorem 3.1: The proof will use the Probability Recovery Lemma in
conjunction with a variant of the ha?d7easyproof technique. The basic kard/easq
proof technique pioneered by I<a?tin [Kad88] and further refined by Chang and
Kadin [CK9Oa] was used to prov( that the existence of ?? -reductioiis l?etween
complementary classes in the B??oiean Hierarchy would imply the existence of an
NP machine which for every length Tn, given a small (polynomial size(t) arnount of
additional information (or advice) would recognize all SAT forniulas of Jeitgth rn.
Apart from the small technicahty introduced by the polynomial siz?d advice -fcr
every input length, this would n?e;?ii that an NP machine could solve co-XP pr??b-
lems and that would collapse the PH. Thus, the basic hard/easy technique rul?s
out ?m?-reductions between complementary classes in the Boolean hierarchy. Our
variation of the hard/easy technique is geared towards proving the impossibility of
having random reductions betw?e'i complementary classes in this hierarchy which
succeed beyond a certain probability. As is the case with the basic proof technique,
our variant is also nonitniform; however we will show that if the hypothesis of The-
orem 3.1 is true, then for every leitgth ni, given polynomial sized advice, one can
construct Merlin-Artkur-Me4?ng<tJn(?s [Bab851 for recognizing all SAT formulas ??f
length rn. A Merlin-Aj?thur-Meriin game is a 3-round game between two players, a
probabilistic polynomial time j?la??r Arthur and an all powerful existential pla???r
Merlin. The game proceeds as fol!??ws: Given an input x which is visible to both
33
players, in the first round Merlin existentially provides a polynornial (in size of
x) sized string mi which is visible to both players. Arthur, in the second round,
randomly produces a polynoinial sized string a which is also visible to Merlin. Iii
the third and final round Merlin again existentially provides a polynomial size?l
string m2. The input x is then accepted if and only if an a priori fixed polyno-
mial time referee machine accepts the string x, ?i, a, m2. A language L is said to
have an Merlin-Arthur??Meilin g?Ime if and only if there is polynomial time referee
machine M such that whenever a string is in L, the probability that the referee
M accepts the ensuing Merlin-Arthur-Merlin game is significantly higher thai' if
the string was not in L. Thus, a Merlin-Arthur-Merhn game a type of iut??ractive
proof in which the number of rouiids is bounded by 3 and all moves are visiblt?.
It has been known for quite sonie time that the existence of such games for SAT
would imply that the I?ll collapses to ?3? [B11Z87,Yap83] and it is straightforward
to show that the same result hoi(ls even with the presence of advice [Cha91j. ??hus,
once we are able to construct ad?ice-based Merlin-Arthur-Merlin games for S??F
given the hypothesis of Theorem 3.1 the conclusion (PH collapsing) woull fi?llow
immediately. Let us n()w proceed with the main part of the proof.
From the hypothesis (f the Thoteni, it follows that for any I ( x1x5
where xl,... ,x5 E ?0,1yrn,
I c BL5 ? Prol)z[h(I, z) e co-BL5j > 2/3 $ s,
I ? co-BL5 ? Prol)z[h(I,z) c 13L51 1.
Using the definitions of BL5 and co-BL5 we rewrite this as
xl) c BL4 or r? E SAT ?
Prob?[ 7r(1,4)oh(I, ) cc)-BL4 and /i5(I, z) E SAT > 2/3 t &,
,X4 C co-Ri4 am X? ? SAT ?
Probz[ 7r(14)oh(I,z) RL4 or h5(J,z) E SAT] 1.
34
Case 1: Suppose, the following condition C1 holds:
C1: Vx5 E SAT=m, ?x1,... , X4 C ;o, 11rn such that for I ( W1,. .. , X5 ?,
Prob?[h5(I,z) c SAT? ?> 1/3.
Then we can set up a Merlin-Arthur-Merlin game for SAT formulas of length
m as follows: Given a formula x5 of length rn, Merlin first provides x1...., x4.
Arthur then provides the randora and asks Merlin to show that h5(I, z) E SAT.
If x5 ? SAT, then condition C1 e1'?s1tres that by a suitable choice of ..... . , X4,
Merlin can succeed with probability > 1/3. If on the other hand, X5 C SAT, then
irrespective of what X1,. . . ,X4 15, I E BL5 and by the definition of h, h5('I, z) F
SAT with probability > 2/3 + ?. Thus, Merlin can succeed with i?robability at
most 1/3 --H & in this case. This ??r??babllity difference of ? is enough to distinguish
between the two cases.
llowever, Ci may not hold, ?.e., it may be the case that ?x5 E SAT=? such
that Vx1,.. . , X4, Prob,[h5(I, z) E SAT] ? 1/3. We then call tlie least such x5 as
H5 and assume that it is pr?widecl as advice and proceed to the next case. N??te
that H5 E SAT.
Case 2: Given H5 we know tl?at frr any 5-tuple I ( x1,. .. ,x4,H5 ), where
X1,... ,X4 ? ?0,11m
,X4 c BL4 or H5 ?- SAT ?
Prob?[ ir(1A)?h(i, z) E c??-BL4 and h5(I, z) c SAT ] > 2/3 + ?,
(x1,...,x4??co-BL4andTh5?SAT =5
Probz[ 7r(1A)?(1?2) F RL4 or h5(J, ?) E SAT]			1.
35
Since we know that H5 c SAT an?l Vx1,. .. ,X4, Prnb?[h5(I,z) c SATi ? 1/3, we
can simplify the above expression to get
xl,... ,X4 E BL4 ? Prob:Ir?i4?oJL(I,z) c co-BL4j > 2/3t?,
( ..... . , X4 ? co-BL4 ? Pm?bz[r?i4?oh(], z) E BL4j > 1 --H [/3 2/3.
Note that we now have a weaker reduction at one level lower in the Hoolean
Hierarchy. Again by unfolding I?he definition of BL4 and co-BL4, we can restate
this as
Xl,X2,X3 ? ? BL3 and X4 e SAT ?
Probz[ 7r(1,3joh(I, z) E: co-RL3 or h4(I, z) ? SAT 1 > 2/3 t ?,
x1,x2,x3 ? c co-BL3 or ?? c SAT ?
Prob?[ 7r(1,3)oh(I, z) E 13L3 and h4(I, z) Q- SAT J > 2/3.
Now, if condition C2 holds then jusi <ts in Case 1, we can design a Merhit-?rthui-
Merlin game for SAT formulas of l?ngth m:
C2: Vx4 E SATrn, Bx1,x2,x:? ? to,llm such that for I ( x?4,H5 \),
Probz[h4(I,z) c SAT]> 1/3??/2.
However, even C2 may not hold i.e., it may be the case that ?X4 C SAT=m such
that Vx1, x2, x3, Prob?[h4(I, z) ? SAP] ? 1/3 + r/2. We then call the least such
4 as H4 and assume that both H4 and H5 are provided as advice and proceed to
the next case.
Case 3: Using the properties of H4, we can simplify the expression we had in
Case 2 to: Given any 5-tuple I x1,x2,x3,H4,H5 ?, where Xi,X2,X3 E ?0,11rn
x1,2,x3 ? ]3L3 ? I)rM?[r?13?oh(I,z) E co-BL3] > 1/3+ r/2,
1, 2, 3 F co-BL3 > Pr()bz[r?1,3??lL(I z) C BL3] > 2/3.
36
Note that we now have a very weak random reduction between tbe classes Bll(3)
and co-BH(3). Due to our analysis. the reduction h appears to have lost a lot of
success probability. However., since h was a nestedreduction, we can recover some
of this lost probability because proposition ?i of the F?vbabiJ?ty J?e???;eru Le??na
is applicable and we actually have the following:
( xl,x2,x3 ? ? BL3 => Pr()b?[??1,3?ah(I z) ? co-BL3] > 1/3 t &/2
xl, x2, X3 E co-BL3			Probz[?r?i,3?oh(I, z) c BL3]			1
Even this reduction is not very powerful. In fact there exists a probability 1/2,
<rmp -reduction from BL3 to co-BI?3, without any assumptions! However, we can
still obtain our result because the ?ednction based on h has the potential for laige
amounts probability recovery fi?om propositions P2 and ?3 of the Probability IQe-
covery Lemma.
As usual, by unfolding the defiiiitions of BL3 and co-BL3 we obtain: Given any
5-tuple 1 = ( x1,x2,x3,H4,H5 ?, where x1,x2,x3 ?
xl,x2 ? E BL2 or x3 C SAT			?
Probz[ 7r(1,2)4?(I, z) c co-?L2 and h3(I, z) E SAT > 1/3 H- /2
(Xl,X2 ? ? co-BL2 and x3 E SAT ?
Prob?[ 7r(l,2)oh(I, z) E l3L2 or JL3(I, z) c SAT ] = 1.
Now, if condition C3 holds then just as in the earlier cases, we can design a Merlin-
Arthur-Merlin game for SAT fr?i??iilas of length m:
C3: Vx3 E SAT=m, ?x1,x2 E f(), 1?m such that for 1 = ? x1,x2,x3, H4,H5 \),
Pwbz[h3(I,z) ? SAT] >2/3.
However, even C3 may not hold i.e., it may be the case that 3X3 E SAT=rn such
that Vx1,x2, Probz[!t3(I,z) c SA'?[i 2/3. We then call the least such x3 as [13
and assume that H3, 114, 115 are pt?wided as advice and proceed to the next case.
37
Case 4: Using the properties of H3 and proposition ?2 of the Probabllfty Recovery
Lemma, we can now obtain that: Given any 5-tuple I ( xt,x2,H3,H4,H5 \),
where xl,x2 C to,llm,
( xi, x2 C BL2 ? Prob?K?i?2?oh(I z) ? co-BL2] ? 2/3 +
xi,x2 ? ? co-BL2 ? Probz[r?i,2?oh(I,z) C BL2] ? t/3.
By unfolding the definitions of ?J?2 ?ind co-BL2 we obtain:
xi ? SAT and x2 E SAT ?
Pwbz[ hi (1, z) ? SAT or h2(I, z) ? SAT ] > 2/3 t ?
xi ? SAT or x2 ? SA? ? Pm?b2I ht(I, z) E SAT and h2(i, z) E SAT] > 2/3
Now, if condition (? hokis then just as in the earlier cases, we (?an design a
Merlin-Arthur-Merlin game for 7Ar formulas of length m:
C4: Vx2 E SAT=rn, ?xi c ?0,11rn ?tch that for I ( x1,x2,H3?1J4, U5 ?
Probz[h2(I, z) ? SAT] > 2/3 + ?/?!.
However, even C4 may not hold i.e., ?x2 C SAT=rn such that Vxi, Probz[h?(I, z)
SAT] ? 2/3+&/2. We then cdl th? le<?st such x2 as H2 and assume thai; 112,. . , FI5
are provided as advice and procee?t to the final case.
Case 5: Using the properties of H2 and proposition P3 of the Probabilfty Rec?wery
Lemma, we now obtain that: Given any 5-tuple I ( x1H2,..., (15 ?, wheic
? ??, 1ym,
x1 ? SAT --H--H? I?mb?[hi(I,z) c SAT] >
x1 ? SAT --H> J?mb?[hi(I,z) C SAT]			1.
We now have an Arthur-Meriin game for SAT=rn given advice 1(2,... , H5 and
we are done.			EJ
38
3.4.2 Proof for a General Case
To illustrate how one proves lower bounds on error probabilities of random reduc-
tions in the general cases, we prove the result for ?rmP -reductions from languages
in BH(2k) to languages in co-BH(2k). As shown earlier, it is possible to reduce
any language in BH(2k) to a language in co-BH(2k) via a probability 1 --H 1/k
?rmP -reduction. The following theorem shows that the probability bound is almost
optimal.
Theorem 3.2 Let L be any language in co-BH(2k). If BL2k ffi?mP L with probability
1 --H 1/k t 1/p(n), for some polynomial p, then the PH collapses to ??3
We will need some definitions <?n?i lemmas before we can prove this theorem.
The hypothesis of Theorem 3.2 iniphes that there exists a probability 1 --H ilk ?
1/p(n) ?rp-reduction from BIL21,. to co-BL2k. However, by applying Lemma 3.5 we
obtain that there must exist a probability 1 --H 1/k $ 1/p(n) nested ?rpreduction
from BL2k to co-BL??.
Notation Henceforth we will refir to this nestedreduction from BL2k t( co-BL??
as h. Let r(n) be the size of tbe random input to /? and let q(m) be the size c?f
2k-tuples of strings in fo, 1Jrn, I?et z denote a randomly and uniformly chosen
string of size ?(q(m)) and let ? denote 1/p(q(m)).
To understand the importance of nested ?rp-reductions one needs to look at
a rough overview of our proof: As in the example, the proof is nonuniform; we
consider every length. A randoni ieduction between two complementary classes in
the Boolean Hierarchy with the ?tp?)ropriate success probabilit5 may either result in
an adverse structural consequence "or the given length or induce a weake?random
reduction between the two complementary classes one level below. This argurnent
can be used recursively and terminates when one reaches tl?e lowest level of the
hierarchy.
39
If we start with an arbitrary reduction, then the probability loss while going
down the hierarchy is so great that we need to start with a probability much
above the bound (roughly 1 --H 1/cxp(k) + 1/poly instead of 1 --H? t/k + t4)oly)
in order to cause an advers? str?ctural consequences at the lower leve[s of the
hierarchy. However, if we use a nested reduction then the structural properties
of the reduction allows us to use the Probability Recovery Lemma to recover
some of the probability lost while going down the hierarchy. At intermediate stages
of our proof we deal with indticed random reductions between lower classes in the
Boolean Hierarchy which work wit it certain probabilities. In niany instances there
exist better reductions betweeii these classes without any assumptions! We can
still prove our result beca?se the reductions induced by the initial nested redu?tion
have the potential to re(:over large amounts of lost probability as the proof proceeds
whereas the existing reductions between the classes don't. Thus, by using a nested
reduction we don't need to start with very high success probability and we can in
fact obtain tight bounds.
Lemma 3.7 [ Probability Reccw??ry Lemma Suppose BL2k ?r?P1 :o?BL21 via h
defined above. Then the foliowiiig prnposition ?j holds for all j, () ? ? --H
Proposition??: Let x XjX1 be any collection ofj formulas in SAT m
for ally yi,...,y? C fo,ljmxt (where ? 2k --Hj):
Ifj is odd:
co-BLe ? Probz[r?1e?oh(( ?ffl ? \), z) c BLel			1.
If j is even:
C BLe ?- Probz[it?i??oh(( ?ffl x \), z) c co-BLe] ? 1 --H 1
- +5.
k
Proof: (by induction on
Basecases??&?i: These follow directly from the hypothesis of Leinma 3.t and
the definitions of BL2k and co- BL2k.
40
Assume??,Inductioncase?j??: We treat the odd and even cases separately.
Case 1: j is odd. Since ?? holds we know that for any collection of j formulas
X=Xj,...,Xl in SAT=rn and for all Y=YiYeE to,1tmxC?where?2k?ji:
co-BLe ? Prob?[r?ie?oIi(( j, ? ?,z) E BLe] 1.
Therefore, for any given set of 5+2 formulas X' Xj+2, .?. ,Xl C SAT=m, by setting
Ye--Hi Xj+2 and Ye Xj+i we have for all Y Yi,. , Ye--H2 C ?O, 1?rnx(C--H2),
( V Xj+2, Xj+i \) E co-BLe ? ProbzK?i,e)Ch(? Yffi ? ), z) E BLe]
Since both Xj+2 and x3+i are iLl S??T it follows from the definition of co-BLe (? is
odd) that
(Yffi Xj+2, Xj+l ) E (o?BLe V) E co-BLe?2
and thus we have that
We claim that
V ) ? co-BLe?2 PJobz[ir?i,e?ch(( Yffi W ), z) c BLel
7r(i,e)oh(( Yffi X ), z) ? BLc ? ir?i,e???ofl(( V X ), z) c BLe?2.
(3.1)
(3.2)
Proof: Let us denote the ?tupIe `r(?,e)oh(? Vffi X ), z) as ( hjhe ). To ??rove
equation 3.2, let us assume that h1,. he ) ? BLe. We show that ihis means
that ( h1,... , he?? ) c BLe?2. By the definition of BLe for odd ? we know that
since ( hi,... ,he ) E BLe,
((( h1,. ..,he?? ) ? Bl???:?) and he?i ? SAT) or he ? SAT.
Now if he E SAT then it must be he case that
((( h1,.. . , hp2 E BLe?2) and he?i E SAlT),
41
which implies ( h1h?? ) c BLe?2. If on the other hand, he ? SAT, then,
since h is a nestedreduction, we know that he?? c SAT. Note that 5+ 2 ? 2k ?
--H 2) > 1. If (? --H 2) = 1 then 4hc4 means that
(hi,...,he?2 )			(h1 ) ?BL#2=BLi
since h1 ? SAT. If, on the other hand, (? --H 2) > 1 then we know that since
( h1,. . . ,he?2 ? ? BLe?2 ? ( hi,... ,he?s ) ? l3Le?3 or h?2 ? SAT
and since he?? ? SAT, ( hi...., he?2 must be in BL?2.
This proves equation 3.2. Therefore, by equations 3.1 and 3.2 we establish W'j+2
for odd 5, i.e.,
Proposition?j+?: For any collection of 5+2 formulas, ? = X5+2,. . , xi iii SAT=m
and for all y = Yi, , Ye--H2 ? to, lyrnx(e--H2) (where ? = 2k --H5):
? co-BL??2 ? Probz[?r(i,e?2?0h(( yffl ? ?,z) ? l3Le?21 = 1.
Case 2: 5 is even. The proof of this case is very similar to that of Case 1, and
hence omitted.
Thus, we have proved the lemma by induction.
We now use a variant of the haul/easy proof technique [Kad88] to prove the
main theorem. We first define a hardsequence of forniulas.
Definition Suppose BL2k ?rmP C0--BIJ2k via h. Then, we call (1rn,xj.... ,xi
( 1?, x a hard sequencewith respect to h if 5 = 0 or if all of the following hold:
1. 1 ? 5 ? 2k --H 1.
2. IxjI=m.
3. Xj ? SAT.
4. ( 1?,xj?i,... ,xi is a harci sequence wfth respect to h.
42
5. Forall?--H--Hy1,...,?? E ?0,1]rnx (where?=2k--Hj),
[j/2J
Prob[ ir+ioh(( yffl 5), z) c SAT] ?			k			+ (I mod 2) *
2
If ( 1rn,x?,. . . ,xl ) is a hard sequence, then we refer to it as a hard sequeiice
of order j for length n?. Also, we call a hard sequence ?aj4ma1 if it cannot be
extended to a hard sequence of higher order. The following leinnia shows that
given a nested ?rp -reduction from BL2k to co-BL2?, a hard sequence of order j for
length m induces an asyminetric probabilistic reduction from BL2k?5 to c0?BL2k?j
for tuples of strings of length nt.
Lemma 3.8 Suppose BL2k <L? c()-BL2? via h. Then, the following proposition
Qj holds for all j, 0 ? 5 ? 2k --H 1:
Proposition Q?: If ( lrfl,x5,.. ,xl ( 1m,5, ) is a hard sequence w.r.t h, then
for all y yi,..., ?e E ?0, 1J?>'? (where e 2k --H 5):
If ? is even:
( y) ? BLe ? Prob?[ n'(1j)Qh(( ? 5,), z) c co-BLe 1 ? 1 --H --H` + ?,
k
(y) Cco-BLe ? Prob2[m1,??oh((? 5'),z) ?BLe] ?> 1--H#k
If ? is odd:
?) E co-BLe --H> Prob2[ Th'l,t)oh(( j, 5' ),z) ? BLe 1 1,
(ij) CBLe ? Probz[ir(t,eh((yffl 5'),z) Eco-BLe] ? 1??T+J +-?
Proof: (by induction on 5)
BasecaseQo: This follows trivially from the hypothesis of tlie leinma.
InductionCaseQ?+i: Suppose Qj holds. Let  2k --H 5 and let ( irn, x1)
( 1m, Xj+l,... , xl ) be a hard sequence. Consider the cases ?`here ? is (?V?I or odd
separately.
43
Case 1: ? is even. Since ( 1rn, &7?) ?` 1m, Xj,.. . , x1 ) is also a hard sequence, by
the induction hypothesis, for alt y ?i,... , c ?O, 1 jrnx?,
? BLe ? Prob?[ r(i,()4?(( ?, x ),z) c co-BLe ] > 1 --H --H + s.
k
In particular, for Ye Xj+? and y! Yi,???,Ye--Hi we have
( Y', Xj+l ? ? BLe ? Probz[?i,e?oh?(( Y?? A ),z) c co-BLel > 1 --H
--H + ?.
k
Using the definitions of BLe and co-BLe for even ?, we have that for all Y?
Yi, , Ye--Hi C ?O, 11mx(?--H1),
C BLe?i and Xj+l C SAT ?			(3.3)
Probz[r?ie?i?oh(( Y? A ?,z) c co-Bl??1 or reoh(( Y?? A ?,z) E SAT] >
Since ( 1?,xj+i,... , xt ) is a hard sequence, we know condftions 1 and 5 of the
definition hold. That is, Xj+J C SAT and for all Y? Yi,???,Ye--Hi C ?O, 11rnx(?i)
Probz[ ?e?h(( y?, A `,, ?) C SAT] ? [(j+1)/2J $ (3.4)
k			2
(since j is even, (j + 1) mod 2 is]).
Now we can establish Qj+i. If \( Yi,			, Ye--Hi ) C BLe?i, then by equations 3.3,
3.4 and the fact that Xj+i E SAT, we have
Probz[ Th;i,e?i)W(( 2 A ?,z) c co-BLe?i
> 1 --H 1			_ [(j+1)/2J _ --H? = 1 --H )+2 + s
--H			-- +			k			2			2k			2
k
(since j is even, [U + i)/2J = )/2 ).
If on the other hand, ( Yi, o+, Ye--Hi ) C co-BLe?i then by conditions 3 and 4 in
the definition of a hard sequence, we know that x1,.. .,X5+1 C SAT. Since h is a
nested ?rp -reduction, by a direct application of the Probability Recovery Lemnia
we know that in this case
Probz[ ?(i,e?j)0h(( Y? A ?,z) ? BLe?i ] = 1.
44
Thus, we have proved Qj+i for 4h( case when ? 2k --H j is even.
Case 2:  2k --H j is odd. Usiiig a proof similar to the proof of Case 1 we can
show that Qj+i holds in this case as well. This completes the proof of the lemma.
The next lemma states that if BL2k ?mrP co-BL2? via h, then a rnai'??a1 hard
sequence for a given length ?? atlows 115 to differentiate between the cases y e SAT
and I) ? SAT, where Y is a formula of length m.
Lemma 3.9 Suppose BL2k ?1??co-I3L?? via h. Let ( lrn,W5 xi --H ( 1m_
be a maximal hard sequence with respect to h. Define  2k --H? j and let y?
Yi, ,Ye--Hi denote an arbitrary (? --H 1)-tuple of strings of size rn. Then,
y ? SAT ?
Prob?[ :reoh(( WI, Y? X ?, z) SAT ] > [(i+1)/2j
_			k			+ ((1 + 1) mod 2) *
2
and
SAT ?
Probz[ ?rcoh(? W'? Y x) ), ?) ? SAT ] ? [(i+1)72; -- (5 mod 2) *
k			2
Proof: If 5 2k --H (Y? is the empty sequence), then, by Lemma 3.8, for all
? ?o, itm
and
YcSAT ? Plobz[rioh((Y, x\),z)ESAT]--H1
y ? SAT ? Pmb (rioh(( Y ? ?, z) ? SAT 1 >??2.
Thus, the lemma holds when 5 2k --H 1. Now consUer the case when 5 ? 2k --H t
Let --H--H 2k--H5.
Suppose y c SAT. Since ( 1?rn,x? `ri ? is maximal, /\ trn,Y,xj, . ,zi
is not a hard sequen(e. How?w??r, 5 + 1 ? 2k --H 1, y' mq E SAT and
45
( 1?,x5,. . . ,x1 ? is a hard sequence. So, ( tm,y,x5,. ,x1 ) mi?t fail to be a
hard sequence by failing to satisfy condition 5 of the definition of hard sequences.
Thus, we get the requiied result.
c ?O, 1ymx(e?1),
Prob?[ ireoh(( I)', u, x ?, z) ? SAT 1 > ???+k1)/2J t ((5 t 1) mod 2) *
If on the other hand, y E SAT then by by Lemma 3.8 we know that fer all
y Yi, , Y?--Hi ? fO, [1m?C?1:
If ? is even:
( ?,y ? c co-BL ? Prob?? 7r(i,e)oh(( #, ?, x ?,z) ? BL 1 > 1-- fTt
and if?is odd:
(y?,y? ?BLe ? Prnbz[r(ie)ch?(y?, u, w?,z) Eco-BL?] ? 1 ?+?
2k			2
Now let us consider the eveii ai?d odd cases separately. If ? is even. then by ibe
definition of co-BLe, we know tltat ? E SAT implies that for all `g' yi,...,
( y?, y ) c co-BL?. Therefore, we b.?v? that
v ?? Pfl)bzK(l,)oh(\ ???			x ?, z) ? BLel > 1 --H __
2k
By the definition of BL? for even ?, we know that ( u1.... ,u? ? E BL? ? zi' E SAT.
Thus, we get the desired result
Vy?, Probz[ir?ch((.V, y,			5
x\)z)CSATj>l?2k
Vy?, Probz[rech((y?, y, x?,z)?SAT] ? 5 LS+l)$2?J+(smod2)*ffi2.
_ 2k k
If ? is odd then using a very similar reasoning as in the eveii case we can get the
desired result, i.e.,
& _ [(5s1)/2J
V y' Prob?[ 7rcoh(( y?, y, x ?, z) SAri ? 5+J + --H --H+? mod 2)?ffi.
2k			2			k			9
46
This completes the proof of the Lemma.
ID
Now we are in a position to prove the main theorem:
Theorem 3.2 Let L be any language in co-BH(2k). If BL2k ?rmP L with prol?Thility
1 --H 1/k + 1/p(n), for some polynornial p, then the PH collapses to Y'?3?
Proof: By Lemma 3.5 we know that BL2k ?rp co-BL2? with probability 1 --H lIk +
1/p(n) via the nested ?rp -reduction h. Thus, Lemma 3.9 is applicable. Given
h, let f be the advice function which on input om outputs the lexically smallest
ma?mal ha?sequence for length rn.
We define an NP machine N which on input ( F, a,1),z does the fo1low-
ing. Suppose a is of the form ( lrn,.U,. . . ,x1 where Xj IF n? and sup-
pose that 1) is of the forin (1)1,.. ,1)2k--H1 ) where y? nt. Then, N ac(:epts
iff ir2k--Hj011(( 1)1, , 1)2k--Hj--H1, L\, Xj . . ,xi ), z) ? SAT. It is easy to see that if
a f(01F1) is of order j then by Lemma 3.9,
F C SAT? By, Prob?[Naccepts( F,Q1),z \)? > ftU+1)/2J +((j+i) mod 2)*?-
k
and
[(5+1)1'2J
F E SAT ? Vy, Probz[ N accepts ( F,Qy, z ?\ ] ? k - --H? (5 niod 2) * 2'
This shows that th?re exists a rtonztniform?lerhn-Arthur-Merliu game [Bc?b85]
for SAT. The existence of such games for SAT implies that the Pli coll??s?s to
?P3 [BHZ87,Yap83,Cha9lj.			L
3.4.3 Other cases
In the previous section we saw a complete proof of the optimality of the proba?ility
1 --H 1/k ?rp -reduction from BL2k to (`o-BL2k. With minor modification', the same
proof technique can al?o be ?ised t() establish the optimality of rhe ?rp and :ffimbPP
47
reductions between complementary classes in the Boolean Hierarchy. We therefore
state these theorems without proof.
Theorem 3.3 Let L be any language in BH(2k). If co-BL2? ?mrP L with probability
1 --H 1/(k + 1) + 1/p(n), for some polynomial p, then the PH collapses to ?3?.
Theorem 3.4 Let L be any language in co-BH(2k + 1). If lBL2k+1 ?rp L with
probability 1 --H 1/(k + 1) + 1/p(n). for some polynomial p, then the Pil collapses
to ??3
Theorem 3.5 Let L be any language in BH(2k + 1). If co-BL2?+1 ?rp L with
probability 1 --H 1/(k + 1) + 1/p(n), for some polynomial p, then the Pil collapses
to ??3
Theorem 3.6 Let L be any language in BH(k). If co-BL? ?bpp L with probal?iUy
1 --H 1/(k + 1) + 1/p(u), for some polynomial p, then the PH collapses to
The optimality of all other reductions in Figure 3.2 follow as corollaries to i hese
basic theorems on the optimality of the random reductions between complementary
classes in the Boolean Hierarchy. i?br example, the probability I --H l/(k + 1) ??P -
reduction from BL2?+1Oco-BL2?+t to BL2??co-BL2? must be atmost optimal (i.e
its success probability ?annot be improved by even l/pol?) otherwise we would get
a probability 1 --H 1/(k + 1) + t/pol'? <zmrp reduction from BL2k+l to co-BL2?t1 and
that would cause the Pll to collapse according to Theorem 3.4
3.5 Randomization and Bounded Query
Functions
In view of the results presented earlier, a natural question that arises is whether
similar results also hold for fu??ct?ons computable using bounded queries to SAT.
In this section we addiess this ??)51tC and provide strong evidence that randomness
is not very useful in saving querie:3 in this case.
48
In order to make the above q?estions mor( precise we iirst define BollJLd?ft
Query function classes ;tnd the notion of computing function probabilistically Using
bounded number of qu(?fles.
Definition [AG88,Bei9l] lf A is a set and k E AT then PFkA.?7 is the cla'?s of
functions that can be computed by a polynomial time oracle Thring machine that
can make at most k queries to the oracle. If the machine is only allowed to query
the oracle nonadaptively, then the corresponding class of functions is denoted b?
A
PFk?tt
In order to allow fi?r a randomized bounded query function computation w?
shall define the notion of a polynomial time randomized bounded query (PRBQ)
machine and the functions computed by such machines.
Definition A PRBQ machine ?s a polynomial time oracle Tunug machine ?hich
has access to a source of randomne?.', and can query its oracle 4 a bounded number
of times. On an input .`c, the machine first obtains a uniformly chos??n, polynon?i0J
sized random string r and then bc??e([ on x and ? it queries the oracle a bounded
number of times. At the end ol this computation it outputs a string g(?, ?;.
Since the output of the machirt? ?iepends on the random string `r, it may nc?t be
a function of x. How?wer, if tbeie is a ftincti??n f such that for (very in pitt ??,
the machine outputs f(x) witIi puobabllfty > 1/2, then we say that tbe PkBQ
machine computes f-
We say that a given Pl?BQ machine C computes a function f with probaI)llfty
6 (6 > 1/2), if for all iitputs x, Ci? ?)lltputs f(x) with probability at least 6.
Definition For a set A and k E AT, we say that a function f is in ?PFkA?TI61 if
there is a PRBQ machine with oracle A which computes f with probabitit? 6 (i >
1/2) and makes no more than ? queries to the oracle. If, in addition, the PRBQ
machine always queries the oracle nonadaptively then f is also in RPFj)?t1, [6].
First we show that a PliRQ nachine can trivially compute any fun?tion in
49
PFkSA?TT (PFSkATtt) with probability 1/2 t 1/exp using only k --H 1 adaptive (nonadap-
tive) queries to SAT. Note that k need not be a constant, it could be any functioii
of the input.
Lemma 3.10 Any function f ilt l)??SkA?TT
RPF(Sk%%)?T?1/2 t 1/2P(?)] (respe?:tively
the input size and n is a polynomial which depends on
(PEkS%ft) is also in the class
R?PFS(k%%)?tt[l/2 t 1/2P(?)1) where n is
Proof Outline: We can simulate the machine computing f and instead of making
one of the k queries to SAT we can randomly guess the oracle response. This wa?y
we will compute f correctly with probability > 1/2. To achieve a correct ness
probability greater than 1/2 by an inverse exponential amount we can use the
fact that if a query F ? SAT. ?hen with inverse exponential probability we can
randomly guess a satistying assiugment of F.
The next theorem provides str':?ng evidence that this is the best that randonj-
ness can achieve.
Theorem 3.7 Let 9 l?e an incre<Lsing integer valued function such that g(n)
O(log n) and let p be any polynomial. Then there is a function in PFSqA(j\?ft which
is not in R?PF?(g(n)?i)??[1/2 t i/p(n)1 for any oracle X, unless PH collapses.
Proof: Before we pro?? this theorem we shall need the following definition:
Definition [AG88] If A is any set and k E K then
A(x1).A(x2) . .. A(xk)
where ... denotes the ?`.oncatenati??n of bits and A(x) is the characteristic function
of A, i.e., A(x) 1 if x ? A, 0 otherwise.
Our proof of Theorem 3.7 U5(5 the following version of a theorem pioved in
[ABG90l.
50
Lemma 3.11 [ABG9OJ Let It(n) be any polynomially bounded function )f ?i. If
there is a function w in PF/poi.q such that on input t ( xl, x2h(n) ?` w(t)
is a h(n)-bit string sucl? that, w(i) $ F?n)(X1,X2,.. , Wh(n)), then A c NP/po1? F'
co-NP/pol?.
We now proceed with the proof of Theorem 3.7 Suppose, for some
O(log n), it is the case that any fun?tion computable in PF9SA(flT)?ft is also coinputal?le
in R?PFX(g(n)?l)?T[1/2 ?- 1/p(n)] with for some oracle X and polynomial p.
Let h(rn) g(rn2). Clearly for large rn, h(m) ? m. Thus, for sufficiently
large m, the size of a collectioii of /t(ni) boolean formulae of size m each, i.e.,
Xl, . . . , Xh(m) ?, will always be less than ?2 Let pad(x1, w2, . . . Xh(?n)) denote
a padded collection of h(?t) formulas ( xl, ..., Xh(m) ? of size m each, such that
the size of the padded collection is exactly m2. Define a function T, which on
input of the form pad(x1, x2, Xh(m)) outputs FhSA(m% (x1 x2, ... , Xh(rn)5.
It is easy to see that f??r an ?t-sized il?pnt of the correct form T can be computed
using only h(#n) g(n) quen'e? to ?AT. Thus, T F PFgSA(flT)??? and therefore, by
assumption in IiPI'X(9(?,)?l)?T[l `(2 ? 1/p(n)] for some oracle K and polyn??mial ]).
Let Al be the PRBQ machine con?pl1ting I with probability 1/2 -? 1 /j?(n), using
only g(n) --H 1 queries to X.
On input I pad(xi, x2rh(rn)) of size n m2, M obtains a rand??m
string r and it outputs 1(I) with ??robabihty 1/2t 1/p(n) and makes no more than
h(m) --H 1 queries to X. Since h(?) O(logn), it is possible to completely expl?re
the entire query/computational tree )f M on I and random string ?r in polyn??mial
time. Since there are h(m) --H 1 oracle queries in this tree, it has 2h(n?)--H1 leaves and
the value output by M on I anci ? is one of the 2h(rn)--H1 possible values which are
computed at these leaves.
Let Si(r) denote the set c)f val?ies output at the leaves of M's computation tree
on input I and random string `r. (?leaHy, Vr, fS1(?) ? 2h(m)--H1 and Prol)r['T(I) c
S1(r)] > 1/2 + l/p(n).
51
Choose c(n) = 2*[(p(n))2*n2J4?i strings ?l,.. ?c(n) independently at random.
By standard prnbabilii? amplification techniques [Sch89], it can be sho??n that
1(1) would belong to a majonty of the sets S1(r1),... , SI(%(n)) with prol?abllIty
more than 1 --H 1/2fl2 Thus, for every possible input J of size n, when stririgs
ri,..., ?c(n) are chosen independently at random, the probability that 1(J) belongs
to a majority of the sets Sj(ri ..... SJ(%(n)) is more than 1 --H 1/2fl2 But there
are at most 2? inputs J of size n. Thus, there is a sequence of random strings
..... . , Rc(n), such that for all J of size n, 1(J) belongs to a majority of Ihe sets
Sj(Ri),... , SJ(I?c(n)). Let this sequence of random strings be encoded into the
advice function 2, which outputs ?i, ... , Rc(n) on input O?.
On input J = pad(??i, x2, ..			Xh(m)) of size n and given advice
Rc(n), a polynomial time machine can easily compute the set MAJ
of all h(rn)-bit strings which are ?fL			a majority of the sets 5?j(1?i) .			3J(1?c(7?))'
One of the strings in N[AJ is 1(J)			FShA(m% (xi, x2, ... , Xh(m)).
Notice that MAJ cannot coilt,'tin all possible h(m)-bit strings. If it did then
then it must be the ???? that
c(n)			> c('n)			* 2h(m) --H (c(n) + 1) *
U 5'j(?i)I			?L????1			2h(rn)--Hl,
i=1			--H			2
but that cannot happeii because we kitow that for each Sj(Rj), Sj(Rj) ? 2h(m)--Hi
and therefore
c(n)
u 5Thj(I?i)f ? c(n) * 2h(m)--H1
i-i
Thus, there exists at least one !t(m)-bft string which is not in MAJ and (he
lexicographically least such string 1, can be output in polynomial time 0fl('C MAJ
has been computed. Clearly L ?-? 1(J).
Thus, we have sat?sfied the h??p??thesis of Lemma 3.11. That is, there is a
function n' in PF/pol?J such that given a collection c = x1,x2 h(rn) ? 0f
h(m) (h(m) = O(log?i)) formulae ?U outputs a h(?n?)-bft string w(c.) su?'h thai,
52
w(c) # FhSA(m%(xl, x2,.. , Xh(m)). Therefore, from the lemma it follows that SAT ?:
NP/poly n co-NP/poly and PR ?:ollapses to ??3 [Yap83?.
3.6 Open Problems
In this chapter, we obtained tight peftormance bounds on the success probabilities
of random reductions between nearby classes in the Boolean and Query Hierar-
chies. For example, we have tight bounds for random reductions which save one
or two nonadaptive queries to SAT. However we do not have tight bounds for re-
ductions between classes which are further apart. For example, we can construct a
probability 1/3 ?rp -reduction from BL6 (a union of 3 D? languages) to BL2 (the
complete language for D? ) but ?e cannot prove that it is optimal. One upper
bound for this case is 1 --H i/?7'?+ 1/poig ( O.42265t 1/poly) because by taking
the OR of two trials of a reductioji with this success probability one could obtain
an ?rmP -reduction from BL6 to BL4 with success probability above 2/3 ? l/poiy
and collapse the PH. NVe conjecture that tight performance bounds exist for such
reductions as well. Our proof technique is based on the hard/easy argument which
is very suitable for analyzing reductions between complementary classes at I he
same level of the Boolean Hierarchy but does not seem to be effective for analyz-
ing random reductions between classes which are far apart. More powerful pro??f
techniques may be needed to resolve such questions.
Chapter 4
Threshold Behavior 1
Traditionally, researchers define?I random reductions without giving much consid-
eration to the success probability that the reductions had to achieve. TypicalLy,
reductions are required to behave correctly with some constant probability but
sometimes the success probabilily is as low as inverse polynomial. In the previous
chapter however, we saw several results in which the exact value of the 5u(?cess
probability played a crucial role. For instance, we saw that, unlike determiiiL?-
tic <m? -reductions, random reductions were abli to reduce harde? languages iii the
Boolean and Query hierarchies t() ??niplcrlanguages wfth varying degree of.?uccess.
We also saw that there were liniits on the success probability of such reductions
depending on the type of reduction and the classes involved.
In this chapter, we first show that the traditional approach that do(s place
much emphasis on the success prol?al?ility of random reductions, results in several
anomalies especially when dealing with the notion of completeness under r??andom
reductions. As an example, we will consider USAT (the language of uniquely
satisfiable formulas) aiid show that traditional approach provides ambiguous and
misleading information about its comple?ty.
We then examine rrndom re?lu?tions under a new light and propose that there
1The results presented ?n this chaptei have been ?trawn from [cKR9l] and IR?oh()2]
53
54
is natural and "correct" defii?ition for the success probability especially wheit
one considering completeness under random reductions, As we saw in Chapter 3,
the power of randomness allow' ils to reduce harder languages to simpler ones
with certain probability of success. ??hus, if we set the correctiiess piobabiiity t()
be very low then much simpler sets can be complete for a class under randoni
reductions. Conversely, if the probability of correctness is required to l?e very
high, then as we saw in Chapter 3, due to the limitations of randomness, such
reductions could not substantially reduce the complexity of a problem. In fact, in
the limiting case if the success probabihty is made to be 1, then the class of sets
complete under random reductions is identical to the class of ?? -complete sets.
As expected, sets comple?e under extremely high probability random reductions
cannot be substantially simpler th'?n i?he ?m? -complete sets. ?V?te propose the thesis
that as we vary the sitccess prob?bility, at some exact point, the probal?ilfty of
correctness is just high enough to make the definition right. We call this 1)oiilt
the th?eskold and we believe that i? is a fundamental attribute of every contpte?ty
class which precisely cbaracten'zes the tradeoff involved in the use of randoniness to
reduce the complexity of problems within it, i.e., it quantifies the minimal amount
of error that must be introduce?[ iit order to reduce the complexity of the hardest
problems in the class using randoniness. We then defend this thesis by proving the
existence of such thresholds for several complexity classes such as NP, co-NP. D?
co-D?and the Boolean and Query lIi?rarThies.
4.1 USAT and Random Reductions
From the beginning, tbe study of the complexity of USAT has been tied to the class
D? and to random reductions. The class D? was defined by Papadimitrion and
Yannakakis [PY84] to ?:ltaracte?'ze the complexity of the facets of polytopes and the
complexity of 0ptimiz??i0n probleiits such as CLIQUE(1) (defined in chaptei 3).
Definition: We define D?, coD?aiid their <? -complete languages SAF/\SAF
55
o+ USA?f x-
pSAT[1]
M			?M)cP
Figure 4.1: ?fSAT and related complexity classes.
and SATvSAT.
-? (ThAL2 Li,L2?NPt,
co-D?			(ThuL2IL1,L2ENPl,
SATASAT			( ( F1, F2			P1 ? SAT and F2 c SAT ),
SATVSAT			( ( Ft, F2			F1 ? SAT or F2 c SAT ?.
The set of uniquely satisliaUe l3oolean formulas, USAT, is easily seen to be in
D?. So, the natural question that arises is: Is USAT D?-compete ? f3lass and
Gurevich [BG82] answered this question partially. They noticed that
USAT is <`? -complete for D? SATASAT?rn USAIt?
? SAT?? USAT.
So, the question of wbether US?? can be ?? -complete for D? binges on whether
there is a ?? -reducti?n from SA1 10 USAT. Then they showed that there aie
oracle worlds where no such redu??tion can exist. This mea'ift a noii-reiativizing
56
proof technique would be needed to answer the question a fairly difficull ol?stacie,
indeed.
Valiant and Vazirani [VV86] did not surmount this obstacle, but they did man
age to circumvent it. They were able to construct a ??ndom reduction from SAT t()
USAT. More precisely, they showed that SAT ?rp USAT wfth probability 1/(4n)
(as a special case we wilt henceforth write A ??? R if A <rp B with prol?abllity
1/p(n) for some polynomial p). Thus, based on the observation of Blass and Gure-
vich, USAT became complete for D? under random reductions2. However, this
type of reduction is not quite satisfying, because the probability of the reduction
being correct approaches zero as the length increases. One would have expected
a probability bound of 1/2 (in keeping with the Adleman-Manders [AM7T] defini-
tion). The justification for the V?diant-Vazirani definition is that in many situations
the probability bound can be amplified, in which case, the defiuftions would be
equivalent.
Definition: For any language 1?, we define the following classes.
OR2(B) =? (x,y ? ? B or ? ? I? ?
ORw(B) --H--Hf ( xl,. . , r? ? for some i, 1 ? i ? n Xj c B J
AND2(B) --H? (x,?) xc BandyEB ?
ANDw(B) =1 (xi,. . ,X? ? for all `I 1 ? i ? n Tj c B ?.
If OR2(R)?m? B via some polynomial-time function, then we say that I? has an OR?
function, or simply that B has OR2. We use the same terminoiogy for OR?w, AND2
and ANDw. If a language B has ORw, then it is possible to amplify the probabilfty
bound of a <VmV -reduction to I?. Thus, when B has ORw, <??? -reductions and
<rp -reductions with high probability are equivalent.
Fact 4.1 If A ??mVV B and B has C?J?, then A <?rp B with probabilliy 1 -? ?7ex]).
2Valiant and Vazirani credit Alaii Selinan for this application of their reducti??n.
57
So, in cases where one randolub' reduces to a language which has ORw, it does
not matter which definition is tise?I. Languages such as SAT and SAT are robust
and have both OR?w and ANDw. Aiso, the c??mplete languages for cotnplexity
classes such as ??k? ??k ??? ?P, MODkP and PSPACE all have both ()Rw an?l
ANDw. Indeed, it is difficult to find natural languages which do nol have ORw or
ANDw. However, there are some g?)od reasons to believe that USAT does not have
O?? (see Corollary 4.'?). Thus, there is no obvious way to amplify the Vahant-
Vazirani reduction from SAT to t?SAT. In the next section, we investigate some
anomalies created by the non-robustuess of USAT
4.2 Anomalous Behavior
The first and most obvious pmI?iei?t with the statement "USNI' is complete for j??
under random reducti?ns" is ti?;ft it fails to consider that USAT can b?! c??mplete
for larger classes as well. In fact a simple observation will show tliar USAT is
??-complete for a se??mingly jrtuh larger class, psATlogni p5AT[1Q?7J is the class
of languages accepted by polyitornial-time Turing machine'; which ask ;tt rnost
O(logn) queries to the SAT ora?le. Introduced by Papadimitrion and Zaclios
[PZ83J, pSAT[logn] captures probl??ins such as Sat-Mod-k, Ciique-Mod-k, Ujtique
Optimal Clause Satisfiability, lJnique Optimal Clique and other problems related
to optimal solution sizes of many NP optimizalion prnUems. [Kad89,Kre88].
Lemma 4.1 USAT is ?1V?V?c0nIp[?t( for psATlogni
Proof: Using the fact that ORw(SATASAT) is ??P?complete for psATlogni, ?l)-
serve that there is a trivial ?VV?reduction from ORw(SATASAT) to SATASAT.
On input ( X1, . . . , X? ?, the reductioit chooses 1 ? i `? n at random an?t prints out
Xj. This randoni reduction wit! sitcc?ed with probability 1/n. So, combined with
the Valiant-Vazirani reducti??n, W(' get a ?mVV -reduction froni c)R?,j(SNl'A'3Nf') to
USAT with probabilfty 1/(4n2)
58
There is compelting evidence (hat the classes psAT[Iogn] and D? have very
different structural properties. For example, pSAT[Iogn] is ctosed under comple-
mentation, but D? cannot equ??l co-D? unless PH collapses [CK90a,Kad88]. Also,
all pSAT[logn] ??m -com?ilete languages have ORw, but D? ?? -complete languages
cannot have OR2 unless PH collapses [CN9obl. Since we expect complete sets
to inherit structural properties of the classes they represent, USAT being ?mVV
complete for both these classes raises doubts as to whether completeness under
??? reductions makes sense. Lemma 4.1 can also give misleading results about
the complexity of certain optimization problems. For instance, it implies that all
the Unique Optimization problems in pSAT[logni can be reduced to Unique Satisfia-
bility. At first glance, this appears to say that we can solve optimization problems
using randomness without having 10 do any optimization. However, the probability
of a correct reduction taking pIw is only 1/(4n2). Moreover, there is no known
way to improve this probability l?ound (see Corollary 4.3). In fact, this lemma
really demonstrates the anoinalie? created by random reductions that aTh?w very
low probability bounds.
One might hope that these attoinalies would disappear if we used only- (he
Adleman-Manders delinition of random reductions. However, in the next section,
we will show that even if we restrict our attention to ?rp -reductions with j?rob-
ability 1/2 or any other constaitt, such anomalies will still occur. First, we must
explain what threshold behazior means.
4.3 Threshold Behavior
Considering the anomalous beha?'ior of random reductions described above one
may be tempted to dismiss comph?teness under random reductions as meaningless.
However, the ??? -re?tuction front SAT to USAT proved to be usehil in maiiy
areas of research. For example, Richard Beigel [Bei88? used it to show -?bat SAl'
is superterse unless RP NI?. &lso, Toda [?bd89j used a similar reduction in
59
his proof that PH c p#P?1? Uhis result, in turn, led to the Lund, Fc?rtnow,
Karloff and Nisan [LFKN9D] res?ili;: PH C IP. So, tbere should be little doul?t iii
the reader's mind regarding the usefulness of the Valiant-Vazirani reduction. The
more pertinent questions are: What does this reduction mean? Does USAT being
?mVV complete for D? mean that it is somehow representative of the whole class?
How does the complexity of ??mVV -complete sets compare wfth the ?? -complete
languages? We answer these questions in terms of th?sho1ds of probability bounds.
4.3.1 Examples of Threshold Behavior
To illustrate what we mean by threshold behavior, we turn to a more familiar
setting namely that of NP and co-NP. Let A be any ?mvv -complete set for NP.
Then, we know that A has the loTh?wing properties [AM77,Z1186,1311Z87,Sch89]
o+ A ? P, unless RP = NP and Pil collapses.
o+ A ? RP, unless PP = NP and PH collapses.
o+ A ? co-NP, unless PH collapses.
This compares favorab[y with the many-one complete set SAT:
o+ SAT ? P, unless P = NP.
o+ SAT ? RP, unless R?P = NP and PH collapses.
o+ SAT ? co-NP, unless PH collapses.
From this comparison, we can draw the conclusion that the 4? -complete set, A,
behaves like the ?? -complete set., SAT, and that the comple?ty of the set A is
representative of the complexity ol' tl?e entire ciass NP
In contrast, the tnvial singleton set B = tly is complete fi?r NP under random
reductions with probability 2--H?. Clearly, B is not representative of the contplexity
of NP. So, completeness under <rml -reductions with probability 2--H? does not make
60
sense for NP. liowever they d() make sense for co-NP. Let C be a set complet?
for co-NP under <rp -reductions with probability 2--H?. Then C ? NP, niikss
NP co-NP.
These results show ?hat conipleteness for random reductions make sense only if
the random reductions have a probability bound above a certain threshold. Moie-
over, the threshold is different for different complexity classes. For NP, the thresh-
old is l/polu; for co-NP, 1/ewp. Alteriiatively, we can look at these results in terms
of random reductions from a set to its complement.
o+ SAT <rp SAT with probability 2--H?.
o+ SAT ?rmP SAT with probabilily 1/p(n), for any polynomial p(n), unless Pll
collapses.
These two statements show that when we consider random flinctions which reduce
SAT to SAT, a probability thres]?old occurs at l/pol?. Shuilarly., for SAT the
probability threshold occurs at i/e.Cp.
o+ There is no known ?? -wdu?.tion from SAT to SAT with probability greatr
than 0.
o+ SAT ?rmP SAT with probability 2--H????, for any polynomial p(n), unless NP
co-NP
4.3.2 Threshold Behavior in the classes D? and co-D?
In this section, we show how proba?bility thresholds can explain the anomaly pre-
sented in Section 4.2. R?ecall that SAFASAT and SAFVSAT are the ?? -complete
sets for D? and co-D?, respectiv?iy. We will show that beyond a certain proba-
bility threshold the ?rp -complele sets for D? and for co-E? have many of the
properties of the --H?m? -?:omplete :3e?s. Some of these properties are tC;K9Da,CN9Ob,
Kad88J:
o+ SATASAT ?m? SATVSAT, i?nl(ss D? co-D? and PH collapses.
61
o+ SATASAT ? co-D? and SATVSAT ? D?, unless D? co-D? and PR
collapses.
o+ SATASAT does not have OR2, unless D? --H co-D? and PR collapses
o+ SATVSAT does not have AND2, unless D? co-D? and PR collapses.
We will use these properties as a benchmark to test if a particular concept of
completeness for D? and co-D? makes sense. First, we show that for completeness
under ?rp -reductions, the probability threshold for D? is bounded below by 2???.
Lemma 4.2 SAT is complete for D? under ?rp -reductions with prnbabilfty 2--H?.
Proof: The following is the required reduction from SATASAT to SAT. On input
( P1, F2 ?, try to randomly guess a salisfying assignment for F1. If F1 is satisfiable,
the reduction will find a satisfying assignment with probability at least 2?-?. If a
satisfying assignment is found, 1?h( reduction simply prints out F2. Otherwise, it
prints out a fixed sati&iable formula.
Corollary 4.1 SATASAT ?rp SAl v SAT with probability 2-?.
Since SAT ? co-D? and since SA? has ORw and ANDw, we can safely say that
completeness under ?rp -reductions with probability 1/exp does not make seiise
for D?. The following theorems, show that completeness under ?rp -reductions
starts making sense when the probability bound is l/poly. Hence, the probal?ility
threshold for D? is bounded ab?we by 1/poly.
Theorem 4.1 SATASAT ??VV SWTvSAT, unless PR C
Proof: Suppose SATASAT ??? SNTVSAT. Then that means that all languages
in BR(2) randomly reduced to a Janguage in co-BR(2) under prol?abihty l/poiy
?rmP -reductions. But as shown in Chapter 3, (Theorem 3.2. see Jsc) [`igure 3.2)
this immediately implies that tl?e PR collapses to ?d?'
62
As an immediate corollary of Theorem 4.1 we can conclude that completeness
under ??? -reductions does make sense for D?. Nioreover, WQ can show that lan
guages complete for D? under <$VmV -reductions have properties very similaj to the
properties of the ?? -complete language SATASAT.
Theorem 4.2 Let A be complete for D? under ??? -reductions. Then
1. A ?rn A, unless PH collapses.
2. A ? co-D?, unless PH coilapses.
3. A does not have OR?w, unless Pil collapses.
Proof (Sketch): Parts 1 and 2 follow from Theorem 4.1. The proof of part 3 is
similar to the proof of Theorem 4. I. Simply note that if A has ORw, then there is
an <r?P -reduction frorn SATVSAT to SATASAT with very high probability. This
condition is sufficient to mimic tile proof that SATVSAT?rn SATASAT ? Pit
collapses. See Theorem 4.4.			E
As a special case of' a language ??? -complete for D?, USAT has all the prop-
erties listed above. In fact, since W( also know that SAT?? USAT we can get even
stronger results.
Corollary 4.2 USAT ? co-D?, unless PH collapses.
Corollary 4.3 USAT does not h?'we ORw, unless Pil collapses.
Theorem 4.3 USAT ?m? USAT, unless D? co-D and PH collapses t()
Proof: Since SAT?? USAT it follows that SAT?? USAT. Hence, if we assunie
that USAT =? USAT, then SAT ??m? -reduces to USAT as well. Thus, ??SAT be-
comes ?? -complete fi?r D?, ?? L)F Co D? and the Polynomial Hierarchy col-
lapses to ?3? by Kadin [Kad88].
63
Thus, we can conclude that Valiant and Vazirani made right decisioi? wheii
they used ??? -reductions to talk about completeness for D? under random re-
ductions. However, completeness ttnder <VmV -reductions may not make sense for
other complexity classes. In fact, the following theorems show that the threshold
for co-D? is 1/2 + 1/poly.
Lemma 4.3 SAT?SAT is complete for co-D under ?rp -reductioiis with proba-
bility 1/2 + 2?n2.
Proof (Sketch): Recall that SATVSAT is ?? -complete for co-D?and that
SATOSAT ? OF F ? SAT lut iF F ? SAT ?.
Also, note that SAT?SAT E 1)P fl co-D?. It is simple to construct a random
reduction with probability greater than or equal to 1/2, because
(F1,F2 ? SAT?SAT ? F1 E SAT orE2 E SAT.
Thus, a randomized function can choose F1 or F2 with equal pn?bability, then
output iF1 or OF2. If ( F1, F2 \) is indeed an element of SATVSAT, then it follows
that Prnbi??o,ii[ ?F2?j ? SAT(jSAT ] > 1/2. On the other hand if ( F1, F2 ?
SATVSAT, then Pr0bj?to,iy[ ?F2?j C SAT?SAT] 0. To improve the probability
beyond 1/2, simply observe that if F2 C SAT, then there is a small probability of
finding a satisfying assignment through random guessing. ??his fact can be used
to improve the probability to 1/2 + 2?n2 EJ
Using the fact that SAT?SAT E D?flco-D?, we also obtain the following corollary:
________			________			2
Corollary 4.4 SATVSAT ?rp SATASAT with probability 1/2 + 2-?
Since SAT?SAT ? D we can conclude that this set does not meet our criteria
for a sensible complet? langu?ge f?r co-D?. H??wever, if we require the reduction
to have a probability l?ound ab?we 1/2 + i/pol?, then completenes?; inake? sen?e.
64
Theorem 4.4 SATvSAT ?rrnP SA??ASAT with probability 1/2 + 1/p(n). for any
polynomial p(n), unless PR c
Proof: Suppose SATvSAT ?rp S]?TASAT with probability 1/2 + 1/p(n). Theit
that means that all languages in co-BH(2) randomly reduced to a language in
BR(2) under pwbabilii? 1/2 + l/pol? ?rmP -reductions. But as shown iii Chapter
3, (Theorem 3.3, see also Figure .2) this immediately implies Ihat the PR collapses
to ??P
Now we can show that the languages complete for co-D? under <:rp -reductions
with probability beyond the threshold of l/2+l/po1? have many properties enjoyed
by the ?? -complete languages Jbi co-D?
Theorern 4.5 Let A l?e comp[ete for co-D? under ?rp -reductions wftb probatul-
ity 1/2 + 1/p(n), for some polynoii?ial p. Then,
1. A?rnTh unless PR c
2. A ? D?, unless PR c
3. A does not have AND2, unliss PR c A3?.
Proof: Parts 1 and 3 follow from Tbe??rem 4.1 and Part 2 follows fr??m i?heo?eni 4.4.
4.3.3
Threshold behav?or in the Boolean and Query
Hierarchies
Next we turn to the classes in th? Boolean and Bounded Query Hieraichies. In
Chapter 3, we proved ti9lit bounds on the success probabilfties of random reduc-
tions between nearby classes in tlie Boolean and Query Rierarcbies. These tight
bounds immediately provide us with the thresholds for thes? classes as well. For
instance, we showed that the BL2k the complete language for BR(2k) ?rmP reduces
65
to the complementary language co-BL2? with probability 1 --H 17k. Tl]us, 1 --H 17k
is a lower bound on the threshold for ?rmP -completeness in Bfl(2k). i?Ioreover,
Figure 3.2 also shows that 1 --H ? /k + 1/poly is an upper bound on the threshohi
for Bll(2k).
Theorem 4.6 For the class Bll(2k), the threshold probability for completeness
under <rp -reductions is 1 --H 1/k 4- ?7poly.
Based on this theorem we can easily show that any language L which is ?rrnP -
complete for Bll(2k) with a prc?babihty above the threshold inherits the follow-
ing hardness properties (assuming PH infinite) usually associated with the ?? -
complete languages:
o+ L is not in a simpler class such as pSATII[2k--Hi] or in the complententary class
co-BH(2k).
o+ L is not closed under OR?? (or ??ven OR2 if k > 1).
Also, for every k > 1, we cai exhibit a language in BII(2k) which is ?rp -
complete with probability above (lie threshold. Define the languages BL2k?2 `V
USAT as
f Xl, . . . , X2k?2,,y )			Xl,.. . , X2k?2 ) C BL2k?2 or y c USAT ?.
Lemma 4.4 For any k > 1 the tanguage BL2k?2 v USAT is ?rp complete for
BH(2k) via a probability 1 --H 17k l/(4kn) reduction.
Proof: BL2k?2 v USAf ? BH(2k) because USAT ? D?. The ""rp -reduction from
BL2k to BL2k?2 v USAT can be ol?tained by combining the ?r? -reduction used in
Lemma 3.1 with the probability 174n Valiant-Vazirani [VV86] reduction from the
SATASAT to USAT.
Thus, the languages BL2k?2 `V ???SAT, by virtue of being ?rrnP -complete with the
requisite probability inherit the kardi?ess propel-ties listed above. Note that we can
6(3
show this without haviiig to prove that the languages are ?ffi -coi-nplet?. in fact
we can prove the following thecreiii that shows that non-relativizing tedtniqi?es
will have to be used to decid? whether these languages are ?m corriplete.
Theorem 4.7 There is a recursiv( oracle 0 such that rdative to 0, Vk, the re]a-
tivized language coues??onding to ??L2k?2VUSAT is not compl??te for the relativize?l
class corresponding to BH(2k) under relativized ?? -reductions,
The oracle 0 can be constructe?J by combining the technique used to construct
an oracle which separates the Bootean Hierarchy ?CGH+88J with the technique
used to construct oracle worlds where USAT is not ?? -comi)lete for D? [BG82]
Chapter 5
Completeness under Random
Reductions: Absolute
Separations 1
In the preceding ct?apters w? ;aw that the correctness probabllity of random
reduction is crucial as far as the notion of completeness under random reductions
is concerned. In fact, we saw th(?t for many complexity classes C, the behavior
of sets complete under random i?c[uctions is determined by a p?obabzi'ity ll?nrsho1d
CT. Sets which are complete fbi C under random reductions witb correctness
probability below CT niay be fat sirni?ler than the ??rn-complete sets of C, whereas
all sets complete under reduction? with correctness probability above CT inherit
many of the hardness properties ?ypical of ?? -complete sets. For many dasses
the value of this threshold is non-trivial, for instance the thi?sho1d probability for
two-sided error randoni reductin?; in pSATII[kJ is 1 --H 1/(k + 4), i.e., sets which are
complete for these dasses undei ?:r.ol?abihty 1 --H 1/(k + 1) + 1/po1?(n) reducti??ns
are harder than certain sets wbic? are complete under probability 1 -- i/(k + 1)
1The results presented n this Ch('t])t?]' h?we been drawn from [CR93]
67
68
reductions unless the Polynoinial Hierarchy (PH) collapses. This established that,
if the PH is infinite, the notion of completeness under probabihty 1 --H 1/(k + 1)
random reductions must differ from that under probaUlity 1--H1/(k ? t)tl/po!y(n)
random reductions, thus highlighting the sensitivity of the notion of completeness
under random reductions to small changes in the success probability.
However, all these results rely on the assumption that the PR is an infinite
hierarchy (actually, we only need to assume that it does not collapse to its thir?l
level). Although this is a standard assumption in complexity theory, it is stiil
not a conclusive proof that randoni reductions have the kind of behavior that we
claimed. In this chapter, we provide further evidence that such behavior is inherent
to random reductions by proving that it is present in very high complexity classes
without making any str?ctu?a1 a?;sumptions. In doing so, we systematically expl(?re
the notion of completeness under random reductions with diff??reni probabilities.
We compare completeness und?'r vanous random reductions to each other and
to completeness under deterministic reductions. We obtain optima] separations
between completeness notions under different random reductions and coin pleteness
under deterministic reductions. Oiir results also show that even a vanishingly small
difference of 1/poly(n) in the sLt(c(ss probability of the reduction yields a diff,'r?,nt
class of complete sets.
Separating various determiristic polynomial time reductions and notions of
completeness under such reductions has been an active area of research. The study
of polynomial time reducibilities originated with the seminal work of Ladner, Lynch
and Selman [LLS75] who defined several truth table reductions and showed that all
these reductions along with ?P and ??T reductions are distinct in E. They left open
the question of whether the complete degrees for these reductions were distinct
in E. This was partly resolved by Ko and Moore [KM81], and finally `vatanabe
[Wat87] developed a powerfiil proof methodology to show that in E most notions
of completeness were indeed dil]br??nt. Subsequently, similar results were obtained
69
by Bulirman, Homer and Toren????t [BHT90] for nondeterministic classes ?uch a?
NE. An interesting question left open by Watanabe's work was whether in IS the
notion of ?P-completeness was difibrent from the notion of ??1?tt-completeness. Iii
a surprising development these were shown to be the same for IS by Homer Nurtz
and Royer and a simlla? result for NE was obtained by Buhrman (cf. [Hom9Oj).
These absolute separation results are only known for highly intractable corn-
plexity classes such as E and beyond. Such results have not been forthcoming
for easier classes such as PSPACE since this would imply that P # PSPACE.
Moreover, due to contradictory relativizations of the P PSPACE question such
separations can not b( obtained in PSPACE using relativizing techniques. For
separating completeness under different random reductions the situation is much
worse: there exists a relativized world where RP E [Wil85] and anothei rel-
ativized world where I3PP --H F?2 [Hd86]! Therefore, in order to obtain strong
separation results we bave to go t() higher classes.
First we show that in E there are sets which are complete under very hig?
probability random reductions btit w1?ich are not complete under any deterininistic
reductions. The construction is a ?traight forward diagonalization which ?????C5
that the resulting set ?loes not a satisfy a property possessed by all ??i-complete
sets for E [Wat87]. Next, we examine whether there are sets which are complete
under deterministic reductions but not under certain random reductions. As noted
earlier, relativizing techniques can not yield such results in classes like IS or 1SA,
However, we do obtain very sharp se?)aration results in slightly higher classes like
IS?2 or IS (superexponential tinie). The crucial difference between the classes IS?2
and EA2 that allows our technique t() work is that in IS?2 we can approximate the
the number of accepting paths of a nojideterministic superpolynomial time machine
to a high degree of accuracy based ?)n Stockmeyer's result on apprG?irnate counting
[Sto83].
Since our techniques for one ??d?d error (??mP) reductic?ns di'ffei from ih??se
70
for two sided error (?J%PP) reducti??ns, we treat these reductious separately. For
<mP reductions we prove that for every k > 1 there is a set in E?2 which is
????u?complete (actually ??k--Hdisj c??mplete) but not ?rP?coInplete with probability
1/k+1/po1?(n). This is an optimal separation result because sets which are
complete are also ?rp complete with probability 1/k. Next we show that for anv
p there exists a set in E?2 which is ?rp complete with probability p but not ????
complete with probability p + i/p??1y(n). This supports the thesis that the notion
of completeness is very sensitive to small changes (even a vanishingly sniatl change
of 1/po1?(n)) in success prnbabilfty of the random reduction. Our approach to
?rmP reductions is based on the niethodology proposed by Watanabe. We first
identify a property that is possessed by all sets which are complete for E?2 under
probability p+ 1/poly(n) ?rmP reductions. We then construct a set by diagonalizing
against this property while ensuring that the set constructed is ?rmP?completeunder
a probability p reduction.
To obtain optzmal separations jor ?bpp?reductions we employ a new techn?qiie'.
For every k > 1 we construct a set n l?j?2 which is ????tt?complete (actually ?? I'sj
as well as --H??k--Hconj complete) but nc?t ?bPP?complete with probabilfty 1/2 + 1/2k-H
1/poly(n). If a <??k?tt complete set is both and ??k--Hconj complete th?n it
is actually complete under probability 1/2 + 1/2k ?rnbPP?redu4,ions. IIenc? tl?is is
an optimal separation. We exten?l this technique to show that for any p, there
exists a set in E?2 which is complete under probability p ?bmPP reductions but not
probability p + 1/pol?(n) reductions. The technique used to prove these resulis
is to first construct a highly structured set which satisfies certain diagonaliz<ttion
requirements and then to explicitly construct a language in E?2 which caniiot
reduce to the constructed set witb high probability <?bpp?reductions.
The chapter is organized as frIlows: In Section 5.1 we provide the necessary
background. In Sectioii 5.2 we outline the construction of sets which are complete
under high probability random r??duction but not complete ?inder deteriuiitistic
71
reductions. Section 5.3 describes the separation results for ??rnP?redijctions and iii
Section 5.4 we present results for %brnPP?reductions.
5.1 Preliminaries
We will use E to denote the class Uc>0DTIME(2Cfl). In this chapter we will also deal
with the classes EA2 and E?2 which are members of the weak exponential hierarchy
[11em87]. The class EA2 consists of Janguages that are accepted by exponential time
(2cn) oracle machines which can query a A?2 complete set, Similarly the class E?2
consists of languages that are accepted by exponential time oracle machines ??-hich
can query a ??2 complete set.
We assume a standard enum?ration of deterministic polynomial time transditc-
ers, Mi, .2....' and randomized polynomial time transducers, ......... in ?hicb
each machine appears infinitely often. Also the running times of AL and R?, are
bounded by ??,
5.2 Separation results in exponential time
In this section we construct sets in E which are complete under very high probabil-
ity (1 --H 2cm) ?mrP and <?bmPP redticti??ns which ar( not complete under deterministic
reductions.
We use the following result of Watanabe [Wat87i which establishes a property
of sets which are complete under jeterministic reductions.
Lemma 5.1 [Wat87j Let A be aiiy ???-complete set for E. Then thew exists a
polynomial time oracle machine I\J stich that for all but finitely many ?, th(' set,
Q, of strings queried by MA--H??(on) contains a string in A of length greaier than
n i.e. Q n A>? #
Since we will be using generalizations of tids lemma later on in som( of our
proofs, we shall provide its proof here.
72
Proof: [Wat87j Given a set A which is ?P??complete for E, define a languag? `;A
based on A as follows. On input ( i,O? ):
o+ Compute the set A<--H?. T[iis can be done in E.
o+ Let Mi be the i'th polynoinial time oracle machine in the standard enumer-
ation of such mac?ines. Simijlate MA<n (( j,0fl ?) for 2? steps.
o+ If the computation is not complete in 2? steps or if the final configuration
is accepting then reject the h?put. Otherwise (the final configuration is
rejecting), accept the inp?tt.
From the definition, it follows that LA constructed as above is in E and since A
is <??-complete, it follows that 7,A??T A via some polynomial time oracle machine
Alk. For sufficiently large n the running time of kj? on ( k, O? ? will always be
less than 2?. For any such n, let us compare the behavior of ki?4--H?? ( ( k, (?fl ))
and MkA(( k, O? `)). If ( k, O? ? ? LA then by definition of LA we must have
that MkA<fl(( k, O? )) must reject whereas MkA(( k, O? )) shouM accept in order to
carry out a correct reduction. Sim?lady, if ( k, O? ) ? LA then we must have that
MkA<fl(( k, O? ?) accepts whereas Mk4(( k, O? )) rejects. Thus, in either case, fr-r
large n, the output ofMkA<fl(( k, O? )) is different from the output ofAfA(( k, O? \/)
which can only happen if for all inputs of the type ( k, O? ? (n large), the machine
Mk queries at least om string in A>n. Thus, an oracle machine M which on input
O? simulates the oracle machine kik on input ( k, O? \) satisfies the requirements of
Lemma 5.1.
We use this characienzation to construct, via diagonalization, a set A which is
<rP?complete under high probability reductions, but not ???-complete.
Theorem 5.1 There exists a set ti, which is ?rP?complete for L' with probobi?tg
1 1 --HT plete.
--H 2Cfl but not ?? corn
73
Proof: Let U be a standard ?P-complete set for E. The elements of A wifl be of
the form u#x where ? ? U and r is a string in ?? of length a We maintah? the
following property:
P : For each u ? U almost ali strings of the form u#x, with `a x , will be
in A.
This immediately gives an obvious high probability ??rnP?reduction ftom tf to
A. The construction maintains ? while ensuring that the resulting set is not
<P??complete for E.
Construction of A: The set A is built in stages. We ensure that fi?r every oracle
machine Mj, for infinitely many ?. none of the strings, of length greater than 7?,
queried by MA--H<?(on) is in A. ]3y Lemma 5.1, A will not be ?P??complete fi?r E.
This is a straightforward diagon;tlization argument where we balance this negative
requirement with the positive requirernent ?.
Let n1 = 0 and A0 = ?. Each machine appears infinitely often in the enumera-
tion of oracle machines and aftei a certain stage, every time a machine ]\4 ap??ears
it gets diagonalized ag?unst.
Stage i: Let n = flj. ;?un Afj -1 ?O?) for 2W? steps. [fit doe? tiot halt let fl??1
flj + 1 and put into A all strings of tiie form ?#x of length n 4- 1 and go I?o stage
i t 1. If the simulation succeeds within 24? steps let Q be the set of strings queried
by by MzAt?1(Ofl) Let Qi be the sul?set of Q>fl consisting of strings of the form
x#y, where 1w = ??. Let m be tbe size of the largest string of Q.
Aj = Aj?1 U ?u#xI i'??			IxI,u c Un ? Ju#xi ?
Let n?+1 = rn and go to stage? $;(.
Since the entire construction ?[) to any length n can be carried out iii time 2???,
for some constant c, the set A is in E. Each oracle machine Al gets diagonahzed
infinitely often and, by Lemma 5 [, A is not ?P??complete The property r is
maintained, since for all `a C U=?2, e?nly one niachine Mj can rule out strings ()f
the form `a#x from A. This occurs at a stage when the input to Af? is 0k with
74
k < n#x which is at most 2n + 1. From the construction, Mi(f)k) runs for at
2n+1			2n+1			2n#1
most 2 4 steps and hence IQ?I < QI ? 2 4 in that stage. Hence at most 2 4
strings of the form u# can be in 4 for any it E U. The fraction of strings of the
form tt#x which are in A is at least 2?--H2(2n+1)/4 ____
> 1 --H 1 Thus the constructioji
maintains the property ?.
Corollary 5.1 There exists a set which is complete for E uncler probability 1 --
1/2Cfl f<rmP,?<bmPPl reductions but which is not f ??m' ??k--H?????tt ???t-complete.
Note that the set constructed above is ?rP?complete for E with inverse expo-
nential error probability. Since an ??-complete set is ?rP?complete with proba-
bility 1, in this special case we have a separation between completeness notions for
reductions with probabilities that are very close.
5.3
Separation results for one sided random
reductions
In this section we construct sets which are complete under deterministic reductions
but not complete under one sided error random reductions. Since the question
R?P E is unresolved we can not hope to find such a separation in E because if
RP--H--HE then all non trivial sets in E are <rP?complete with high probability. Since
these techniques are also apphcable to certain ?bPP?reduction we have to go to the
class E?2 to avoid the relativized t3PP EA2 result [Hel86].
In section 5.3.1, we construct a set which is ?????jsi?comPlete (and hence ?rp?
complete with probability k1) bul which is not ?rrnP?complete with probabi?ity
?k1+po1y'(n) When constructing s(?s which are ??? -complete but not ?rP?complete
we have to contend with ??k--Hdisj complete sets which are ??rnP?complete with proba-
bility ?k1 Thus p ?k1+po? is th( smallest probability2 at which we (?aii find a set
2Actually a smaller difference of 2? ;?fiices.
75
which is not ??rnP?complete under pr??b??bility p reductions. This directly shows tha-
the class of complete sets for <T?P??edUctions with probabilities k1 and k1 + poly1(Th
differ, In section 5.3.2 we exien?l i?his to show that for any p, the classes ?)f coin-
plete sets under probability p ??nP??1?ducti0nS and probabllity P + po?y1(n) reduclions
differ.
5.3.1 Deterministic but not ?rP?comp1ete sets
Motivated by the approach used by Watanabe [Wat87], we first establish a propeity
of sets <rP?complete fr?r E?2 with probability p and then diagonahze to produce
sets which are not ?rP.?complete with probability p.
Lemma 5.2 Let A be <w?complete for E?2 with probability p. Then there exists
a randomized polynornial time irans?iucer, R, such that for all but finitdy many
n, R(O?) outputs an element of A??? with probability at least p.
Proof: Extending thc approach ;?f Wat87] we define a language ??A as folio?vs.
On input ? i, O?>:
o+ Construct the set A<n. Since there are at most ? n+1 elements to be tried
this can be done in E?2. L?et 6 be the exponential sized characte?stic vector
for A<--H?.
o+ Query the ??2 oracle if J?i on ilIput ? ?, O? > outputs an Xj with b)xj) 1
on some path in at most 2? st(ps. The input to the oracle is (? ?, O? >
whose size is at least 2?, an?i an NP machine can simu]ate Rj(<7 i, O?? >) for
at most (? i, O? >, ? steps and detect if such an Xj exists. li no Su(t J'?'j
exists then accept else reject.
Clearly LA is in E?2. Since A is ?rP?complete for E?2 with probability p, theie
exists a probabilistic transducer, J?j, witnessing the reduction from LA to A. i?or
sufficiently large n, th( running tiiite of Rj(? I, 0? >) is less than 2? For such jt
76
j, O? > must be in LA, or 4se R5(? j, On >) would only output etements of A
and by definition of LA, we would get <j, O? >E LA.
Thus, for all but finitely many it, Rj(? j,0fl >) outputs an eiement of A
with probability at least p. It can not output any element in A<--H?, otherwise, by
construction, ? j, On > would not be in LA. The required machine R, on input
O?, simulates J??(? j,()fl >).
We now construct a set which is --H??2--Htt complete but not ?rP?complete with
probability p > ? + e. rUhe ffi?2--Ht? condition is actually a disjunction and hence the
set is ?rP?complete with probability 2
Theorem 5.2 There L?i5t5 a s(t 1? which is ??2 tt?contplete for E?2 but which is
not complete under <rP?reduction? with probability p >?? + ? where E po?y1(n)
Proof: The set B is constructeti in stages. In the construction we ensure that for
every probabilistic transducer 7? then are infinitely many n, such that 7?(On) does
not output elements of B>n wLt? ??rnbability p and thus by I?emma 5.2 B cannot
be ?rrnP?complete with pwbability ??
The set B consists of stflngs ()f the form u#O or u#,1 where u C TX, the siandard
complete set for E?2. For each `?j C at least one of the strings ukO or u#1 will
be in B. This ensures that B is ??2ffi?t hard for E?2. Let no 1 and B0
Stage i: Let n n?. By assumption the running time of 7?j(0?) is at most n?. If
this is larger than ?log(n) then set `flj+1 2flj and add to B all strings of the form
u#O, u C U, of length between iij -? 1 and n?+1 and go to stage i + [.
Use the ??2 oracle, using sufhcient padding, to find ni, the size of the largest
string that 7?j(0?) outputs. To meet the diagonalization requirements we must
ensure that the probability that l?i(O?) outputs any of the strings that we add
to 7? is less than p. On the other hand, for each u ? U W( must add one of
u#O or u#1 to 7?. If among ii#O and u#1, the string that 7?j(0?) outputs witk
lower probability is added to 1?, then the probability that R?(O?) outputs a string
77
in B>n is at most 21. However we can not naively simulate all paths of Rj t()
determine which string is output with lower probability since that may require
2?Iog(n) time, Instead we adopt the approach of approximating these probabilities
using the following resuli due to Stockmeyer.
Lemma 5.3 [Sto83] Let M be an NP machine. Then in A3 we can, on any input
x, estimate #ACC(M,x), the number of accepting paths of A] on x to within a
multiplicative factor of 1 ? 6 where 6 is inverse polynomial in the length of the
input.
Consider strings of the form u#O or u#1, with v ? U, of length 1, where flj ?
1 ? m. To decide which of u#O or u#1 to put into B we first approximate
the probability that J?j(0fl) outputs these strings. Since Rj(O?) runs for at most
?log(n) steps on any p;ith and we have the resources to produce an exponential
sized padding we can use Lemma 5.3 to approximate these probabilities to within
a multiplicative factor of (1 ? 6), where 6 is as low as 21cn.
Let pu(0) and pu(1) be the computed estimates of the probabllity that R(O?)
outputs v#O and u#1 respectivel? and let pu(O) and pu(1) be the actual proba-
bilities. We put in B the striug which has the lower estimated probability. The
use of estimates may cause a string with larger actual probability to be put into
B but we now show that this does n(?t introduce a large error.
For each v E U if we had put the string with lower actuaJ prnbabihty then
Prob[ 1?j(0fl) outputs a stn't? in B>? 1 ? ?min(p?(O),p?(1)) ? --H
2
where the summation is over all v such that u#tO, ?Y > n When estimates are
used, the probability that Rj(O?) outputs a string in B>? is Zv niin(p%(O),p%(l)).
Notice that for all v,
? ?flifl(Pu(D),Pu(1))(1 + 6)/(1 --H 6)
where 6 is at most 2cn Thus, the j?robability that R%(O?) outputs a string in B>?
is at most 21(1 + 7??2c1n) For leugt?? ?? + 1 to `?i+1 2??, put v#O ijito A, whe?e
78
u C U.
[z
B ? E?2 since the above construction can be carried out up to any length iii
E?2. By construction, we ensured that B is ??2??-hard for EL2. Heuce B is ??2--Htt
complete for E?2. Since each R5 is diagonalized infinitely often, by Lemma 5.2, B
is not <rP?complete with probability p >?2' t E.
Corollary 5.2 For any k, there exists a set Ck which is ????tt?complete for E?2
but not ?W?complete with probabilfty for k1 ? poly1(n) There exists sets which are
p(n)-??ft,<??? complete but whiclt are not ?rp complete with probability greater
than p(1n) + pJly.
The big step in the above coiistruction was the ability to estimate probabilities
in E?2. In exponential time we can not simulate all paths of an arbitrary Rj to
compute actual probabilities. ?[owever in classes such as E DTIME(2?'0????),
and beyond, the probabilities (:ali be computed exactly. ??he foliowing can be
shown along the same lines.
Theorem 5.3 For any k, there e;?"s/s a set Ck which is ????tt?complet? for F ?ut
not ??rnP?co7flplete with probabil?ty for ?k1 + pol?(n) There exist? sets which are
f<??tt,<?Tt complete but which are not ?rp complete with probability yreater Than
Hn +1
poly.
5.3.2 Separations of different probability ?m?P?reductions
Let us now consider the pr??blem of separating the class of coniplete sets under
different ?rP?reductions in tlie clas? E?2. We note again thai if I?P--HE then every
non trivial set is complete witfi ??uol?ability 1 ---H 1 Howe??r at classes such as
exp
E?2 which are higher than E we show that th??re is a very fine distinci;ion in tbe
completeness notions lor ?rp reductions witb different probabilities.
79
In Corollary 5.2 we obtainel sets which were ??k--Htt complete but nut ?rp
complete with probability ?k1 + p%Th71(?t?)' In our construction the truth table condition
was a disjunction and hence the set was also ?rP?complete with probabihty k'
Therefore, we have separated the notions of ?rP?completeness for probabilities ?
k
and ?k1 + poly1(n) for integral k. ?? will use similar ideas to prove the following
theorem which separates reductions with probabilities p and p + poly1(n) for any
arbitrary value of p.
Theorem 5.4 For anu, p, the? erists a set A in E?2 which is ?rP?comp1ete with
probability p but not ?rP?complete with probability P + poiy1(n)'
Proof: The construction uses ideas from the proofs of Theowms 5.1 and 5.3 The
constructed set A will consist of strings of the form u#x where u C U, the s? andard
complete set for E?2, with Ix! u . For each U ill U we will ensure that at least
a p fraction of the strings of tbe form u#x will be in A. Hence the set A will be
<rP?complete with probability p. in order to ensure that it is not ??rnP?c()mplete
with probability ? 1 we ensure that for each randomized polynomial time
p()ly(n)
transducer, R, for infinitely many ?? the probability that 1?(0fl) outputs an eleineiit
of A>fl is less than p + poly1(n)' J3y Lemma 5.2 the set A can not be ?rP?c()mplete
with probability P + poly(n)
The set A is constructed in stages: Let no 1 and A0 ?. Stage i tries to
diagonalize against the jth probabilistic transducer 1??.
Stage i: Let n = n? and consUer 1?j(0fl), By assumption 1?j(0fl) does not run
for more than n? steps . If this is larger than ??log(n) then we set n???1 --H 2flj and
add to B all strings of the form u#x, u E U and x = lul, of length between n? + 1
and n?+1 and go to the next stage.
Query the ??2 oracle using suff??cient padding, to find rn, the size of ?he largest
string output by J?j(0fl) on any l?ath. To diagonalize against this madjine we must
make sure that the strings we put in ?i of length between n+ i and rn ar?. such ti?at
the probability that the machine outputs any of these strings is less than p+ ??1?1 n?
80
A simple way to ensure this is as follows: For every u E U, of appropriate size,
consider all strings of the form a#x where Ix v . Sort them on the basis of
the probability with which flj(0Th) outputs them. Add to A the p fraction of these
strings with the lowest probability. This will ensure that J?j(O?) outputs a string
in A with probability3 no more than p and we will have successfully diagonalized
against Rj. llowever, since we cannot compute these probabilities exactly we will
settle for approximations of these witit error approximately 2cIn for some c > 0 and
perform the above step based on tite estimated probabilities.
For lengths m to flj+1			2?? we put into A all strings of the form n#x with
v --H--HIx.			E]
All that we need to show to cont?)lete the proof is to show that the error in using
estimated probabilities does not airect the diagonalization. This is easily seen as
follows: For any v El U. let q? be tl'?? probability that Rj(O?) outputs a String of (he
form u#x where x is any string of iength v . Clearly ZuEU qu ? 1 If we use exact
probabilities and put ijito A tbe lowe.?t p fraction then the probability that Rj(O?)
outputs a string of th(? form v??' which are iii A would at most be pq?. Tfra??,
the probability that 1?? (O?) outputs a string in A>? would at most ?uEU J??u ?
When we use estimated probabilit?es then the estimate of q1I is at most Q?(l t ?)
where 6 is at most 2cln by Lemina 5.3. If we take the lowest p fraction based on
estimates then the estimated probabilfty that Rj(0?) outputs one of these strings
is at most pq?(I + r). The actual j?robabifity of this can at most be pquJffi? Thus,
the probability that R?(O?) outputs a strings that is in A>? is at most Pt$e? which
is much lower than p 4 poly(n) and h??nce the diagonahzation is successful. El
We note that similar results held for determirtistic classes like L' or nice classes
containing E.
3The small error of			in ????0Mn?;?ifl? a p fraction can be ignored.
81
5.4 Separations for ?bpp?reductions
In this section we consider reductions with two sided error. We construct s?ts
which are complete under detern?inistic reductions but not under ?bPP?reductioi?s.
We also obtain separation results for completeness under ?brnPP?reductions wit Ii
different probabilities. To obtain opt??na1 separation results for <bPP?reductions we
employ a technique that is different from that of Watanabe [Wat87]: We construct
highly structured sets which meet certain diagonalization requirements and then
explicitly find sets which do not ?bpp reduce to the constructed sets beyond a
certain probability.
We illustrate our results on ?`%PP-reductions by constructing a set A which is
2			1
?bPP?complete for E?2 with pn?babihty 32 but not with probability ? t FoIy(n)
In fact the set we construct is c??mplete under ??3--Hdisj reductions and ffi?3--H-conj
reductions and hence we have ?t? ??ample of a set which is <?3?tt-complete but
not ?bPP?complete with proba1?ility 32 + pol?(n) This separation is also opti-
mal in the sense that a ??3?tt?co?p[ete set may be both <??3??c0ni?c0mplete and
<?3??jsi?c0mPlete and hence ?b?P.complete with probability ?32. Since the set is
???3??1si?c0mplete it is also ?TP?complete with probability 31 and similarly it is also
?rnC0??P?complete with probability 31. This is also an optima[ separation l?etween
<rP?completeness and ?brnPP?conipleteness since a set which is ?rP?con'plete with
probability ?31 could also be ?C0?rP?complete with probahlity 3?1 aud hence <?-bpp
complete with probability 32. Th( proof generalizes to yield simitar optimal sep-
arations between ?bPP?completeness and ????tt?completeness and between ??P?P
reductions with different probabilities.
The following analogy illustrates the intuition behind the construction of A:
Suppose we put in A `few' strings of the form Oxf 1,2, 3? and `most' strings of the
form 1x?1, 2, 3? while inaintainilig ??3??0??-completeness and ??3--Hdisj-completeness.
If we can then construct LA su(? ihat any higit prol?abllfty reductioii from 1'A -to
A must either produce `lots' of strings in A of the form 0x?1, 2,3) or produce `lots'
82
of strings in A of the f:?rm 1x?1, 2. 3t then the properties of A would ensure that
LA can not reduce to A via high probability reductions. In the actuJ construction
the terms `few', `most' etc. would it4er to probabilities and not nunibers.
Theorem 5.5 The? exists a set A which is complete for E?2 under ffif3??isjani?
?P3??0?j.reductions (and hence <:brnI?P?complete with probability 4) but not ?bpp
complete with probability 4 + poty1(n)
Proof: Let U be the standard complete set for E?2. The set A will be a subset
of (0 + 1)?*(1 + 2 + 3) and have the following form:
1. The strings ini, 1u2, 1u3 wiji be in A for all u ?
2. Exactly two of the strings 1??i1, 1?2, 1n3 will be in A for each a E 17
3. Exactly one of tbe strings Oil, 0n2, 0u3 will be in A for each `a C
4. None of the strings O?u1, ()?i2, QF?3 will be in A for u E ET
It is easy to check that conditi??ns 1 and 2 ensure that A is bard for E? un?ier
<:? -reductions and under p?oabihty l ?Cn0???P?reductions. Also conditi??ns 3
--H 3--HconJ			3
and 4 ensure that A is hard for L?2 under ??3--Hdisjreductions and under probai?ility
1 ??rnP?reductions The following lemma shows that A is also hard for E?2 under
3
probability 4 <:bPP?reductions.
Lemma ??? ? ?bpp 4 with probabilfty 4.
Proof of Lemma: Consider the frillowing random reduction ftorn U t() A:
o+ On input x, choose i unifornily from fO,1? and) uniformly from tl,2,31 arid
output ix).
If x C U then the only cases when ix) ? A are when i 0 and Ox) is one
the two such strings not in A (se condition :3). Thus the error probability is ii..
Similarly if x is not in U then <tn error occurs only when i 1 and ix) is one
83
the 2 such strings not in A (condition 2). Thus, the reducti??n is a probability 2
3
?bpp?reduction.
A is constructed by diagonatizing against all probabilistic polynomial tirn?'
transducers Rj to ensure that for each I?j, for infinitely many n, the following
two conditions are satisfied:
(a) For each u C U, the probability that J?j(0fl) outputs a string of the form Ouj
in A is at most ??? + & of the probability that it outputs any string of the form
Ouj, where j ? ?1,2,3). Here & is a very small (2cm for some c ? 0) en?r
parameter.
(b) Foreach u ? U, the prnbal?lity that J?j(0fl) outputs a string of the form 1?u,j
in A is at least ??2 --H & of the probability that it outputs any string of the fon?
Thuj.
A is constructed in stages. Let n0 1 and A0 Q). Stage i tn'es to diagonalize
against Rj.
Stage i: Let n = flj. By ass'Iml)ti()n. the running time ofRj(O?) is at most n?. ]f
this exceeds ?Iog(n) then set ?Lj? 1 2???, extend A by adding all strings of the foun
Oul, lul, 1u2, 1u3, lul and l?2 o? lengths between n? + 1 and flj+1, where u ?
and u ? F? and go to the next stage.
Otherwise, use the ??2 oracle t() find m, the length of the largest stn'ng output
by Ri(O?) on some path, Add to A strings of the form lul 1u2 and [u3 where
u E U and n + 1 ? Ivil ? m. 10 m??et diagonalization requirement (a), for eah
u C U such that n + 1 ? in) ? mi, estimate the probabilities that Rj(O?) outputs
On), where) ? ?1, 2,3). Among the three strings Oni, 0n2 and 0n3 put into A, the
string with the lowest estimated probability. To meet requirement (b), for each
U such that n + 1 `? in) < mi, estimate the probabilities that Rj(O?) outputs
1?n), and put into A tbe two strings with the lar?est and second lai??st estimated
probability.
84
It is clear that if exact probal?ilities were used in this step then both the condi
tions would be satisfied with & 0. As we have done before we can argue that th(
use of estimates only adds a small (inverse exponential) error paranieter &. Thus,
both conditions are sa?isfied and we say that Rj has been diagonalized at length
n. For lengths between m + 1 and ?t?t1 2flj add to A all strings of tlie form Oul,
lul, 1u2, 1u3, lul and 1=2zt where'u ? U and Ti C U.
By construction A is in E?2. We now explicitly construct a set LA in E?2 which
does not reduce to A by a probaThiity 32 + pol?(n) reduction.
Lemma 5.5 There exists a set L?1 in E?2 which is not reducible to A by a prob-
ability ?32 + poly1(n) ?bmPP-reduction.
Proof: The language ?A is deline?i c5 follows: On input ? i, O'? >:
o+ Construct A<?fl. Since there ;3??e at most ? n+1 elements to be tned, this can
be done in E?2. if on s??n)? p;?th J?j(0fl) runs for more than ?log(n) s?eps then
we reject.
o+ Define the following probabiiiti??s:
def
p = Prob[A??(< ?,U? > outputs a string in A<--H?].
def
q = Prob[P?(? i, O? >, o'ttputs a string in A--H or a string not in
(0 + 1)v?*(] + 2 + ?)1
def
r = Prob[i??(< i, 0? >) oittputs a string in 0?*(1 + 2 + 3) of length
greater than n].
def
s = Prob[L??(? i, 0" > oittputs a string in 1?*(1 + 2 -? 3) ()f lengtl
greater tliaii ?1
Note that p + q $ r + s 1. Estimate the probabllfties p and s with high
accuracy (within a multiplicative factor of 1 + ? where ? is inverse exp()neiL-
tial). If the estiniated pro bablli ties p and s sum to less thaii r? then accEpt
else reject.
85
The intuition why LA (an not reduce to A with `high' probability is as fol]ows: If
? i, D? >? LA then a ieduction from LA to A must produce of strings in A witit
high probability. Sinc' s is small' in this case that means a `large' probability
must be concentrated on strings the form Oxj ?n A. But condition (a) in the
construction of A ensures that this can not happen. A similar conflict occurs
under the assumption that <i, ()fl >? LA due to condition (b) and the definition
of LA.
We now carefully formalize this argument to show that there is no probability
32 ? 1 ?bPP?reduction from LA to A. Assume Rj0 carries out such a rediiction
oly(n) --Hm
LA to A. Let Rj be the machine which, on input 0?, simulates ??o(? ?o,D" >).
By the construction of A, Rj is diagonalized at infinitely many lengths. Consider
a large n such that Rj(Ofl) runs for at most ?log(n) steps and such that R? is
diagonalized at this length in the construction of A.
Suppose ? i0, 0? > belongs to LA. Then since R?0 reduces L4 to A, R5 outputs
a string in A with probability less than 1 _ 1 By definition of LA we know
3			poly(n)
that p+s ? ?21 and hence q+'r $ft 21 ex%' The probability qtr can be apporti?ned
into the following disjoint parts:
1. Probability q on strings in A? and strings not in the set (ot1)y?*(1t2+3).
2. Probability r1 on strings of the form Onj.
3. Probability ?21 on strings of the form On), I c fi, 2, 3?, which are in A
4. Probability r22 is on strings ??fthe form OQL), j E ?1,2,3?, which are not in A.
Note that only the strings whi?:h account for r21 are in A. Thus, we have that
q t r1 t T22 ? 1 _ 1 since this a bound on the that a
3 poly(n)'			probability			-?? outputs
string in A. Therefore.
1			1			1			1			1			1			1
___ --H (--H			--H-- --H --H			+
2			exp			3 )o1?(n)			6			exp pol'n(n)
But by construction of A, sinc( L) i5 diagonatized at this length we 1t;?e (from
condition (a) of the c??nstruction ()f A) that ?2t ?			+ ?)(r?? + ?22) Sin?e "?22 15
86
less than ? --H			1			we can derive that
3			poly
1			1
r21 <			+			--H --H_____
(? exp poit'(n)'
which contradicts the above lower bound for `r21. Thus, we can not have
? j0,()fl >E LA.
So ? ?o,O? >? LA. Then by defiuftion, R5 outputs a string in A with prob-
ability less than 31 --H p()1y1(n) By construction of LA we know that p + 8 >?21 and
1			1
hence p + 8 > 2 exp' The prob??bihty p + 8 is as before apportioned into four
disjoint parts as follows:
1. Probability p is on strings in A--H??.
2. Probability 81 is on stflngs of the form luj, 5 E f1,2,3).
3. Probability 821 is on strings of the form 1u5, 5 E ?1, 2,3), which are in A.
4. Probability 822 is on strings of the form 1?u5, 5 ? fi, 2,3), which ar? not
in A.
Only strings which contribute to 822 tre in A. Thus, P + 81 + 821 --H poty1(n) and
hence
1			1			1			1			1			1			1
822 > --H -- ___ --H			--H			)			--H			+
--H2			exp			3 po1?(n)			6			exp pol'y(n)
But by the construction of A Sin(?e we diagonalize the machine Rj at this stage
we have 821 > (32 --H ?)(821 + ,??). Since 821 is less than 1 _ 1 we h??ve
3			polv(n)
1			1			1			which contradicts the above lower bound for 822. Thus, we
822 ? 6 + exp po?y(n)
can not have ? j0,?fl ?? LA.
Since in either case (? i0,)? >E LA and ? j0,?fl >? LA), we obtained a
contradiction, it must be the case EA does not ?bPP?reduce to A with probability
32 + poig1 n			El
Using the same technb?ue we can prove the fotlowing:
87
Theorem 5.6 For an;q k there is a set which is --H??k--Hdisj complete and
complete for E?2 (and hence ?bPP?oomplete with probability 21 + T1k ) but not ?bpp
1			1			1
complete with probability 2 + 2k' + poly(n)
We can combine the techniques from the above proof and the proof of i;beoreni 5.(?
to obtain fine separations between ?bPP?reductions as in the case of ?rmP reductions.
We state the following theorem without the proof.
Theorei? 5.7 For any p, then is a set A which is ffi?rnP?complete for E?2 with
probability 2p --H 1 and also ?C0?rP?complete with probabitity 2p --H 1 (and hence
<bpp -complete with probability p ) but which is not ?bpp -complete `with probability
? + 1
po?y(n)
As before we note similar ?he??rems will hold for the class E and nice cl<?s
which contain E.
5.5 Discussion
We have shown that the class c?f ??omplete sets under random reductions is very
sensitive to very small changes in the success probability of reductions. We can
extend the arguments to show thc'tt even smaller differences (21En) are enough to
yield a different class (?f complete sets.
Most of the separation results obt?nned in the previous sections rely crucially on
the fact that the class in question is closed under complement. however by directly
extending the techniques of Homer [f[om9ol one can show that some of the results
of Section 5.2 hold for nondeterministic exponential tirne classes as well. Since there
are relativized worlds where BPP?.-NEXP we can not obtain separation results for
two sided random reductions in XEXP without first separating the base classes.
However even though we know I?P#NEXP we are unable to obtain separations
of completeness under one side(l (,rr?)r random reductions in NEXl? ai?d we leave
this as an open question.
Chapter 6
Random Reductions and Sparse
Sets 1
The class NP plays a central rote in structural complexity theory. Great effort has
gone into understanding the structure of this class both for theoretical ?`tnd practical
reasons. In 1977, drawing from 4he evidence available, Berman and Hartmanis
postulated their famous conjecture that all NP-complete sets are p-isoinorphic
[Bll77]. This drew a lot of attentio? from the comple?ty theory community. ?ince
proving the isomorphism conjecture is at least ;? hard as proving P ? NP, efforts
were concentrated on ])roving thai; it was false. One way to do so is to show that
there is a sparse NP-complete set. l3ut, Karp and Lipton showed that even this may
be quite difficult by proving that ii' there is a sparse NP-hard set then Pli collapses
[KL8o]. Then, in a much celebrated result, Mahaney showed that existence of a
sparse many-one NP-bard set implie? that P NP and hence, contrary t() belief,
that NP is feasibly re?:ognizabli [?tah82]. This led researchers to investigate tlie
more general problem : For what other types of reductions ??, does th( existence
of a sparse r-hard set for NP impiy that P NP. In a beautiful resnlt, Ogiwara
and Watanabe show that this is true for bounded truth-table reductions which ai?e
1The results presented in this chai)tE? have been drawn from [RR92]
88
89
much more general than many-onQ reductions [OW9O].
In this chapter we investigate random reductions from NP-coinplete sets t()
sparse sets. We will show that the ??stence of a sparse set which is NP-hard under
<mco?rP -reductions with non-negligible probability, would imply that NP=?P and
hence all languages in the Polynomial-time Hierarchy can be recognized feasibly.
This provides a strong evidence for the non-existence of such sets. Random reduc-
tions from NP-complete sets to sparse sets have been studied earlier by Mahaney
and Simon [MS81], but the random reductions they considered did not make any
errors but instead could fail to produce any output with small probability. More-
over, they showed that existence of sparse NP-hard sets under these reductions
would imply NP--H--Hco-NP. We str?ngthen these results in two ways. Firstly, we
consider reductions which are allo??d to err in one direction. Secondly we show
that existence of sparse NP-hard sel;s under these reductions implies NP=RP which
immediately provides efficient ran?lon?ized algorithms for the PH. This sort of fea-
sibility is not known io follow fr()m NP--H--Hco-NP. Since Mahaney's techniy?e is
not easily extendible to random reductions, we use the properties of the left ?et
of SAT to prove our results. ??he left set of SAT also played a key role in the
Ogiwara-Watanabe result.
6.1 Definitions
Convention Since we will be considenug random reductions to NP which is a
robust class closed un?[er OR2, ORw and majority, the the success probabili(? of
the reductions is not of much C0iiC(?rn. In this chapter we will use the symbols ? rp
and ?co--Hrp to denote ?rp an?l ffimCO??P reductions will success probability 3/4.
Due to the robustness of NP all ()?1' results hold even if the success probability
was defined to be as low as J /p()l?.
We now introduce the langiia?e LSAT, wbich is the left set of th( langu?'i?e
SAT. The language L?AT pl?yed a major role in the Ogiwara-\Vatanabe proofl
90
We will be using it ext??nsively iii this chapter.
Definition LSAT ? < x, w > ?W1 W ? w' and w' satisfies x ?. Here x is
a boolean formula and w, w' C ?0, l1? are truth assignments to its n va?abl??s,
represented as bit strings.
We shall often be talking about intervals. By the interval (`Wi, W5) we mean the
set ? W Wj ? W ? Wj ?. We assume that all of w, Wj, Wj E tO, itt for some t. iii
this chapter whenever we talk of ordering of strings, we mean the lexicographical
ordering. When we talk of ordering of intervals, we mean the lexicographical
ordering according to their left end-point. An interesting and very useful property
of LSAT is that, if < X, W >E LSAT and W? ? W then ? ?, W1 >E LSAT
6.2 Main Result
Theorem 6.1 For anv sparse set S, if SAT ?cmo?rP S then NP--H--HRP.
Proof: Let S be a sparse set sucb that SAT ?mco?rP S. Let 1 be a polynomial snch
that S<--H? ? 1(n). Our aim is to exhibit an RP algorithm for SAT. Recall thai this
means that given a formula w, the ;tlgorithm should accept x with high probability
if x is satisfiable and reject x otherwise. To do so, we shall use the language LSXl'
defined previously. As LSAT ?? SAT, by composing reductions LSAT ?c?o?rP ?
Let g be this reduction. Hence we have that,
o+ ? X, W >? LSAT ? g(? x, W >, z) c 5' for all z,
3
o+ ? X,W >? LSAT ? PrzLq(< X,W >,z) ? 5'] > 3,
where z is chosen uniformly at random from ?0, 1jq(?<x,w>?) for some polynomial q.
We use the interval search technique developed in [OW9o] combined with a
new idea to device an RP algorithm for SAT. The algorithm works as follows
Algorithm RCllECKSAT
Input : A boolean formula x ha?ing n variables.
91
o+ Let p denote a poJynomial having the property thM g(? x. zt >, ?) ? x
Let N 1(p(Ix )) and consider the interval (U?. 1?).
o+ Partition this interval into N smaller intervals of roughly equal size, that is,
no two interval sizes differ by more than 1.
o+ While there are intervals of size > 1 do
Split each interval ilito two smaller intervals of roughly equal size
(*)Eliminate intervals from the set of resulting intervals using the inter
vat elimination procedure described below With very high probabilit,??
this procedure retains the interval containing Wrnax, the lexicographi-
cally largest satisfying <`?ssignment of w. No more than N intervals will
remain after this proce?Jure terminates,
o+ If any of the remaining w's ?atisfy x then accept else reject.
end RCllECKSAT
The main idea in this proof is ;3??comphshing interval elimination in siep (*) of
the algorithm, that is, ehminating enough intervals efficiently in a way such tha?
with high probability the interval contaim'ng QL!max, is not dropped. We ?`al1 this
the subset technique. The interval elimination procedure is carried out as follows
Procedure INTERVAL-ELIMINATION
Input tt1, t2 . . . ?, a collection of intervals ordered from left to right.
o+ Let Wj denote the lefimosi pCint of the interval J?.
o+ For each interval tj, pick ?? . . Zm at random (m to be specihed later) and
let Wj = ? 9(X,Wi,Zk) 1 ? k ? Tn
o+ (t)Find the least ? (if it e??'sts) such that W5 > V. Let ?) denote this
index. Eliminate all inter?als t?, i > jo.
92
o+ Repeat the following unti] fl() more changes occur
--H For simplicity, call the remaining intervals consecutively from left to
right ri,??... and rename the Wj'5 correspondingly.
--H Find the first i such that ?Vj C Uj<iW?. Remove tj?1.
end INTERVAL-ELIMINATION
We now show that this interval elimination procedure retains the interval con-
taining Wmax with very high probability.
Intervals are eliminated by the elimination procedure in two cases. In the
first case, an interval ?? is dropped if i > ?o (see t) We claim that this interval
cannot contain Wmax, for if it did, then each of ? x, W1 >? X, Wj0 > would
be in LSAT. Hence ?..... , W?0 would all be subsets of S by the definition of the
reduction g. Hence, Ui?i0 Wj is a subset of S. Since there are at most N elements
of S which 9 can map onto, and Ui<i0 Wj > N, we get a contradiction.
For the second case note the foltowing : Let tmax be the the interval that
contains Wmax (if x is satisfiable)? By definition of g, for all i ? max, Wj % S.
Also, for all i > max, the probabi]ity that Wj C S is less than 1/4rn. He'ice, the
probability that any of the Wj, i ? n?ax, is a subset of S is less than 2iV x 1/4rn.
Note that, tmax cannot be dimhtated unless there is an interval tk to its right such
that Wk C Uj<?max ifl C S. Hence the probability that t.max is eliminated in any
single execution of the interval elimination procedure is less than 2N/4rn. Since
this procedure is executed at most n times by the algorithm, the probability that
tmax is ever eliminated is less thait n x 2N x 1/4m which cait be made arl?itrauly
small by the choice of a proper polynomial for m.
We now prove that after tht elimination procedure terminates, no more than
N intervals remain. The elimination of the intervals i0 and beyond (see t) ensures
that there are at most N elemeifts in the remaining intervals. Suppo??e at th(' end
more than N intervals remain. C?ll the first N + 1 intervals ti ... tN+1 and tlie
93
corresponding sets W1 ... WN+I. Since for all i, Wi ? Uj<iWj, by induction it can
be shown that the cardinality of Wj is at least k. Therefore. Uj<?(N+1) Wj >
N t 1 which is a contradiction.
It is easy to see that algorithm R,CHECKSAT runs in polynomial time. it never
accepts unsatisfiable formula and accepts satisfiable formulas with high probability.
Hence, it is an RP algorithm for SAT.
Using the same idea, we can establish the following:
Theorem 6.2 Fof an?j spa?se set S if SAT ?co--Hrp S then NP --H--HRP.
Theorem 6.3 PoT an?j spa?se set 5, if SAT ??conj5 then P--HNP.
This result has been obtained independently by Arvind et al [AHllN92i. Our
technique also proves the result ft?r SAT but this was already kiiown [Ukk83,Yap83].
From the above theorems we also get the following corollaries:
Corollary 6.1 For any tally set T, if SAT(or SAT) ?rp T tlten NP=:RP
Corollary 6.2 For any tally sei I., if SAT(or SAT) ?%sj T then P--H--H?P.
The result for SAT in CoroPaiy (;.2 also follows Irom [Ukk83,Ya1?83] and th0
result for SAT also follows from t?e independent work of Arvind et al [A1111K92).
6.3 Open Prob1em?',
1. Can the similar results be ol?tained for ?rp -reductions tc sparse sets ?
2. Can similar results be obtaiited for --H??disj -reductions to sparse sets ? This
may be difficult in light of thc fact that ??disj -reductions to sparse sets are at
least as powerful ;? bounded (ruth-table reductions to sparse sets [EHOW9lJ
Bibliography
[ABG9Oj
[AG88]
[A11llK92]
[AKL+ 79j
A. Amir, II. Beiget, and W.I. Gasarch. Some ?onnections between
bounded query classes and non-uniform complexity. In Psoceed?ngs of
the 5th St??ucture tn (?ntplewzt? Theo?? Confem'nce, pages 232--243,
July 1990.
A. Amir and W. I. G?'tsarch. Polynomial terse sets. J?iforntatz'on and
Computatzom 77:37--5(j, April 1988.
V. Arvind, Y. llan, I?. ilemachandra, and J. Ko?bler. Reductions to sets
of low information ?.ontent. In Proceed?ngs of the 19Th Interttatio'i?rtl
Colloqu?unt on A'alo'n?iia., Langua?es, and Pnog?ni?ntng Springer Ver-
lag Lecture Notes `in (%rnputer Science #650, pages 162--H173,1992
R'. Aleliunas, R. M. Narp, R. J. Lipton, L. Lovasz, ?Ld C. liac:k??ff.
Random walks, uni?ersal sequences and the complexity of maze I?r(?b-
lems. In Pnoceedin?t' of the IEEE Syntposiu? on Foundat'on? (?f ()?m-
puter Scie'?ce, pages 218-?223, 1979.
[ALM+92i 5. Arora, C. Lund, R. ?iotwam, M. Sudan, and M. Szegedy. I?roof
verification and hardness of approximation problems. In Pwceedings
of the IEEE Symposiu?n on Foundations of Computer Science, pages
14--H23,1992.
[AM77]
[AS92j
L. M. Adleman and I?. Manders. Reducibility, randomiiess, and in-
tractibility [sic]. In A CM S?mposiunt on Theory Qf Con??uting, pages
151--H163,1977.
5. Arora and 5. Safia. Probabilistic checking of proofs; a new charac-
terization of np. In Proceedings of the JEFE Symposium on Founda-
tions of Computer Science, pages 2-13,1992.
[13ab85] L. Babai. Trading group theory for randomness. In ACA! Symposium
on Theory of Compat?ng, pages 421--H429,1985.
94
95
[BDG90]
[Beij
[Bei88]
[Bei9 1]
[BF90]
[BG82]
[BH77]
[BHT90]
J. L. Balcazar, J. Diaz, and J. Gabarro. Structural CompThxity J.
volume 11 of EATCS Alonograpks on Theoretical Computer Science.
Springer-Verlag, 1990.
Richard Beigel. Bi-immunity results for cheatable sets. Theoretical
Computer Science. To appear.
R. Beigel. NP-hard sets are p-superterse unless R NP. Techiii-
cal Report 4, Department of Computer Science, The Johns Hopkins
University, 1988.
R. Beigel. Bounded queries to sat and the boolean hierarchy. Theo-
retical Computer Scie'?ce, 84(3): 199--H223,1991
L. Babai and L. Fortuow. A characterization of ?P by <`tnthnietic
straight line programs. [n Proceedings of the JEFE S??posium oTt
Foundations of Cornpute?' Science, pages 26--H34,1990.
A. Blass and Y. Gurevich. On the unique satisfiability problem. Jn-
formation and Contwi, 55(1--H3):80--H88, 1982.
L. Berman and J. H;?trnanis. On isomorphisin and density of NP and
other comj?lete sets?JAM Journal on Cornputing, 6:305-322, Jun?
1977.
II. Buhrman, 5. IIon?ei', and L. Torenvliet. On complete sets for ncn?le-
terministic classes. Te'hnical Report 90-013, Dep;irtment ?f Com??u?:cr
Science, B??ston Un iveI%',i?y, 1990.
[BHZ87j R. Boppana, J. llastaJ, ?`tnd 5. Zachos. Does co-NP have short iM?i-
active pro??fs? i?tformation Processing Letters, 2"?(2):1 27??1 32,1 9S7.
[CGll+88j J. Cai, T. Gundermanii, J. Hartmanis, L. Hemachandra, V. Seweis??n,
1K. Wagner, and G. V?chsung. The Boolean hierarchy I: StructurJ
properties. SJAAf Jou?wal on Computing, 17(6): 1232--H1252, December
1988.
[CH86]
[Cha89j
J. Cai and L. A. Hemachandra. The Boolean hierarchy: hardware
over NP. in Strntcture in Complexity Theory, Spnnger-Veilag Lectu?'e
Notes in (?niputer Science *223, pages 105--H124,1986,
R. Chang. On the structure of bounded queries to arbitrary NP set?.
In Proceedings of the .`?th Structure in Complexity Theory Conference,
pages 250-?58, Jun? 1989.
[Cha91] R. Chang. On the St?"i'?cture of NP Computations under Bo?)l?an 0]?-
erators. Ph.D. dissertjiiun, Cornell University, 1991.
96
[CK90a]
[CK90bj
[CKR91]
[CR93]
[CR593]
R. Chang and J. Kadiri. The Boolean hierarchy aiid the polynomiat
hierarchy: ? closer connection. In J#oceedings of the F)th Structure i??
CompThxity Theory Conference, pages 169--H178, July 1990
R. Chang and J. Kadin. On computing Boolean connectives of charac-
teristic functions. Technical Report 90-1118, Department of Computer
Science, Cornell Univen',ity, May 1990.
R. Chang, J. Kadin. and P. Rohatgi. Connections between the com-
plexity of unique satisliability and the tbreshold behavior of random-
ized reductions. In Proceedings of the 6th Structure in (?niplewity
Theory Conference, pages 255--H269, July 1991. To appear in the Jo?tr-
nal of Computer and System Sciences.
5. Chari arid P. Rob atgi. On completeness under random reductions.
In Proceedings of the 8th Structure in Complewity Theory Conference,
pages 176--H184, May lP93.
5. Chari, P. Rohatgi, <ind A. Srinivasan. Randomness oplimal uni(lu
element is??lation with applications to perfect matching aiid related
problems. In ACAf Symposium on Theory of Computi??, pages 458--H
467, 1993.
[EHOW91j E.Allender, L. llemacbandra, M. Ogiwara, and 0. Watariabe. RAating
equivalenc?? and redticil?lity to sparse sets. In Proceedings of th?? t)%1?
Structure ?n Comp'?xity Theory Conference, pages 220?2'.?9, 1?.)91.
[FGL+91j U. Feige, 5. Goldw?isser, L. Lovasz, 5. Safra, aiid NI. Szegedy. Ap-
proximating clique is <ilmost up complete. in Proceedings of the JEEP
Symposiun? on Fonnd??tions of Computer Scienc?, pages 2--H12, 1991
[GJY87]
[GMR89]
[GY89]
J. Goldsmith, D. Joseph, and P. Young. A note on bi-in?munfty and
p-closeness of p-cheatable sets in p/poly. Technical Report 87-11-O??,
Department of Coinpiiier Science, University of Washington, 5e<ttil?<,
November 1987. To appear in JCSS.
5. Goldwasser, 5. Mic<iti, and C. Rackoff. The knowledge complexity
of interactive proof-systems. SlAM Journal on Computing, 18( 1):186--H
208,1989.
R. L. Grab am and A. C. Yao. On the improbabllity of reaching byzan-
tine agreements. In ACA' Symposium on Theory of Computing, pages
467--H478,1989.
[Haul4] F. Hausdorff. Grun?lzitge der mengenlehre. Leipzig, 1914.
97
FHe1861 II. Heller. On rAativized exponential and probabilistic complexit?
ctasses. Inlormation and Control, 71:231--H243,1986.
[Hem871 L. Hemachandra. Courttiny in Structural Complexity Theory. Ph.D.
dissertation, Cornell University, 1987.
[Hom90]
[HU79]
[Kad88]
[Kad89]
[KL80]
5. Homer. Structural properties of nondeterministic complete sets.
In Proceedings of the 5th Structure in Complexity Theory Confrrt'nce,
pages 3--H10, July 1990.
J. Hopcroft and J. Uliman. Introduction to Automata Theory, tan-
guages, and Computation. Addison-Wesley, 1979.
J. Kadin. The polynomial time hierarchy collapses if the BoAean
hierarchy collapses. SlAM Journal on Computing, 17(6):1263--Hl282,
December [988.
J. Kadin. pNP[logn] and sparse Turing complete sets for NP. .Thur?tal
of Computer and System Sciences, 39:282--H298, December 198?).
R. Karp and It. Lipton. Some connections between nonuniform and
uniform complexity classes. In ACM Symposium on Theory of (?n?-
puting, pages 302--H309, 1980.
[KM8l] K. Ko and D. Mo??re. Completeness, approximation and density.
SlAM Journal on Computing, 10:787--H796,1981.
[Kre881 M. W. Krentel. Tlie c??mple?ty of optimization problems. Journal of
Computer and System Sciences, 36(3):490--H509, 1988.
[KUW861 It. M. Karp, E. Upfal, and A. Wigderson. Constructing a perfect
matching is in Itandon' NC. Combinatorica, 6(1):35--H48, 1986.
[LFKN90]
[LL575]
[LP81]
C. Lund, L. ?ortnow, II. Karloff, and N. Nisan. Algebraic niethods for
interactive proof systems. In Proceedings of the lEEE Symposium on
Foundations of Compnter Science, pages 2--H10, 1990.
It. E. Ladner, N. A. Lynd?, and A. L. Selman. A companson of po]y?io-
mial time reducibilities. Theoretical Computer Science, l(2):103-123,
1975.
II. It. Lewis and C. \Y. Papadimitriou. Elements of the Theory of
Computation. Prentice-Hall, 1981.
C. Lund and M. Yannak??kis. On the hardness of approximating min-
imization problems. iii ACM Symposivm on Theory of (.`ompt&i??,
pages 286--293, 1993.
[LY93?
98
[Mah82]
5. Mahaney. Sparse complete sets for NP: Solution of a conjecture of
Berman and llartman's. Journal of Computer and &ysten? S?'iences,
25(2):130--H?43, 1982.
[MS81] 5. Mahaney and J. Sirnon. Polynomial self-reducibility and spaiseiless.
Manuscript, 1981.
[MVV87] K. Mulmuley, U. V. Vazirani, and V. V. Vazirani. Matching is as easy
as matrix inversion. Combinatorica, 7(1): 105--H113,1987.
[OW90] M. Ogiwara and O. N\7atanabe. On polynomiat time bounded truth-
table reducibility of np sets to sparse sets. In ACM Symposium on
Theory of Computing, pages 457--H467, 1990.
[PY84j
[PZ83j
C. Papadimitriou and M. Yannakakis. The complexity of facets (an?l
some facets of complexity). Journal of Computer and System Sciences,
28(2):244--H259, April 1?)84.
C. Papadimitrion and 5. Zachos. Two remarks on the power of coujit-
ing. In Sixth CI ConI?rence on Theoretical Computer Scienc?', pages
269--H276. Spflnger-Veri??g Lecture Notes in Computer Scienc? #14k,
1983.
[Rab80] M. 0. Rabin. Probabitistic algorithm for testing pn'm<?t? Journal of
Number Theory, 12: [25--H138,1980.
[Roh92]
[RR92]
[Sch89]
[Sha90i
[Sto83]
P. Rohatgi. Saving (jueries with randomness. In Pn?ceedings of the `7th
Structure ?n Complex?ty Theory Conference, pages 71--H83, June 1992.
To appear in the Journal of Computer and System Sciences.
D. Ranjan and P. Rohatgi. On randomized reductions to sparse sets.
In Proceedings of the 7th Structure in Complexity Theory Confrrencc,
pages 239-242, June 1992.
U. Scho?ning. Probabilistic complexity classes and lownes?. Journal of
Computer and System Sciences, 39(1):84--H100, 1989.
A. Shamir. IP PSl)ACE. In Proceedings of the JEFF Symposium
on Foundations of (lomputer Science, pages 11--H15,1990.
L. J. Stockmeyer. ?`he complexity of approximate counting. In ACM
Symposium on Theory of Computing, pages 118?126, 1983.
5. Toda and M. Ogiwara. Counting classes are at least as hard as
the polynomial-time hierarchy. In Proceedings of the 6th Structvre in
Complexity Theory Conference, pages 2--H12, July 1991.
[TO91]
99
[Tod89]
[Ukk83]
[VV86]
[Wag86]
[Wat871
[Wil85j
[WW851
[Yap83]
S. Toda. On the computational power of PP and E)P. In Pwceedings
of the JEEF Symposiun? on Foundations of Compute? Science, pages
514--H519, 1989.
E. Ukkonen. Two results on polynomial time truth-tablt' ?educlions
to sparse sets. SIAAI Journal on Computing, 12(:3):580--H587, 1?)83.
L. G. Valiant and V. V. Vazirani. NP is as easy as detecting unique
solutions. Theoretical Computer Science, 47(1):85--H93, 1986.
K. W. Wagner. More complicated questions about maxima and min-
ima and soaie closures of NP. In Proceedings of the 13th International
Colloquium on Automata, Languages, and Programming, pages 434--H
443, 1986. Volume 226 of Lecture Notes in Computer Science.
0. Watanabe. A companson of polynomial time completeness notions.
Theoretical Computer Science, 54:249--H265,1987.
C. Wilson. Relativized circuit comple?ty. Journal of C??mputer and
S?stem Sc'ences, 31(2):169--H181, 1985.
K. Wagnei and G. ?\r???5??g On the Boolean dosure of NP. I]1
Proceedings of the 1985 International Conference on Fun?YamentaTh cf
Computation Theor?, pringer-Veilag Lecture Note? ii? (??mputer Sc?-
ence #199 pages 485--493, 1985.
C. Yap. ?;ome conse(luences of non-unfform conditioiis on ?tniform
classes. Theoretical C??m??uter Scie??ce, 26(3):287?-3OO, 19?3.
S. Zachos and II. lieller. A decisive characterization of BPP. 1nfa?
mation and Control, 69(1--H3):125--H135, 1986.
[ZH86j
