Information Technology Reference
In-Depth Information
2.2.3 Constant-Depth Circuits
Attention was first focused on AC
0
isomorphisms by considering a very restricted
class of AC
0
reductions: projections (which are reductions computed by circuits with
no gates, other than negation gates). Sets complete for NP (and other classes) under
uniform projections are isomorphic under uniform AC
0
isomorphisms [
ABI97
].
The logical next step was to work on extending this result from projections to
NC
0
functions (that is, functions computed by constant-depth circuits with fan-in
input bits—as contrasted with
projections, where each output bit depends on either zero or one input bit). As part
of this investigation, it was also discovered that, at least for the class NC
1
,thesets
complete under AC
0
reductions are also complete under NC
0
reductions, thereby
obtaining the first theorem showing that the sets complete under AC
0
reductions
are all AC
0
isomorphic [
AA96
]. Subsequently, the authors were joined by Rudich,
in showing that this holds not only for NC
1
, but also for NP and for most other
complexity classes of interest [
AAR98
].
These initial AC
0
isomorphism theorems were proved only in the nonuniform
setting. After a series of intermediate steps improving the uniformity condition
[
AAIPR01
,
Agr01
], Agrawal succeeded in overcoming some daunting technical
difficulties, in presenting a Dlogtime-Uniform version of the isomorphism theorem
[
Agr11
], which stands as one of the crowning achievements of the study of the struc-
ture of complete sets. This work not only shows that a natural re-phrasing of the
Berman-Hartmanis Conjecture (in terms of AC
0
reductions and isomorphisms) is
true, but also gives a convincing setting where the Encrypted Complete Set Conjec-
ture fails (since even when
f
is an AC
0
function that provably cannot be inverted in
AC
0
,
f
(SAT) is still AC
0
-isomorphic to SAT).
O
(
1
)
, so that each output bit depends on only
O
(
1
)
2.2.4 Open Questions
Again, please refer to [
Agr11
] for several interesting open questions. Here are a few
additional questions relating to isomorphisms, that are not discussed there.
Two important problems that are not believed to be NP-complete are Factoring
and the Minimum Circuit Size Problem:
FACT
=
{
(
x
,
i
,
b
)
:the
i
th bit of the prime factorization of
x
is
b
}.
ˇ
f
denotes a string of length 2
m
(for some
m
) that is the
truth-table of a Boolean function
f
on
m
variables and
s
denotes an integer such
that
f
can be computed by a Boolean circuit of size at most
s
.}
(In the definition of FACT, the prime factorization is presented as
p
e
1
,...,
MCSP
=
{
(ˇ
f
,
s
)
:
p
e
k
k
,
where each exponent
e
i
>
0, and
p
i
<
p
i
+
1
, so that each number has a unique
prime factorization.)
