Information Technology Reference
In-Depth Information
∈
On the other hand, we claim that
A
P. For, if
A
were in P that would give a
O
(
log log
|
x
|
)
time algorithm to decide if
x
|
|
∈
x
SAT, contradicting the assumption that
n
log
n
SAT is not in DTIME
.
Unfortunately, we can only assume that SAT is not in P and cannot make the
stronger assumption that SAT is not in DTIME
[
]
n
log
n
. So we need to define the
padded language
A
more carefully to make the above argument work. Let
[
]
x
01
k
A
:= {
|
x
∈
SAT
,
k
=
f
(
|
x
|
)
}
,
where the padding function
f
(
n
)
will be computable in time polynomial in
n
and con-
structed by diagonalization. Let
M
i
}
i
>
0
be a recursive enumeration of polynomial-
time clocked, deterministic Turing machines; more precisely, let
M
i
be clocked to
run for
n
i
{
+
i
steps on length
n
inputs. The function
f
is defined as follows:
1.
i
1.
2. For
n
:=
:=
1to
∞
do
n
i
.
4. If there is an input
x
of length at most log
n
such that
M
i
(
3. Let
f
(
n
)
=
x
)
accepts and
x
∈
A
or
M
i
(
x
)
rejects and
x
∈
A
then
i
:=
i
+
1.
5. endfor
Notice that at the
n
th iteration of the for-loop, in which
f
(
n
)
gets defined, the
function
f
(
m
)
is already defined for
m
<
n
and hence checking
x
∈
A
for log
n
∈
length inputs is well defined. Moreover, checking membership of
x
A
can be done
|
|≤
in polynomial in
n
time since
log
n
. Hence,
f
is defined by the above procedure
for all
n
and is computable in time polynomial in
n
. This defines the set
A
.
Suppose
A
x
∈
P. Then
A
=
L
(
M
i
)
for some machine
M
i
. By construction, there
n
k
are constants
n
0
and
k
n
0
. That means, for
all but finitely many input lengths, SAT is polynomial-time reducible to
A
by the
map
x
>
i
such that
f
(
n
)
=
for all
n
>
k
x
01
|
x
|
≈ₒ
which contradicts the assumption P
=
NP. It follows that for each
n
i
for all but finitely many
n
.
Suppose
A
is NP-complete and
g
is a polynomial-time reduction from SAT to
A
. We will give a polynomial-time algorithm for SAT contradicting the assumption.
Since
g
is polynomial-time computable, we have
constant
i
we have
f
(
n
)>
c
|
g(
x
)
|≤|
x
|
for some constant
is not of the form
y
01
f
(
|
y
|
)
we can
c
>
0 and all but finitely many inputs
x
.If
g(
x
)
reject
x
. Also, if
g(
SAT
)
is finite then SAT is trivially in P by table look-up. Suppose
y
01
f
(
|
y
|
)
g(
SAT
)
is infinite. Then for all but finitely many
x
∈
SAT we have
g(
x
)
=
c
. The finitely many exceptions we can keep in a table. Thus, given
a SAT instance
x
we first compute
g(
where
f
(
|
y
|
)>
|
y
|
y
01
f
(
|
y
|
)
.If
x
is not in the look-up table,
x
)
=
c
,itfollowsthat
(
|
|
)<
|
g(
)
|≤|
|
|
|
<
|
|
∈
since
f
y
x
x
y
x
and
x
SAT if and only if
∈
y
SAT. We can now recurse on the instance
y
. Overall this gives a polynomial-time
SAT algorithm contradicting the assumption. This concludes the proof.
Exercise
Suitably adapt the above proof to show for any language
A
∈
P that there
p
m
A
but
A
p
m
B
.
is a language
B
∈
P such that
B
≤
≤