O such that

).
(a)
HN <-+v QUAD <-+v 4FEAS
(b)
QUAD <-+11 IP <-+11 IPF
References for all of the above resn.lts can be found in (2J
3.7 The Class NPR
The definition of NPR given by Blum et al is a generalization of the classical characterization of NP as t.he class of decision problms which are verifiable in polynomial t-ime. The idea of verifiability is roughly the following: for many decision problems S. it seems difficult to determine whether an arbitrary input r; is a member of 5'. For some of these problems. however. there exist '·short" proofs
3.7. THE CLASS NPR 29
of the fact that s E S.
A classic example of such a problem is SUBSETSUM , which asks, given a set of numbers X = {x1. X2-..•xic} and a target t. is there some subset Xt X such that Lxex, = t. This problem is clearly decidable. since there are only finitely many possible subsets to check, but it is unclear how we might go about finding such a subset (or proving one does not exist) in a way that is more efficient than checking all the subsets. On the other hand, it is easy to convince someone that a particular instance of SUBSETSUM is, in fact, a Yes-Instance once we know the correct. subset. For example. given a problem instance
X= ({L 15, 7. 44. 3. 9, -4, 5. -3. 2, 8}, 31)
we can determine immediately that X is a Yes-Instance if we arc given the set. S = {1. 15. -4. 5, -3. 8. 9}, because we can verify that S is a subset of the problem instance set that adds up to the problem instance target. Thus, while it's unclear if SUBSETSUM L<; efficiently (i.e., polynomial time) decidable. the above considerations lead us to say that SUBSETSUM is efficiently verifiable. The complexity class NPR represents the class ofproblellls that share this feature of efficient verifiability.
Definition 3.7.1. Class NP over R
A decision problem S Roc over a ring R is in the class NPR if there exist positive integers c and q and a BSS Machine M over R with 'LM = R'>O x R00 such that:
L If.1: E S then there exists awE R00• such that M accepts (w. x) aud costAT(w. x) c(size(x))q
2. If :1: (/:. S. then there is no such w sueh that M accepts (w. x).
Example 3.7.2. The decision problem HN is a. member of NPR for R = JR, R = C. and R = Z with unit. cost. (Recall that an instance of HN is an encodiHg of some of polynomials S = {p1,P2-...•pk} c R[x1 , x2, . . . , x,, ]. and that an instance is a Yes Instance if there exists some x E R" such that for each J>i E S. p,(.1:) = 0.) To show that HN E NPR, we must exhibit a machine which takes as inputs pairs (to.x). and for each x. accepts some pair (w.x) in polynomial time if and only if x the polynomials encoded by x have a shared zero.
The following algorithm describes a machine with the desired properties.
Algorithm 3.2 NP MachiM for HNn
Input: wE R00. X= ({PI-P:2· ... pk} C R[x,. .c2. . . . . Xn]) for i= 1 k do
Evaluate Pi 011 the first. k coordinates of w and write the output. to out. if out I= 0 then
Reject
end if
end for
Accept
Chapter 4
NDET-Machines
So far, we have focusccl our attention on presenting the BSS Machine model as it appears in [2] and [3]. Where we have made modificatiom; to the theory, our changes have been essentiaUy cosmetic. and our original contributions have primarily taken the form of new examples and (hopefully) clear explanations of some of the more ter,;c sections of the original material.
In this chapter, we pn•sc•nt an extension to the BSS Machine model that gives rise to an alternative generalization of the complexity class NP. Our contribution is motivated by the following observations:
•
In Definition 3.7.1. we characterized the relativizcd complexity class NPR as tile class of decision problems efficiently verifiable by standard BSS Mad1ines. This definition generalized the characterization of the classiral NP as the st>t of decisiou problems efficiently verifiable by a st.andard Turing Machine. 1
•
In classical theory of computation, there are many ways of characterizing NP. An important definition for dccisiou problems equates NP with the class of problems that are efficiently decidable by a wore powerful class of 01achine called nondetermjnistic Turing Machines, or NTJ\Is.2
•
In the classical theory. the standard proof of the equivalence of efficient verifiability and efficient nondeterministic cornputability depend'> crucially on the fa.ct that. Turing 1Iad1ines work with a finite alphabet. To our knowledge no proof exists that does not rely on this fact.
1 Recall that for a machine /Ill to be an efficient verifier for some decision problem S is for it to be the case that for each .; E S, there exists some additional input value tv such that 1'v1 accepts (tv, .•;) with polynomial cost if and only if rc E Syc•. Ignoring the technical details involved in defining acceptance and costs for TMs and BSS Machines, this definition holds equally well for both computational models
2There are other influential characterizations of NP in the classical theory. For example, Ill links membership in NP to a process of probabilistic verification using a logarithmic number of random bits. In this thesis, however, we focltl. primarily on generalizations from efficient computability by nondeterministic 'I\Jring Machines. Considering how other characterizations of NP translate to the BSS Machine model could be a promising direction for future work.
31
4.2. NONDETERMINISTIC CONIPUTATION FOR BSS MACHINES
The only change in the definit.ion of an NTM from t.h(. definition of a stan*M(X) to z. We denote the :wt of all halting computation branches in ¢M(X) by WM(x).
Note: Each halting computation branch of a machine J'vf is a finite sequence of configurations (z,.z2 .... ,zk) such that z1 is the in.it.ial ronfigurat.ion of M for some input x. Zk is a terminal configuration. and for all i < k. we have z; 1-z;+ 1 • Tim'S elements of IJ! 111 have exactly the same structure as the computat.ions of standard BSS Machines. which means that all the attributes and functions defined for BSS Machine comput.ations can be applied to NDET Machine computation branches. In particular. the cost of a computation branch can defined in e.xactly the manner we used to define cost for BSS Machine computatiOt1'5 in Definition 3.4.4.
Definition 4.2.5. NDET-Machine Halting, Acceptance and Rejection
An NDET Machine M is said to halt on input :c if it mntains finitely many vertice,s. Equivalently. an NDET Machine halts on :r if every directed path through 111(x) eventually reaches a terminal configuration. We use the symbol nM to denote the Halting Set of ]II[, which is the subset of IM on which M halts.
An NDET Machiue M is said to accept an i.npnt x if M halts on x and at. least one leaf of ¢M(:;;) is an accepting configuration of 1\1!.
If M halts on x and no leaf in ¢ M (x) is au accepting configuration, we say that. M rejects :.:.
4.3 Computation Cost for NDET Machines
Definition 4.3.1. Nondeterministic Computation Cost
Let M be an NDET 1\'I M(x).
Thf' cost of *