Information Technology Reference
In-Depth Information
subsequently elaborated on this intuition, and formulated the
Encrypted Complete Set
Conjecture
, which states that there is a one-one, length-increasing, one-way function
f
such that SAT and
f
(SAT) are not p-isomorphic.
Several papers were then written, all of which tended to buttress support for
the Encrypted Complete Set Conjecture (all of which are discussed in the survey
[
Agr11
]). But then attention shifted to some interesting classes of
restricted
p
m
-
reductions; we will discuss some of these developments in more detail below—but
the general trend of these investigations has been to weaken our confidence in the
Encrypted Complete Set Conjecture. More recently, there has been a productive
series of investigations of
more powerful
classes of reductions, notably including
m-reductions computed in P/poly [
AW09
,
Agr02
] and in NP
ↆ
coNP [
HHP07
] (this
latter class of reductions is known as SNP-reductions). As a consequence, we now
know that some fairly plausible hypotheses imply that all sets complete for NP under
P/poly-reductions and SNP-reductions are P/poly-isomorphic and SNP-isomorphic,
respectively. Combined with the results about restricted
∃
p
m
reductions that will be
discussed below, the picture that emerges is that NP-complete sets are either provably
isomorphic or at least are reasonably likely to be isomorphic, bothwhen one considers
reductions strictly
less
powerful and
more
powerful than
ↆ
p
m
reductions. It remains
to be seen whether any of these lessons ultimately shed much light on the case of
ↆ
ↆ
m
reductions themselves.
2.2.1 Restricted Reductions
p
m
reductions really constitute the most important class
of reductions. There is a rich structure of complexity classes within P, and
It is debatable whether
ↆ
p
m
-
reducibility is essentially useless in elucidating this structure. This was themotivation
for Jones et al. to introduce log-space reductions [
Jon75
]—but even in that pioneering
work, it was realized that a higher precision tool was necessary, in order to investigate
the structure of logspace, which is why Jones introduced what he called
log-bounded
rudimentary reductions
[
Jon75
]. This was several years before the modern study
of circuit complexity got under way, and it took a while before it was noticed that
log-bounded rudimentary reductions actually correspond to many-one reductions
computed by uniform AC
0
circuits (that is, constant-depth polynomial-size families
of circuits of AND and OR gates) [
AG91
]. Ultimately, AC
0
reductions have proved to
be the most useful notion of reducibility for investigating subclasses of P, surpassing
both NC
1
reducibility [
CM87
] and 1-L reducibility (discussed below). However,
AC
0
reducibility posed greater challenges initially, and thus progress was made first
with 1-L reducibility.
ↆ
