Minimization and NP multifunctions.
The implicit characterizations of the polynomial-time computable functions FP given by Bellantoni-Cook and Leivant suggest that this class is the complexity-theoretic analog of the primitive recursive functions. Hence, it is natural to add minimization operators to these characterizations and investigate the resulting class of partial functions as a candidate for the analog of the partial recursive functions. We do so in this paper for Cobham's definition of FP by bounded recursion and for Bellantoni-Cook's safe recursion and prove that the resulting classes capture exactly NPMV, the nondeterministic polynomial-time computable partial multifunctions. We also consider the relationship between our schemes and a notion of nondeterministic recursion defined by Leivant and show that the latter characterizes the total functions of NPMV. We view these results as giving evidence that NPMV is the appropriate analog of partial recursive. This view is reinforced by earlier results of Spreen and Stahl who show that for many of the relationships between partial recursive functions and r.e. sets, analogous relationships hold between NPMV and NP sets. Furthermore, since NPMV is obtained from FP in the same way as the recursive functions are obtained from the primitive recursive functions (when defined via function schemes), this also gives further evidence that FP is properly seen as playing the role of primitive recursion.
Introduction
When considering the analogy between the arithmetic and polynomial-time hierarchy, a standard
view is that polynomial time plays the role of recursive (though not always|see, e.g., Selman [9],
to which we will return). The polynomial-time sets are used as the base  p
0 of the polynomial
hierarchy and  p
is dened as those sets polynomial-time in an oracle for some  p
set. However,
this view is not unproblematic. The analogy of  p
i with  i indicates that NP \ coNP should be
identied with the recursive sets. Under the assumption that P 6= NP \ coNP, this leaves the
polynomial-time sets to be viewed in analogy with some smaller class.
A natural choice for this smaller class is the primitive recursive sets (or functions). This is backed
up by Cobham's [4] characterization of FP, the functions computable in polynomial time, by a
scheme of recursion on notation that is nothing more than an explicitly bounded version of primitive
recursion itself (formulated for binary words). Further, the work of Bellantoni and Cook [3] and
Report date: 24 Oct. 2000
Leivant [6] provides primitive recursive schemes for dening FP with no explicit bounds of any
rather controlling the primitive recursion by semantically-inspired, syntactically implemented
tiering notions. This approach to characterizing complexity classes without any explicit mention
of resources or bounds is typically referred to as implicit computational complexity.
However, if we are to identify FP with the primitive recursive functions and view NP \ coNP
as the appropriate analogy for the recursive sets, we are left with the following question: what is
the correct analog of the partial recursive functions? Of course, we expect some class of partial
functions. However, from a machine-based view of complexity classes, this is bound to lead to some
unpleasantness, as there does not seem to be a straightforward, \clean" way to dene complexity
of partial functions. This especially becomes clear if we insist upon some notion of time-bounded
machines which may not halt on some inputs. It is here that implicit computational complexity
truly shines. Since its characterizations make no mention of resources or bounds, it is natural to
extend the existing implicit characterizations of FP with operators analogous to the classical case,
and then analyze the resulting class of partial functions as a candidate for the analog of the partial
recursive functions.
Since one passes from the primitive recursive functions to the partial recursive functions by adding
the minimization operator to composition and primitive recursion, an obvious starting point is to
add a version of minimization to Cobham's, Bellantoni and Cook's, and Leivant's characterizations.
To understand the version of minimization that we use, consider the classical denition used for
the partial recursive functions:
To obtain a version of minimization appropriate to polynomial-time functions, we want to ensure
that the verication that a is in fact the minimum value requires a search over a polynomial number
of values. Thus we replace the bounded quantier with a sharply bounded one:
This denition immediately raises a
ag: minimization no longer denes a partial function, as
there could be several a satisfying 8b 0:'(x; (e.g., suppose that ' is 1 on all inputs of
length  3 and 0 on all inputs of length > 3; then this minimization would yield all a with
Thus our straightforward approach leads us to consider partial multifunctions which formally are
maps from the natural numbers N to P <! (N), the set of nite subsets of N. In retrospect, this
is not at all unexpected. A partial function satises the condition that for all x, '(x) has at
most one element. A partial multifunction is the same, except that '(x) has at most nitely
many elements. With the (essentially) unrestricted computational resources of recursive functions,
collapsing many values into one is not a problem. But when we restrict the complexity of the
objects under consideration, it is reasonable to assume that we cannot necessarily perform such
a collapse (e.g., if '(x) has too many elements), and so our \functions" must be allowed to have
many outputs.
Another view of this sharply bounded quantier is that instead of having multiple output values,
we should instead choose one of the values. This leads directly to the idea of a nondeterministic
choice in the computation, and in fact such function classes have been considered. In particular,
Selman [9] denes the class NPMV to consist of those partial multivalued functions computable
on a nondeterministic Turing machine in polynomial time. Here, \computed" means that y is a
possible output of '(x) i the TM has an accepting path on input x such that the contents of the
output tape upon halting are y. The main results of this paper are that when we add minimization
as above to the various primitive recursive denitions of FP, we obtain exactly the class NPMV.
Thus not only does the approach of implicit computational complexity provide a straightforward
way to generalize polynomial-time computable functions to a broader class that ought to correspond
to the partial recursive functions, it in fact gives a resource-free characterization of a previously-
dened class that asserts to play the same role, thus justifying the naturality of (what turns out to
be) the single class considered.
The plan of this paper is as follows. In Section 2 we provide the basic denitions, including a
notion of bounded minimization, resulting in an extension of the Cobham class. Section 3 contains
the proof that the extension captures exactly NPMV. In Section 4 we introduce a resource-free
notion of minimization within the framework of Bellantoni and Cook's safe recursion [3]. The only
other work we know of that directly addresses the issue of adding a minimization operator in a
similar way is Bellantoni's [2], where he adds an operator that is single-valued and total; we compare
our approach to his in this section as well. In Section 5 we consider the scheme of nondeterministic
recursion dened by Leivant in [6] and show that the (total) functions denable with this scheme
are exactly the total functions of NPMV (and hence are the total functions denable using safe
recursion our our notion of safe minimization). Finally, in the closing Section 6, we mention a few
straightforward results that reinforce the claim that NPMV is the correct analog of the partial
recursive functions and suggest further directions for study.
2. Definitions
We use lowercase Roman letters a, b, x, y for numeric variables. The length of a number, jxj,
is dened as dlog 2 1)e. We abbreviate a sequence x
x when k is not relevant.
The binary successors are s i and the binary predecessor is given by
A partial multifunction (pmf ) is a Alternatively, ' can be
viewed as a relation on N k+1 satisfying the constraint that for all  x, fy j hx; yi 2 'g is nite. We
use ',  , , and  to range over pmf's. Any total or partial function is identied in the natural
way as a pmf, and we assume this identication whenever we mention any functions or function
classes. We write '(x) 7! y when y is a (possible) output of '(x) and y < '(x) if there is some z
such that '(x) 7! z and y < z.
Our computation model is the register machine (RM) which consists of a nite set of states d
a nite set of registers  a nite set of instructions of the following form:
When in state d i , if  j holds x, store s 0 x or s 1 x in  j 0
and change to state d k .
When in state d i , if  j holds x, store p(x) in  j 0 and change to
state d k .
When in state d i , if the contents of  j are either 0 or s 0 x, change to
state d k 0
and otherwise change to state d k 1
Let M be a register machine. States of M for which there is at most one instruction are deterministic
states; the others are nondeterministic. M is deterministic if all of its states are deter-
ministic. A deterministic RM computes an n-ary partial function ' by storing the n arguments
in  entering state s 1 , and then executing instructions in the natural manner. If M
reaches a state for which there is no instruction, it halts, and '(x) is the contents of
wise, M never halts and '(x) is undened. For nondeterministic RM's, we assume there are two
distinguished states d acc and d rej for which there are no instructions. If M enters one of these
states, it is said to accept or reject its input accordingly. A nondeterministic RM M computes
a pmf ' by storing
x in  executing instructions in the obvious (nondeterministic)
fy j  0 contains y when M accepts
xg. A conguration of M is a list d
specifying a state and contents of the registers. A computation sequence for M is a sequence of
congurations such for all i < n, there is a transition of M from c i to c i+1 . We assume a
coding of register machines and congurations satisfying the condition that if e is the code of M and
z is the code of a computation sequence of length n for which every register in every conguration
stores a number of length  n, then z  seqbnd(e; n), where seqbnd is polynomial-time computable.
We also dene a polynomial-time function result so that if z is the code of a computation sequence,
result(z) is the contents of  0 in the last conguration of z. We shall consistently con
ate state,
etc. with their corresponding codes.
We will consider the following classes of functions in this paper:
FP: the class of total single-valued functions computable on a deterministic RM in time
polynomial in the length of the input.
NPMV: the class of pmf's computable on a nondeterministic RM in polynomial time.
PR: the primitive recursive functions.
REC: the partial recursive functions.
As noted by Leivant [6], Turing Machines and register machines are polynomial-time reducible to
each other, so our denitions of FP and NPMV correspond to the usual ones.
We will make use of the following operators on pmf's:
Composition: ' is dened by composition from  ,
when
Bounded Recursion on Notation: ' is dened by bounded recursion on notation (brn) from
when
and for all
Bounded Weak Minimization: ' is dened by bounded weak minimization (bwm) from
and , written
Bounded Witnessing: ' is dened by bounded witnessing from   and , written
Definition
1. The class C is the smallest class of pmf's that contains the projections, zero, binary successors
s 0 and s 1 , and smash function (x; y) 7! 2 jxjjyj and is closed under composition, brn, and
bwm.
2. The class D is the smallest class of pmf's that contains the projections, zero, binary successors
s 0 and s 1 , and smash function (x; y) 7! 2 jxjjyj and is closed under composition, brn, and
bounded witnessing.
Proposition 1 FP  C and FP  D.
Proof. Without bwm or bounded witnessing, both classes are dened as Cobham's characterization
of FP.
We will freely make use of polynomial-time computable predicates in the denitions of our func-
tions; in such cases, we understand that formally we are referring to their characteristic functions,
Specically, in a minimization of the form z < (x):P (x; z), we mean
z
Definition A pmf ' is polynomially-bounded (poly-bounded) if there is a polynomial p such that
for all
y, then jyj  p(jxj).
Proposition 2 Every pmf in C and D is poly-bounded.
Proof. This is a straightforward proof by induction on the denition of C.
By this proposition, we may assume that the bounding functions used in bounded recursion on
notation and bounded pseudo-minimization are in fact polynomials.
3. Machine Characterization
Theorem 3 Let ' be a pmf. The following are equivalent:
1.
2.
3. ' 2 NPMV.
Proof. (1) ) (3): This is proved by induction on the denition of C. The initial functions of C are
p-time computable, and hence in NPMV. When is given inductively, we assume it is computed
by a nondeterministic RM M in time p and similarly for other pmf's.
Suppose computed by the machine M as follows. On input x,
run M  on x; if it rejects, M also rejects. Otherwise, if M  accepts with output z, run M on
input x; z; if it rejects, M rejects, and otherwise M accepts with output that of M . Clearly M
computes ' and runs in time p  (n)
Suppose that '(x; z) is dened by bounded recursion on notation from ,  i , and 2 q(jj;jj) , where q
is a polynomial that is increasing in both arguments. Then for any z, we have '(x; z) 7! y i there
is a sequence t
and y, where z(i) is the i th bit of z. Furthermore, for any such sequence and all i, we have
. Thus to compute '(x; z), guess a sequence t
each t i < 2 q(jxj;jzj) and verify that the above condition holds for each element of the sequence
by running M or M  i
and comparing the output to the previous element in the sequence. If
none of the verications fails and t y, then accept and output y. Guessing the sequence takes
time and the verication takes jzjp(jxj; q(jxj; jzj)) time.
Finally, suppose that We compute '(x) as follows. Run M  on
input x. If it rejects, then reject, and otherwise guess y smaller than its output. Next verify that
reject if not. If the verication is successful, run M on input x; i for every i < jyj.
If any of the computations accepts with output 0, reject, and otherwise accept with output y.
our assumptions about coding of RM's given in Section 2. For any polynomial q,
let T
x; z) be a modied Kleene T -predicate that asserts the following:
e is the description of some nondeterministic RM N ;
z is a sequence c each c i is (the code of) a conguration of N , c 0 is
the initial conguration of N on input  x, and for all i, c i+1 is a conguration of N reachable
from c i in one step of the transition relation of N ;
is an accepting state of N (note that c k may be repeated any number of times); and
Now suppose that M is a nondeterministic RM with code e that computes the pmf such that for
all  x, all computation paths of M have length  p(jxj). Dene ' by
We claim that y, then by denition there is some z that codes a computation
sequence of M on input  x of length < p(jxj) such that y is the contents of  0 when M enters
state d acc , and hence (x) 7! y. Conversely, suppose that (x) 7! y. By denition, there is
an accepting computation path (code) w of M on input
x with length < p(jxj) (and hence w <
seqbnd(e; p(jxj))) and that ends with y in  0 . Since we allow the accepting state to be repeated any
number of times, we may assume that j seqbnd(e; p(jxj))j < w and so we have j seqbnd(e; p(jxj))j <
w). The only reason we might not have '(x) 7! y is that there could be a much
shorter accepting computation path with output dierent than y; the weak minimization operator
would then \reject" w and \pick up" this shorter path instead. But if w 0 < jwj, we have w 0 <
and so this situation does not arise. Hence
z < seqbnd(e; p(jxj)):j seqbnd(e; p(jxj))j < z
and therefore '(x) 7! y.
The proof that (2) and (3) are equivalent is essentially the same as the preceding, but without
having to compensate for short computation sequences for the reverse direction.
Corollary 4 (Normal Form Theorem) Every pmf '(x) 2 C can be written in the form (z <
As an application of this equivalence, consider the following \intersection" and \union" operations
on pmf's:
We see that NPMV is closed under both operations as follows. If ' and are computed by the
RM's M ' and M , respectively, then ('  )(x) is computed by nondeterministically choosing to
run one of M ' or M on x, and
)(x) is computed by running both M ' and M and accepting
exactly when both accept with the same output. By the Theorem, C and D must also be closed
under these operations. Note that this latter fact is not so obvious, because composition is not
such a simple operation when applied to partial functions. In particular, consider the composition
To evaluate '(x), intuitively we must nd some z 1 and z 2 such that
This involves evaluating both  i . But if, for example,  1 (x) is undened, then the
entire composition is undened. On the other hand, these intersection and union operators are
well-dened even when '(x) or (x) is not dened.
4. Resource-free Characterization
We now recall Bellantoni and Cook's denition of safe recursion [2] in the context of pmf's.
Arguments are separated into two types: normal (for which we use x, y, z) and safe (a, b, and c).
One view of this distinction is that the normal arguments can be used to clock iterations, whereas
the safe arguments can be used simply as bit stores, for which a polynomial number of the bits
can be examined in a computation [2]. Another view is that the safe positions are safe for \large"
input values; i.e., one can increase the size of these arguments without a signicant increase in the
computation time [3]. Yet another, more philosophically justied, view is given by Leivant [6]. He
views the safe arguments (in his terminology, tier 0 arguments) as being able to take data that
has been somehow \impredicatively" dened. That is to say, if the denition of the data somehow
assumes the totality of the domain on which the function is being dened, it is impredicative, and
can only be used in a tier 0 position. In particular, when a function is dened by recurrence as
the denition only makes sense when g is dened no matter what its
third argument is|in other words, the denition assumes the totality of f , and hence the domain
of denition, and so this argument must be of tier 0. We use a semicolon to delimit normal from
safe arguments: '(x; a) takes a single normal argument x and a single safe argument a.
Now consider the following operations on pmf's, where x mod 2 is the value of the low-order bit
of x:
Safe Composition: ' is dened by safe composition from ,
, and
when
z) 7! y:
Safe Recursion on Notation: ' is dened by safe recursion on notation (srn) from and  i
when
a) 7! y , 9u:'(x; z;
a) 7!
Safe Weak Minimization: ' is dened by safe weak minimization (swm) from , written
d) mod 2 7! 1
(we write (x;  a; c) mod 2 7! 0 if there is z such that (x;  a; c) 7! z and z mod this is
just the usual notion of pmf composition of ' and z:z mod 2).
It would be natural to say that ' is dened by safe witnessing from when
'(x;  a) 7! c , (x;  a; c) mod 2 7! 0:
But with no minimization or bounding requirements, this would lead to pmf's with an innite
number of outputs for a xed input (e.g., if is constantly 0), so we do not consider such a scheme.
As we mentioned in the introduction, Bellantoni [2] denes the minimization scheme  t b:f(x;
to be the least b such that f(x;  a; b) mod if such a b exists and 0 otherwise 1 . Note that
if f is total, then so is  t b:f(x;  a; b) mod so Bellantoni can add this scheme to his characterization
of FP (base functions plus safe composition and safe recursion on notation) to dene a
new class of total functions. He then proves that under the natural denition of \i applications of
Actually, if there is such a b, Bellantoni's minimization outputs s1b.
minimization," the functions denable with i+1 applications of minimization are exactly those that
are computable in polynomial time from a  p
oracle. He also shows that the same characterization
holds for a bounded version of this total minimization scheme (no notion of safety). Furthermore,
we note that if we add an unbounded, total minimization operator to primitive recursion, then it
is easy to show that the functions denable with applications are exactly those recursive in a
(for a proof, one can simply remove the bounds from Bellantoni's proof of the bounded
version). Thus this total minimization operator (bounded or safe) behaves in a manner exactly
analogous to the corresponding operator for recursive functions. However, for exactly this reason,
it does not capture the appropriate minimization that is analogous to generating the partial recursive
functions, which is our aim in this paper. We now show that safe weak minimization is the
appropriate operator for this goal.
is the following set of functions:
1. The constant 0 (nullary) function.
2. Projections:  n;m
3. Binary successors: s 0
4. Predecessor: pred(;
5. Conditional: cond(; a; b; c) = if a mod
Definition The class C safe is the smallest class of pmf's containing B 0 that is closed under safe
composition, srn, and swm. The class C nml
safe consists of those functions of C safe with only normal
arguments.
The following denition, lemma, and proposition are taken essentially from [2] and the proofs
can be taken almost verbatim from there. Taken together, they formalize the intuition that for any
pmf ' there is a polynomial q such that the jwj bits of the output of '(x;  a) depend only on the
bits of the safe arguments  a. First dene a the jxj rightmost bits of a;
Bellantoni gives a denition of a mod x with x safe and a normal in [2].
Definition Let '(x;
a) be a pmf (note that we do not separate the arguments into normal and
safe here) and let q be a polynomial.
1. ' is poly-checking on  x with threshold q if for all w and all v satisfying jvj  q(x) + jwj we
have '(x;
a mod v) 7! y mod w , '(x;  a) 7! y mod w.
2. A pmf '(x;  a) is polymax bounded on  x by q if for all  x and  a, if '(x;  a) is dened, then
maxfjajg.
Lemma 5 Let '(x;  a; b) be a pmf that is poly-checking on
x with threshold q. Then for any
x and  a,
if '(x;  a; b) mod 2 7! 0, then there is jb
Proposition 6 If '(x;  a) 2 C safe , then ' is poly-checking and polymax bounded on
x.
Proof. By induction on the denition of C safe .
Theorem 7 Let ' be a pmf. Then '
safe .
Proof. The proof that ' 2 NPMV implies ' 2 C nml
safe follows the same lines as the proof of Thm. 3
that if ' 2 NPMV then ' 2 C. What we must do is dene a version of the Kleene T -predicate
using safe recursion on notation that allows us to extract accepting computation sequences of a
nondeterministic RM. The main idea is that we use srn to dene functions f(x; a) which \examine"
bits of a and return some value. In other words, normal arguments are used as clocks to
examine safe values, which are used as \bit stores." With this in mind, dene (characteristic
functions of) the following predicates:
mach(m; e) , the jmj low-order bits of e code a description of a nondeterministic RM (given
the coding, mach(m; e) actually examines p(jmj) bits of e for some xed polynomial p, a detail
which we do not specify from this point onward).
cfg(n; e; c) , mach(jej; e)^ the jnj low-order bits of c code a conguration of the RM described
by e.
there is a transition from c 1 to c 2
according to the description e.
cs(n; t; e; z) , mach(jej; e)^ the jtj low-order bits of z code a sequence of congurations c
of a RM such that for all i we have trans(n;
rst conguration of z is the initial conguration of the
RM described by e on input
x and the last conguration is an accepting state.
Now suppose that 2 C. By Thm. 3, is computed by a nondeterministic RM with code e with
time bounded by some polynomial p(n). Since no more than p(n) tape cells are accessed during
a computation on input of length n, every conguration can be coded by a string whose length is
also polynomial in n, say q(n). Furthermore we have that the code of any computation sequence
of length  n is itself  seqbnd e
(n; ), where we take seqbnd e
arguing as in
Thm. 3, if we dene
safe and
For the reverse direction, one proves by induction that if '(x;  a) 2 C safe , then ' 2 C using the
polymax bound on ' given by Prop. 6. The only cases of real interest are when ' is dened by safe
recursion on notation or safe weak minimization. If ' is dened by srn from and  i , then the same
recursion on notation denes ' in C. Furthermore, if ' is polymax bounded by q on  x, then for all
x
and  a for which '(x;  a) is dened we have '(x;  a)  2 q(jxj)+
. Since the bound is polynomial-time
computable, the recursion on notation is bounded by a function denable in C. Suppose
that '(x;  a) = b: (x;
that ' is polymax bounded by q on  x. Then under the
induction hypothesis that is denable in C, we have '(x;
a)
0. For this denition to be valid, it suces to note that the function z:z mod 2 is polynomial-time,
and therefore denable in C.
5. Nondeterministic Recursion
In [6, x5], Leivant discusses a notion of nondeterministic recursion and its safe (ramied) variant.
We say that f(x; z;  a) is dened from the nite set  of multifunctions by nondeterministic safe
recursion if
a) 7! y , 9g 2 :g(x;  a) 7! y
a) 7! y , 9g 2 9u:f(x; z;  a) 7!
In other words, at each step of the computation of f(x; z;  a) we are allowed to \choose" a dierent
recursion function from . Note that if  consists of total multifunctions, then f is also a total
multifunction. Let E be the smallest class of (total) multifunctions containing B 0 that is closed
under safe composition and nondeterministic safe recursion; E nml consists of those functions of E
that have only normal arguments. In this section we prove that E nml consists of exactly the total
multifunctions of NPMV 2 .
Lemma 8 If f(x;  a) 2 E, then f is polymax bounded on
x.
2 Because of a technical subtlety, Leivant's proof sketch of this result does not carry through.
Proof. This is proved by induction on the denition of f and is essentially the same as the proof
that the functions dened by safe recursion (no minimization) are all polymax bounded.
Theorem 9 Let f be a total multifunction. Then f
Proof. For the forward direction, prove by induction that if f(x;  a) 2 E, then f(x;  a) 2 C, and
therefore f 2 NPMV by Thm. 3. This is essentially the same as the proof of the forward direction
of Thm. 7. Of course, the only case that needs consideration is when f is dened by nondeterministic
safe recursion from . Say that the multifunctions of  0 are used to
compute f(x; 0;
a) and the multifunctions of  1 are used to compute f(x; s i z;  a). Then we dene f
in C by
where  is the \union" operator dened after Cor. 4 (recall that we have only dened nondeterministic
safe recursion from nite sets , so  0 and  1 are nite). The polymax bound on f given
by Lemma 8 gives a p-time computable bound on the recursion, and so the recursion can be dened
in C.
For the reverse direction, suppose that f is computed by a nondeterministic RM M that runs
in time q(n), uses states d registers  . For simplicity, assume that f is
unary. We can assume that for any nondeterministic state of M has exactly two corresponding
instructions. We dene a new register machine N that will behave similarly to M ; the dierence is
that N will rst guess its nondeterministic choices, then behave deterministically, referring to its
original guesses whenever it encounters a nondeterministic state. Formally, we dene N as follows:
1. N uses registers  new states
t and d a0 , d 0
for every nondeterministic state d a of M .
2. From the initial state, N nondeterministically constructs y in m+1 with length  q(j
using the states  t.
3. Otherwise, N is exactly the same as M , except that for every nondeterministic state with
instructions d a
D 0 and d a
D 1 we replace these instructions with the following:
d a Tm+1 d a0 d
d a0 Pm+1m+1 d 0
d
Thus, when N enters state d a , it transitions to state d ai , where i corresponds to the low-order
bit of the contents of m+1 , deletes that bit, and then executes either the rst or second
instruction that M would execute from state d a .
Note that the only nondeterministic instructions are now those that start with one of the states
from  t. Then N also computes f(x) by executing exactly q(jx
steps that change the contents of only m+1 , then acting deterministically. To simulate N using
nondeterministic safe recursion:
1. Dene transition functions  j (; s; a in [6], but do not
dene them for the states  t (more accurately, the denition for the states
t is irrelevant). For
gives the contents of the j th register after the transition from state (with code) s (for
which there is only one possibility);  1 gives the next state. The  j can be dened with just
the use of conditionals, successors, and predecessors, and hence can take all safe arguments.
2. Dene the functions  j by simultaneous safe recursion so that  j (y
is the contents of  0 after executing jy 1 j      jy steps starting at state d and with a i
in register  i ; see [6] for details. Leivant also shows there that simultaneous safe recursion is
reducible to safe recursion, so we can without loss of generality assume we use the latter.
3. Dene the function guess(z; ) using nondeterministic safe recursion by
In other words, guess is dened from the set of functions containing the constant 0 and 1
functions and s 0 and s 1 .
Just as in [6], if q(n)  n k (where q(n) is the running time of M ), then f is represented in E nml as
Examining the proof of Thm. 9, we actually proved that if f 2 E nml , then f can be dened
in C using only the schemes of composition and bounded recursion on notation, along with the
operator. So if we let C 0 be the smallest class of (total) multifunctions containing the same base
functions as C that is closed under composition, brn, and , then we have proved:
Theorem f be a total multifunction. Then f 2 C
6. The Analogy of NPMV and the Partial Recursive Functions
We close by returning to the theme of the introduction: the proper analog of the partial recursive
functions is the class NPMV. Recall that PR and REC are the primitive recursive and partial
recursive functions, respectively. We have made the argument that FP is the proper analog of PR,
given that the two are dened in terms of essentially the same function schemes (one bounded or
safe, the other not). In previous sections we have seen that NPMV arises when a straightforward
bounded or safe minimization operator is added to these schemes, just as the partial recursive
functions arise when an unbounded minimization operator is added to PR. In this section, we
consider some other properties of REC and their analogs in NPMV. Specically, we consider
the relationship between REC and the recursively enumerable sets, and show that (mostly) the
same relationships hold between NPMV and the NP sets. We conclude by introducing a new
hierarchy that we obtain by applying our analogy to the view that the  levels of the arithmetic
hierarchy are ranges of partial functions and also discuss the generalization of NPMV to higher-
type computability.
For a pmf ', we dene yg to be the graph of '. We say that ' is
poly-bounded by the polynomial q if hx; yi
Lemma 11 Let ' be a partial function. Then ' 2 NPMV i ' 2 NP and ' is poly-bounded.
In particular, if  is a characteristic function for some set, then  2 NPMV i  2 NP.
Proof. If ' 2 NPMV and is computed by the register machine M , then to verify that y,
run M on
x and accept i M accepts and outputs y. Since M runs in polynomial time, ' must
be poly-bounded. For the reverse direction, suppose that '(x) 7! y
and that ' is poly-bounded by q. Compute '(x) as follows. First guess y  2 q(jxj) , then guess
then accept and output y, otherwise reject.
Lemma 12 If A is a set with characteristic function , then  2 NP i A 2 NP \ coNP.
Proof. Suppose that  2 NP; say that
Now suppose that A 2 NP \ coNP:
where R and S are p-time predicates. Then
Proposition 13 If A is a set, then A 2 NPMV i A 2 NP \ coNP (compare: A 2 REC i
Proof. The rst equivalence follows from Thm. 3. The second follows from Lemmas 11 and 12.
Proposition 14 If A is a set, then A 2 NP i there is ' 2 NPMV such that
(compare: A is r.e. i there is ' 2 REC such that A = Dom ').
Proof. Suppose that x 2 A , 9y < 2 p(jxj) :R(x; y). Dene ' 2 NPMV as follows: on input x,
guess y < 2 p(jxj) . If R(x; y) holds, then accept and output reject. Clearly Dom A.
Now suppose that ' 2 NPMV. Since ' is poly-bounded, we have that x 2 Dom ' i 9y <
y. But '(x) 7! y is an NP predicate by Lemma 11.
Interestingly, we only seem to be able to identify NP with the ranges of honest pmf's in NPMV.
Following Balcazar, D  iaz, and Gabarro [1, Def. 3.10], a pmf ' is honest if there is a polynomial q
such that whenever '(x) 7! y, then there is some
z with all jz i j < q(jyj) such that '(z) 7! y.
Proposition 15 If A is a set, then A 2 NP i there is an honest ' 2 NPMV such that
Ran '.
Proof. For the forward direction, use the same pmf as in Prop. 14. For the reverse direction,
suppose that ' 2 NPMV is honest. Then y y, and the matrix of
this predicate is NP by Lemma 11.
However, the same honesty condition applies for expressing NP as the ranges of FP functions,
and Rosser showed that an analogous result holds for primitive recursive functions, albeit without
the honesty condition:
Proposition A be a set.
1. [1, Exercise 3.9.2] A 2 NP i there is an honest f 2 FP such that A = Ran f .
2. [7] A is r.e. i there is a primitive recursive f such that A = Ran f .
Finally, we close with two suggestions for further study. First, one can view the arithmetic
hierarchy in the following way, which does not refer to the syntax of a formal language:
recursive in A , A 2  i g
If NPMV is the right analogy for partial recursive, then the following ought to be an interesting
hierarchy to study:
Second, the notion of oracle computation for a total single-valued oracle g is the straightforward
one, and corresponds to adding g as a base function to the class C. Once one considers oracle
computation and focuses on functions, it is natural to about oracles that are themselves pmf's,
leading to notions of higher-type computability. There are two dierent denitions of computing
relative to a pmf oracle [5, 8], but neither is obviously comparable to adding the oracles as base
pmf's to C. This is because both denitions \totalize" the oracle in order that it always return
a value (obviously, this makes no dierence when the oracle is a characteristic function), whereas
this would be an unnatural approach to adding base pmf's to C. Properly developing a notion
of higher-type computability along these lines may help to clarify some of the dicult issues of
higher-type feasibility by providing an appropriate \universe" in which to consider higher-type
complexity.



--R


Predicative recursion and the polytime hierarchy.
A new recursion-theoretic characterization of the polytime functions
The intrinsic computational di
Oracles that compute values.

Extensions of some theorems of G
A taxonomy of complexity classes of functions.
Much ado about functions.
--TR
On the power of single-valued nondeterministic polynomial time computations
A new recursion-theoretic characterization of the polytime functions
On Functions Computable in Nondeterministic Polynomial Time
Much Ado about Functions
implicit computational complexity;safe recursion;minimization;non-deterministic partial multifunctions