Information Technology Reference
In-Depth Information
I suspect that FACT is probably not complete for
any
reasonable complexity class
under AC
0
reductions. In an earlier survey [
All01
] I outlined a possible approach
toward proving that this is the case. Namely, I noted that it would suffice to show that
there is no one-one length-increasing NC
0
reduction from FACT
}
∗
to FACT
(or no isomorphism between these sets, computable and invertible in depth-three
AC
0
). All of my attempts to construct such a reduction have involved multiplication
in some form, and this is not computable in AC
0
. Perhaps, I suggested, one could
show that multiplication is inherent, in computing such a reduction. Now, however,
after some illuminating discussions with Michal Koucký, I no longer think that this is
a promising approach. One way to build a padding function would be to map the pair
((
×{
0
,
1
xy
∈
, where
y
∈
has binary representation
x
,
i
,
b
),
y
)
to the triple
(
z
,
i
,
b
)
, where
z
=
is suitably large, and where
z
∈
has log
O
(
1
)
n
bits. If
y
∈
is prime, then it will be the largest prime factor of
z
, and thus the initial
part of the prime factorizations of
x
and of
z
will be the same. The product
xy
∈
can
be computed in AC
0
, because of the padding by 0
ʲ
and because
z
∈
is small. It is
reasonably likely that a value of
z
∈
exists so that
y
∈
will be prime, although number
theorists have not yet established that this holds. It would be
very
hard to show that
no
such
z
∈
can be found in uniform AC
0
. Thus it is reasonably likely that a padding
function for (a suitable encoding of) FACT does exist in AC
0
. This does not guarantee
that such a padding function can be found in NC
0
, but it does illustrate some of the
difficulties of pursuing this approach.
Kabanets and Cai have presented some arguments, suggesting that MCSP is not
complete for NP under
10
ʲ
y
1
0
ʲ
y
2
0
ʲ
...
y
n
−
1
0
ʲ
y
n
0
ʲ
z
∈
where
ʲ
p
m
reductions [
KC00
]. Can one obtain even stronger evi-
dence, suggesting that MCSP is not p-isomorphic to SAT? It is certainly not clear
that MCSP should have a padding function (i.e., a polynomial-time computable and
invertible function
f
mapping MCSP
ↆ
}
∗
onto MCSP). It is even harder to see
how to construct a padding function if one fixes the circuit size
s
to be something
exponentially large, but still much smaller than 2
m
, such as this set:
×{
0
,
1
ˇ
f
denotes a string of length 2
m
that is the truth-table of a Boolean
function
f
on
m
variables such that
f
can be computed by a Boolean circuit of size
at most 2
m
/
2
.}
MCSP2
=
{
ˇ
f
:
As Kabanets and Cai observe [
KC00
], if MCSP2 has a padding function computed in
polynomial time, then
BPP
P
. The connection between the paddability of MCSP2
and the BPP versus P problem arises through the easy observation that any set
C
isomorphic to SAT has a P-printable sets contained both in
C
and in
C
, combined
with the following equivalence (where the first condition listed is the well-studied
Impagliazzo-Wigderson derandomization hypothesis [
IW97
]):
=
E that requires circuits of size greater than 2
n
/
2
for all large
n
•
There is a set
A
iff
•
There is a P-printable set
B
contained in the complement of MCSP2 of the form
B
ˇ
f
denotes a string of length 2
m
that is the truth-table of
A
=
m
}.
=
{
ˇ
f
:
