Information Technology Reference
In-Depth Information
p
(
|
x
|
)
−|
w
|
:
(
)
={
,w
|∃
∈
ˇ
,w
∈
}
Define the language pre
A
x
u
x
u
B
.
p
m
pre
Exercise
Show that pre
(
A
)
is in NP and
A
≤
(
A
)
.
A
tally
language is a subset of 0
∗
. The next exercise is about tally languages and
is analogous to Theorem 4.1.
Exercise
For a language
A
∈
NP if pre
(
A
)
is polynomial-time reducible to a tally
language then show that pre
(
A
)
, and hence
A
,isinP.
1.4.1 Subexponentially Dense Languages
ↆ
ˇ
∗
is of
subexponential density
if for every
˃ >
A subset
S
0 there is an
2
n
˃
. A natural question is whether
Mahaney's theorem can be generalized to sets of subexponential density.
The class of languages SUBEXP
S
=
n
n
0
∈ N
such that for all
n
>
n
0
we have
|
|≤
2
n
˃
=∩
˃>
0
DTIME
[
]
consists of languages that
have subexponential time decision procedures.
In the proof of Theorem 4.1 we gave a polynomial-time algorithm for SAT assum-
ing that it is reducible to some sparse language. Modify the proof to show the
following.
Exercise
If SAT is polynomial-time many-one reducible to a language of subexpo-
nential density then show that NP
ↆ
SUBEXP.
SUBEXP is believed unlikely. For instance, it would imply a
2
o
(
n
)
time algorithm for the satisfiability of 3CNF formulas, where
n
is the number of
boolean variables in the input formula. This would, in turn, imply similar subexpo-
nential algorithms for certain other NP-complete problems [
IPZ01
]. For a complexity
theory tailored to the problem of designing faster exponential-time algorithms for
NP-complete problems see [
IPZ01
] and related papers.
For the rest of this sectionwe briefly discuss another unlikely complexity-theoretic
consequence, assuming SAT is reducible to a set of subexponential density. In the
process we will introduce some more basic complexity theory.
We start with the definition of the
polynomial-time hierarchy
. A language
L
is in
the class
The inclusion NP
ↆ
p
k
ˇ
if there are a polynomial
p
(
n
)
and language
A
∈
P such that
L
={
x
|∃
y
1
∀
y
2
···
Q
y
k
:|
y
i
|≤
p
(
|
x
|
)
for all
i
and
x
,
y
1
,
y
2
,...,
y
k
∈
A
}
,
p
k
consists of
where the quantifier “
Q
”is“
∃
”if
k
is odd and “
∀
”if
k
is even. The class
ʲ
p
k
. The following observations are immediate
ˇ
∗
\
all languages
L
such that
L
is in
ˇ
from the definition:
