Information Technology Reference
In-Depth Information
/
Exercise
Show that a language
L
is in P
poly if and only if there is a polynomial-
size circuit family that computes
L
. Similarly, characterize NP
/
poly using circuit
families.
As there is no bound on the computational complexity of advice functions, the
class P
poly contains even noncomputable languages (exercise: prove this). Are
there NP-complete languages in P
/
poly? This could be useful for efficiently solving
NP-complete languages for fixed input lengths. The advice function, computed as a
preprocessing step, serves as a small table that can be looked up to efficiently solve
instances of that fixed length. However, this seems to be unlikely because it implies
that the polynomial hierarchy will collapse to the second level.
/
Theorem 4.2
p
2
[
KL80
]
.
/
=
ˇ
1.
If an
NP
-complete language is in
P
poly
then
PH
p
3
[
Yap83
]
.
Coming back to sets of subexponential density, it is shown in [
BH08
], using a nice
counting argument from [
FS08
], that if SAT is polynomial-time many-one reducible
toaset
S
of subexponential density then coNP
2.
If there is a
coNP
-complete language in
NP
/
poly
then
PH
=
ˇ
ↂ
NP
/
poly which in turn would
p
3
by the above theorem.
imply PH
=
ˇ
1.5 Nondeterministic Logspace
We now turn to logarithmic space bounded complexity classes. A deterministic
logarithmic space-bounded Turing machine is a deterministic Turing machine that
has a read-only input tape and one or more worktapes, where
n
denotes the input
size and the workspace on each worktape is bounded by
O
. By the tape-
compression theorem the constant factor in the space bound is not important. It
can be reduced by suitably increasing the tape alphabet size. Furthermore, multiple
worktapes can be replaced by a single worktape in space-bounded computation. We
denote by DSPACE
(
log
n
)
the class of decision problems that can be solved in deter-
ministic logspace bounded Turing machines. Likewise, NSPACE
[
log
n
]
denotes the
class of languages accepted by
nondeterministic
logspace bounded Turing machines,
where acceptance is defined as usual: the machine accepts an input if there is some
accepting computation path for the machine on that input. The definitions and results
go back to the seminal work of Hartmanis and Stearns [
HS65
] and are well treated
in the classic textbook [
HU79
, Chaps. 12 and 13].
The class DSPACE
[
log
n
]
[
log
n
]
is denoted as L. Likewise, the nondeterministic class
NSPACE
[
log
n
]
is denoted as NL.
Proposition 5.1
L
ↆ
NL
ↆ
P
.
Proof
The first containment is obvious. Consider the nondeterministic computation
of an NL machine
M
on an input
x
of length
n
. Notice that the configurations of
M
