A First-Order Isomorphism Theorem.
We show that for most complexity classes of interest, all sets complete under first-order projections (fops) are isomorphic under first-order isomorphisms.  That is, a very restricted version of the Berman--Hartmanis conjecture holds.  Since "natural" complete problems seem to stay complete via fops, this indicates that up to first-order isomorphism there is only one "natural" complete problem for each "nice" complexity class.
Introduction
In 1977 Berman and Hartmanis noticed that all NP complete sets that they knew of were
polynomial-time isomorphic, [BH77]. They made their now-famous isomorphism conjecture:
namely that all NP complete sets are polynomial-time isomorphic. This conjecture has
engendered a large amount of work (cf. [KMR90, You] for surveys).
The isomorphism conjecture was made using the notion of NP completeness via polynomial-
time, many-one reductions because that was the standard definition at the time. In [Coo],
A preliminary version of this work appeared in Proc. 10th Symposium on Theoretical Aspects of
Computer Science, 1993, Lecture Notes in Computer Science 665, pp. 163-174.
y Some of this work was done while on leave at Princeton University; supported in part by National
Science Foundation grant CCR-9204874.
z Supported in part by ESPRIT-II BRA EC project 3075 (ALCOM) and by Acci'on Integrada Hispano-
Alemana 131 B
x Supported by NSF grant CCR-9207797.
Cook proved that the Boolean satisfiability problem (SAT) is NP complete via polynomial-time
Turing reductions. Over the years SAT has been shown complete via weaker and
weaker reductions, e.g. polynomial-time many-one [Kar], logspace many-one [Jon], one-way
logspace many-one [HIM], and first-order projections (fops) [Dah]. These last reductions,
defined in Section 3, are provably weaker than logspace reductions. It has been observed
that natural complete problems for various complexity classes including NC 1 , L, NL, P, NP,
and PSPACE remain complete via fops, cf. [I87, IL, SV, Ste, MI].
On the other hand, Joseph and Young, [JY] have pointed out that polynomial-time, many-one
reductions may be so powerful as to allow unnatural NP-complete sets. Most researchers
now believe that the isomorphism conjecture as originally stated by Berman and Hartmanis
is false. 1
We feel that the choice of polynomial-time, many-one reductions in the statement of the
Isomorphism Conjecture was made in part for historical rather than purely scientific reasons.
To elaborate on this claim, note that the class NP arises naturally in the study of logic and
can be defined entirely in terms of logic, without any mention of computation [Fa]. Thus
it is natural to have a notion of NP-completeness that is formulated entirely in terms of
logic. On another front, Valiant [Val] noticed that reducibility can be formulated in algebra
using the natural notion of a projection, again with no mention of computation. The sets
that are complete under fops are complete in all of these different ways of formulating the
notion of NP-completeness.
Since natural complete problems turn out to be complete via very low-level reductions such
as fops, it is natural to modify the isomorphism conjecture to consider NP-complete reductions
via fops. Motivating this in another way, one could propose as a slightly more
general form of the isomorphism conjecture the question: is completeness a sufficient structural
condition for isomorphism? Our work answers this question by presenting a notion of
completeness for which the answer is yes. Namely for every nice complexity class including
any two sets complete via fops are not only polynomial-time isomorphic, they
are first-order isomorphic.
There are additional reasons to be interested in first-order computation. It was shown
in [BIS] that first-order computation corresponds exactly to computation by uniform AC 0
circuits under a natural notion of uniformity. Although it is known that AC 0 is properly
contained in NP, knowing that a set A is complete for NP under polynomial-time (or
logspace) reductions does not currently allow us to conclude that A is not in AC 0 ; however,
knowing that A is complete for NP under first-order reductions does allow us to make that
conclusion.
First-order reducibility is a uniform version of the constant-depth reducibility studied in
[FSS, CSV]; sometimes this uniformity is important. For a concrete example where first-order
reducibility is used to provide a circuit lower bound, see [AG92].
Preliminary results and background on isomorphisms follow in Section 2. Definitions and
background on descriptive complexity are found in Section 3. The main result is stated and
proved in Section 4, and then we conclude with some related results and remarks about the
structure of NP under first-order reducibilities.
One way of quantifying this observation is that since Joseph and Young produced their unnatural NP-complete
sets, Hartmanis has been referring to the isomorphism conjecture as the "Berman" conjecture.
Short History of the Isomorphism Conjecture
The Isomorphism Conjecture is analogous to Myhill's Theorem that all r.e. complete sets are
recursively isomorphic, [Myh]. In this section we summarize some of the relevant background
material. In the following FP is the set of functions computable in polynomial time.
Definition 2.1 For we say that A and B are p-isomorphic
exists a bijection f 2 FP with inverse f \Gamma1 2 FP such that A is many-one reducible to B
Observation 2.2 ([BH77]) All the NP complete sets in [GJ] are p-isomorphic.
How did Berman and Hartmanis make their observation? They did it by proving a polynomial-time
version of the Schr-oder-Bernstein Theorem. Recall:
Theorem 2.3 ([Kel, Th. 20]) Let A and B be any two sets. Suppose that there are 1:1
maps from A to B and from B to A. Then there is a 1:1 and onto map from A to B.
Proof A be the given 1:1 maps. For simplicity assume that
A and B are disjoint. For a; c 2 A [ B, we say that c is an ancestor of a iff we can reach
a from c by a finite (non-zero) number of applications of the functions f and/or g. Now
we can define a bijection h : A ! B which applies either f or g \Gamma1 according as whether a
point has an odd number of ancestors or not:
if a has an odd number of ancestors
f(a) if a has an even or infinite number of ancestorsThe feasible version of the Schr-oder-Bernstein theorem is as follows:
Theorem 2.4 ([BH77]) Let f : A -m B and are 1:1, length-
increasing functions. Assume that f; f are inverses of f; g.
Then A
Proof Let the ancestor chain of a string w be the path from w to w's parent, to w's
grandparent, and so on. Ancestor chains are at most linear in length because f and g
are length-increasing. Thus they can be computed in polynomial time. The theorem now
follows as in the proof of Theorem 2.3. 2
Consider the following definition:
Definition 2.5 ([BH77]) We say that the language A ' \Sigma   has p-time padding functions
iff there exist e; d 2 FP such that
1. For all w; x 2 \Sigma   , w 2 A , e(w;
2. For all w; x 2 \Sigma   , d(e(w;
3. For all w; x 2 \Sigma   , je(w; x)j - jwj simple example, the following is a padding function for SAT,
where c i is (y -
y) if the i th bit of x is 1 and (-y - y) otherwise, where y is a Boolean variable
numbered higher than all the Boolean variables occurring in w.
Then the following theorem follows from Theorem 2.4:
Theorem 2.6 ([BH77]) If A and B are NP complete and have p-time padding functions,
then A
Finally, Observation 2.2 now follows from the following:
Observation 2.7 ([BH77]) All the NP complete problems in [GJ] have p-time padding
functions.
Hartmanis also extended the above work as follows: Say that A has logspace-padding functions
if there are logspace computable functions as in Definition 2.5.
Theorem 2.8 ([Har]) If A and B are NP complete via logspace reductions and have
logspace padding functions, then A and B are logspace isomorphic.
Proof Since A and B have logspace padding functions, we can create functions f and g
as in Theorem 2.4 that are length squaring and computable in logspace. Then, the whole
ancestor chain can be computed in logspace because each successive iteration requires half
of the previous space. 2
Here, we show that sets complete under a very restrictive notion of reducibility are isomorphic
under a very restricted class of isomorphisms. This result is incomparable to a recent
result of [AB], showing that all sets complete under one-way logspace reductions (1-L re-
ductions) are isomorphic under polynomial-time computable isomorphisms. (This work of
[AB] improves an earlier result of [A88].) Note that it is easy to prove that the class of
1-L reductions is incomparable with the class of first-order projections. Other interesting
results concerning 1-L reductions may be found in [BH90, HH].
3 Descriptive Complexity
In this section we recall the notation of Descriptive Complexity which we will need to state
and prove our main results. See [I89] for a survey and [IL] for an extensive discussion of
the reductions we use here including first-order projections.
We will code all inputs as finite logical structures. The most basic example is a binary
string w of length logical structure:
where the unary relation R(x) holds in A(w) (in symbols, A(w) just if bit x of w
is a 1. As is customary, the notation jAj will be used to denote the universe f0;
of the structure A. We will write jjAjj to denote n, the cardinality of jAj.
A vocabulary
r
a tuple of input relation and constant symbols.
We call the R i 's ``input relations'' because they correspond to the input bits to a boolean
circuit. In the case of binary strings, the input relation tells us which bits are 0 and which
are 1. In the case of graphs, the input relation E tells us which edges are present.
denote the set of all finite structures of vocabulary - . We define a complexity
theoretic problem to be any subset of STRUC[- ] for some - .
For any vocabulary - there is a corresponding first-order language L(-) built up from the
symbols of - and the numeric relation symbols and constant
using logical connectives: -; :, variables: x; quantifiers: 8; 9.
First-Order Interpretations and Projections
In [Val], Valiant defined the projection, an extremely low-level many-one reduction.
Definition 3.1 Let k-ary projection from S to T is a sequence of maps
that satisfy the following properties. First, for all n and for all binary
strings s of length n, is a binary string of length n k and,
Then each map p n is defined by a sequence of n k literals:
Thus as s ranges over strings of length n, each bit of p n (s) depends on at most one bit of s,
refers to the usual ordering on means that the i th bit of the binary
representation of j is 1, and 0 and m refer to 0 and respectively. For simplicity we will assume
throughout that n ? 1 and thus 0 6= m. These relations are called "numeric" as opposed to the input
relations because, for example, "BIT(i; j)" and "i - j" depend only on the numeric values of i and j and
do not refer to the input.
Projections were originally defined as a non-uniform sequence of reductions - one for each
value of n. That is, a projection can be viewed as a many-one reduction produced by a
family fC n g of circuits of depth one. The circuits consist entirely of wires connecting input
bits or negated input bits to outputs. If the circuit family fC n g is sufficiently uniform, we
arrive at the class of first-order projections. (Recall that first-order corresponds to uniform
AC 0 [BIS].) We find it useful to work in the framework of first-order logic rather than in
the circuit model. The rest of this section presents the necessary definitions of first-order
reductions.
The idea of the definition is that the choice of the literals hl 3.1
is given by a first-order formula in which no input relation occurs. Thus the formula can
only talk about bit positions, and not bit values. The choice of literals depends only on n.
In order to make this definition, we must first define first-order interpretations. These are
a standard notion from logic for translating one theory into another, cf. [End], modified
so that the transformation is also a many-one reduction, [I87]. (For readers familiar with
databases, a first-order interpretation is exactly a many-one reduction that is definable as
a first-order query.)
Definition 3.2 (First-Order Interpretations) Let oe and - be two vocabularies, with
r
be two problems. Let k be
a positive integer. Suppose we are given an r-tuple of formulas '
where the free variables of ' i are a subset of fx
g. Finally, suppose we are given
an s-tuple of constant symbols 3
be a tuple of these formulas and constants. (Here
Then I induces a mapping also called I from STRUC[oe] to STRUC[- ] as follows. Let
A 2 STRUC[oe] be any structure of vocabulary oe, and let jjAjj. Then the structure
is defined to be:
where the relation R i is determined by the formula ' i , for as follows. Let the
function jI(A)j be given by
Then,
If the structure A interprets some variables - u then these may appear freely in the the ' i 's
and t j 's of I, and the definition of I(A) still makes sense.
Suppose that I is a many-one reduction from S to T , i.e. for all A in STRUC[oe],
Then we say that I is a k-ary first-order interpretation of S to T . 2
3 More generally, we could use closed terms which are expressions involving constants and function
symbols. An even more general way to interpret constants and functions is via a formula ' such that
However, in this paper the simpler definition involving constant symbols suffices.
We are now ready to define first-order projections, a syntactic restriction of first-order
interpretations. If each formula in the first-order interpretation I satisfies this syntactic
condition then it follows that I is also a projection in the sense of Valiant. In this case we
call I a first-order projection.
Definition 3.3 [First-Order Projections] Let I be a k-ary first-order
interpretation from S to T as in Definition 3.2. Suppose further that the ' i 's all
satisfy the following projection condition:
where the ff j 's are mutually exclusive formulas in which no input relations occur, and each
- j is a literal, i.e. an atomic formula P
or its negation.
In this case the predicate R i
i) holds in I(A) if ff 1 (-u) is true, or
if ff j (-u) is true for some and the corresponding literal - j (-u) holds in A. Thus
each bit in the binary representation of I(A) is determined by at most one bit in the binary
representation of A. We say that I is a first-order projection (fop). Write S - fop
T to mean
that S is reducible to T via a first-order projection. 2
Example 3.5 To help the reader grasp an intuition of the way an fop reduction behaves,
let us describe an example. We present here the reduction from 3-SAT, satisfiability of
CNF Boolean expressions with exactly three literals per clause, to 3-COL, the problem of
coloring the vertices of a graph with 3 colors under the constraint that the endpoints of
all edges get different colors. We use the same reduction as described in section 11.4.5 of
[Man], so that the reader in need of additional help can consult it there.
The respective vocabularies for the input and output structures are as follows. To describe
instances of 3-SAT, clauses and Boolean variables are each numbered from 0 through
1. There are six predicates: P i (x; c); N i (x; c), i=1,2,3, indicating that variable x occurs
positively or negatively in the i th position of the clause c. The vocabulary for the output
structures is simply a binary predicate E standing for the Boolean adjacency matrix of the
output graph. Thus E(u; v) is true exactly when the edge (u; v) is present in the output
graph.
The output graph consists of 6 vertices per clause and two vertices per Boolean variable,
plus three additional vertices usually named T , F , and R (standing for true, false, and red).
Let an arbitrary 3CNF formula be coded by an input structure,
The output structure will be a graph with 8n vertices. The easiest way for
us to code this is to use an fop of arity 2. We will assume for simplicity that n is always
greater than or equal to 9.
It remains to write down the first-order projection, '. To do this, we need some nitty gritty
coding. We will let the vertices T; F , and R be the elements h0; 0i; h1; 0i, and h2; 0i of I(A)
respectively. The formula ' will have three pieces:
Where ff says that there are edges between T; F , and R; fi says that vertices hx; 1i and hx; 2i
representing variable x and its negation are connected to each other and to R; and; fl says
that for clause are connected to each other, and
the following edges exist: (hC; 3i; hC; 6i), (hC; 4i; hC; 7i), (hC; 5i; hC; 8i), as well as the edges
(a; hC; 3i); (T; hC; 3i),
(b; hC; 4i), (T; hC; 4i), and (d; hC; 5i); (T; hC; 5i).
In case anyone really wants to see them, here are the formulas written out:
Theorem and Proof
Theorem 4.1 Let C be a nice complexity class, e.g., L, NL, P, NP, etc. Let S and T be
complete for C via first-order projections. Then S and T are isomorphic via a first-order
isomorphism.
To prove Theorem 4.1 we begin with the following lemma. Note the similarity between
Lemma 4.2 and the proofs of Theorems 2.4 and 2.8. For simplicity in this lemma we are
assuming that I is a single fop that maps STRUC[oe] to itself. The proof for the case with
two fops and two vocabularies as in Lemma 4.5 is similar.
Lemma 4.2 Let I be an fop that is 1:1 and of arity greater than or equal to two (i.e.
it at least squares the size). Then the following two predicates are first-order expressible
concerning a structure A:
a. IE(A), meaning that I exists.
b. #Ancestors(A; r), meaning that the length of A's maximal ancestor chain is r.
Proof Let I
is in the form of Equation
3.4. To prove (a) just observe that each bit of the relation R i of A either (1) depends on
exactly one bit of some pre-image B (specified by an occurrence of a literal - ij in ' i ), or (2)
it doesn't depend on any bit of a pre-image. In case (2) a given bit of A is either ``right''
or "wrong." Thus, A has an inverse iff no bit of A is wrong, and no pair of bits from A
are determined by the same bit of A's preimage in conflicting ways. We can check this in a
first-order way by checking that for all pairs of bits from A: R i (-a) and R i either they do
not depend on the same bit from B, or the same value of that bit gives the correct answer
Furthermore, the preimage B if it exists can be described uniquely by
a first-order formula that chooses the correct bits determined by entries of A. N.B. Since
we have assumed that I is 1:1 every bit of I \Gamma1 (A) is determined by some bit of A.
(b) To express #Ancestors(A; r), we want to describe the existence of an Ancestor Chain:
A r
I
I
I
We will then assert that this is the maximal length such chain, i.e.,
Equation 4.4 expresses the existence of the ancestor chain 4.3 inductively in the following
sense: Once we know that A k exists, we can ascertain the value A k [[p k of the bit at position
k of A k , by exhibiting a certificate:
We can say in a first-order sentence that C(k; p k ) is internally consistent. That is, for all
determined correctly via I by bit p i of A i . 4 Note
that because each structure A i+1 is of size at most the square root of the size of A i , the
certificate requires only O(log n) bits, i.e., a constant number of variables, to express.
Thus, in Equation 4.4, we refer to bit p k of the structure A k by existentially quantifying
an internally consistent certificate C(k; p k
We know inductively, that since IE(A
), the
bit value determined by C(k; p k ) is unique and correct. 2
Lemma 4.5 If S and T are interreducible via 1:1 fops I and J each of arity at least two,
then S and T are isomorphic via first-order isomorphisms.
Proof Let A be a structure in the vocabulary of S, and, as in the proof of Theorem 2.3
define the length of the ancestor chain of A to be the length of the longest sequence of
the The argument given in Lemma 4.2
shows that there is a formula #Ancestors(A; r) that evaluates to true iff A's ancestor chain
has length r. Lemma 4.2 also shows that there is a formula computing J \Gamma1 . The desired
isomorphism is now the function b such that the i-th bit of b(A) is one iff the following
first-order formula is true:
4 The reader who is more familiar with bit hacking on Turing machines than with first-order formulas,
could instead convince herself that this can be done by an alternating Turing machine running in logarithmic
time and making O(1) alternations; first-order expressibility follows by [BIS].
(Note that this first-order isomorphism b is not, strictly speaking, a first-order interpre-
tation, since it maps some inputs to strictly shorter outputs, which is impossible for an
It now remains to show,
Lemma 4.6 Suppose that a problem S is complete via fops for a nice complexity class, C.
Then S is complete for C via fops that are 1:1 and of arity at least two.
Proof Of course it remains to define "nice", but here is the proof. Every nice complexity
class has a universal complete problem:
using resources f C (r)g (4.7)
Here f C (r) defines the appropriate complexity measure, e.g. r nondeterministic steps for
NP, deterministic space log r, for L, space 2 r for EXPSPACE, etc.
We claim that U C is complete for C via fops that are 1:1 and of arity at least two . In
order to make this claim, we need to agree on an encoding of inputs to U C that allows us to
interpret them as structures over some vocabulary. Since all of our structures are encoded
in binary, we will encode $ and # by 10 and 11 respectively, and the binary bits 0 and 1
constituting M and w will be encoded by 00 and 01 respectively. Now, as in, for example,
[I87], we consider a binary string of length n to be a structure with a single unary predicate
over a universe of size n. Now for any given problem T 2 C accepted by machine M , we
show that T is reducible to U C via a fop that is 1:1 and of arity at least two. The fop simply
maps input w to the string M$w# r , for an appropriate r which we can always take to be at
least jwj 2 . The fop checks that if i - 2jM j then the odd-numbered bits are 0 and if i is even,
then the i th bit is 1 iff the i=2-th bit of M is 1. Similarly, if
then the odd-numbered bits are 0 and the even numbered bits are the corresponding bit of
etc.
To complete the proof of the lemma, let T be any problem in C and let S be as above. Then
we reduce T to S via a 1:1, length squaring fop as follows. First reduce T to U C as above.
Next reduce U C to S via the fop promised in the statement of the lemma.
It is easy to verify that, using the encoding we have chosen for U C , it holds that for every
length n, for all i - n, there are two strings x and y of length n, differing only in position
i, such that x 2 U C and y 62 U C .
Thus the fop from U C cannot possibly ignore any of the bits in its input. But an fop cannot
process several bits into one, it can only either ignore a bit or copy it, or negate it; and this
choice is made independently of the values of any of the bits.
It follows that the composition of these two fops is the 1:1 length squaring fop that we
desire. (Note that an fop by definition must have arity at least one and thus cannot be
length decreasing on Boolean strings.) 2
From the above three lemmas we have a first-order version of Theorem 2.3 and thus Theorem
4.1 follows.
We can inspect the proof of Lemma 4.6 to get a definition of "nice". A complexity class
is "nice" if it has a universal complete problem via fops as in Equation 4.7. It is easy to
check that the following complexity classes, among many others, are nice and thus meet the
conditions of Theorem 4.1.
Proposition 4.8 The following complexity classes are nice: NC 1 , L, NL, LOG(CFL),
Proof This is immediate for the Turing machine based classes: L, NL, P, NP, PSPACE,
EXPTIME, EXPSPACE. It similarly follows for the other three classes using the definitions:
More on the Relationship between Isomorphisms and
Projections
There are several questions about isomorphisms among complete sets that can be answered
in the setting of first-order computation but are open for general polynomial-time compu-
tation. It is not known whether one-way functions exist since their existence would imply
that P 6= NP. However, if one-way functions exist (i.e., if P 6= UP) then there exists a
one-way function f such that f(SAT) is polynomial-time isomorphic to SAT [Ga].
Here we can be more definitive: the bijection shown in [BL] to
be one-way for first-order computation, in the sense that f is first-order expressible, but
f \Gamma1 is not. (See also [H-as] for other examples.) However, it is not too hard to show that
for this choice of f , f(SAT ) is complete for NP under first-order projections, and thus it is
first-order isomorphic to SAT.
The next result shows that the class of sets complete under first-order projections is not
closed under first-order isomorphisms. (This also seems to be the first construction of a set
that is complete for NP under first-order (or even poly-time) many-one reductions, that is
not complete under first-order projections.)
Theorem 5.1 There is a set first-order isomorphic to SAT that is not complete for NP
under first-order projections.
Proof Let g(x) be a string of jxj 2 bits, with bit x i;j representing the logical AND of bits
and j of x. Let SATg. By an extension of the techniques used in
proving Theorem 4.1, it can be shown that A is first-order isomorphic to SAT. However a
direct argument shows that there cannot be any projection (even a nonuniform projection)
from SAT to A. (Sketch: For all n, one can find bit positions i and j that are independent of
each other and are independent of every other bit position, in the sense that for any setting
b of bit j there are two words that differ only in bit i, having b in position j, such that one
of the words is in SAT and one is not. No projection reducing SAT to another language
can "ignore" either i or j. But since i and j are independent of all other bit positions, no
projection can encode the AND of bits i and j.) 2
A natural question that remains open is the question of whether every set complete for NP
under first-order many-one reductions is first-order isomorphic to SAT. A related question
is whether one can construct a set complete for NP under poly-time many-one reductions
that is not first-order isomorphic to SAT. Since so many tools are available for proving
the limitations of first-order computation, we are optimistic that this and related questions
about sets complete under first-order reductions should be tractable. 5 Furthermore, we hope
that insights gleaned in answering these questions will be useful in guiding investigations
of the polynomial-time degrees.

Acknowledgments

The authors wish to thank the organizers of the 1992 Seminar on
Structure and Complexity Theory at Schlo- Dagstuhl, where this work was initiated. We
also thank Richard Beigel, Jose Antonio Medina, and two anonymous referees for comments
on an earlier draft.



--R

"Polynomial Isomorphism of 1-L- Complete Sets,"
"Isomorphisms and 1-L Reductions,"
"P-Uniform Circuit Complexity,"
"On Strong Separations from AC 0 ,"
"A Uniform Circuit Lower Bound for the Perma- nent,"
"On Uniformity Within NC 1 ,"
"On Isomorphism and Density of NP and Other Complete Sets,"
"One-Way Functions and Circuit Complexity,"
"The degree structure of 1-L reduc- tions,"
"Constant Depth Reducibil- ity,"
"The Complexity of Theorem Proving Procedures,"
"Reduction to NP-Complete Problems by Interpretations,"
A Mathematical Introduction to Logic
"Generalized First-Order Spectra and Polynomial-Time Recognizable Sets,"
"Parity, Circuits, and the Polynomial-Time Hierarchy,"
"One-way Functions and the Isomorphism Conjecture,"
Computers and Intractability
"One-Way Permutations in NC 0 ,"

"One-Way Log Tape Reductions,"
"Collapsing Degrees Via Strong Computa- tion,"
"Languages That Capture Complexity Classes,"
"Descriptive and Computational Complexity,"
"The Complexity of Iterated Multiplication,"
"Space-Bounded Reducibility among Combinatorial Problems,"
"Some Remarks on Witness Functions for Non-polynomial and Non-complete sets in NP,"
"Reducibility Among Combinatorial Problems,"
"The Isomorphism Conjecture Fails Relative to a Random Oracle,"
"The Structure of Complete De- grees,"
Introduction to Algorithms: A Creative Approach
" A Syntactic Characterization of NP- Completeness,"
"Creative Sets,"
"A Complexity Theory Based on Boolean Alge- bra,"
"Using the Hamiltonian Operator to Capture NP,"
"Reducibility By Algebraic Projections,"

--TR

--CTR
Manindra Agrawal , Eric Allender , Russell Impagliazzo , Toniann Pitassi , Steven Rudich, Reducing the complexity of reductions, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.730-738, May 04-06, 1997, El Paso, Texas, United States
complexity classes;reduction;first-order projection;descriptive complexity