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
Search WWH ::




Custom Search