Ladner's Theorem in Computational Complexity Theory
Computational Complexity Theory
Lecture 6:
Ladner’s theorem
Indian Institute of Science
Recap: Diagonalization
Diagonalization
refers to a class of techniques used in
complexity theory to separate complexity classes.
These techniques are characterized by
two
main
features:
1.
There’s a universal TM
U
that when given
strings
α
and
x
, simulates
M
α
on
x
with only a
small
overhead.
2.
Every string represents some TM, and every
TM can be represented by
infinitely many
strings.
Recap: Time Hierarchy Theorem
Let
f(n)
and
g(n)
be time-constructible functions s.t.,
f(n) . log f(n) = o(g(n)).
Theorem.
DTIME(f(n))
⊊
DTIME(g(n))
Theorem.
P
⊊
EXP
Ladner’s Theorem
- Another application of Diagonalization
NP-intermediate problems
Definition.
A language
L
in
NP
is
NP-intermediate
if
L
is
neither in
P
nor NP-complete.
NP-intermediate problems
Definition.
A language
L
in
NP
is
NP-intermediate
if
L
is
neither in
P
nor NP-complete.
P
NPC
NP
NP-intermediate
NP-intermediate problems
Definition.
A language
L
in
NP
is
NP-intermediate
if
L
is
neither in
P
nor NP-complete.
P
NPC
NP
NP-intermediate
(
integer factoring, graph
isomorphism ??
)
NP-intermediate problems
Definition.
A language
L
in
NP
is
NP-intermediate
if
L
is
neither in
P
nor NP-complete.
… the notion makes sense only if
P ≠ NP
NP-intermediate problems
Definition.
A language
L
in
NP
is
NP-intermediate
if
L
is
neither in
P
nor NP-complete.
Theorem.
(Ladner)
If
P ≠ NP
then there is an NP-
intermediate language.
NP-intermediate problems
Definition.
A language
L
in
NP
is
NP-intermediate
if
L
is
neither in
P
nor NP-complete.
Theorem.
(Ladner)
If
P ≠ NP
then there is an NP-
intermediate language.
Proof.
A delicate argument using diagonalization.
NP-intermediate problems
NP-intermediate problems
m
H(m)
NP-intermediate problems
m
H(m)
H
would be defined in such a way that
SAT
H
is NP-intermediate
(assuming
P ≠ NP
)
Ladner’s theorem: Constructing H
Ladner’s theorem: Constructing H
for every m
Ladner’s theorem: Constructing H
∞
Ladner’s theorem: Constructing H
∞
Ladner’s theorem: Proof
P ≠ NP
Suppose
SAT
H
∈
P
. Then
H(m) ≤ C.
Ladner’s theorem: Proof
P ≠ NP
Suppose
SAT
H
∈
P
. Then
H(m) ≤ C.
This implies a poly-time algorithm for
SAT
as follows:
Ladner’s theorem: Proof
P ≠ NP
Suppose
SAT
H
∈
P
. Then
H(m) ≤ C.
This implies a poly-time algorithm for
SAT
as follows:
On input
ϕ
, find
m = |ϕ|
.
Ladner’s theorem: Proof
P ≠ NP
Suppose
SAT
H
∈
P
. Then
H(m) ≤ C.
This implies a poly-time algorithm for
SAT
as follows:
On input
ϕ
, find
m = |ϕ|
.
Compute
H(m)
, and construct the string
ϕ 0 1
m
H(m)
Ladner’s theorem: Proof
P ≠ NP
Suppose
SAT
H
∈
P
. Then
H(m) ≤ C.
This implies a poly-time algorithm for
SAT
as follows:
On input
ϕ
, find
m = |ϕ|
.
Compute
H(m)
, and construct the string
ϕ 0 1
Check if
ϕ 0 1
belongs to
SAT
H
m
H(m)
m
H(m)
Ladner’s theorem: Proof
P ≠ NP
Suppose
SAT
H
∈
P
. Then
H(m) ≤ C.
This implies a poly-time algorithm for
SAT
as follows:
On input
ϕ
, find
m = |ϕ|
.
Compute
H(m)
, and construct the string
ϕ 0 1
Check if
ϕ 0 1
belongs to
SAT
H
m
H(m)
m
H(m)
length at most
m + 1 + m
C
Ladner’s theorem: Proof
P ≠ NP
Suppose
SAT
H
∈
P
. Then
H(m) ≤ C.
This implies a poly-time algorithm for
SAT
as follows:
On input
ϕ
, find
m = |ϕ|
.
Compute
H(m)
, and construct the string
ϕ 0 1
Check if
ϕ 0 1
belongs to
SAT
H
As
P ≠ NP,
it must be that
SAT
H
∉
P
.
m
H(m)
m
H(m)
Ladner’s theorem: Proof
P ≠ NP
Suppose
SAT
H
is NP-complete. Then
H(m)
with
m.
∞
Ladner’s theorem: Proof
P ≠ NP
Suppose
SAT
H
is NP-complete. Then
H(m)
with
m.
This also implies a poly-time algorithm for
SAT
:
∞
SAT ≤
p
SAT
H
ϕ Ψ 0 1
k
f
Ladner’s theorem: Proof
P ≠ NP
Suppose
SAT
H
is NP-complete. Then
H(m)
with
m.
This also implies a poly-time algorithm for
SAT
:
∞
SAT ≤
p
SAT
H
ϕ Ψ 0 1
k
f
|ϕ| = n
|Ψ 0 1
k
| = n
c
Ladner’s theorem: Proof
P ≠ NP
Suppose
SAT
H
is NP-complete. Then
H(m)
with
m.
This also implies a poly-time algorithm for
SAT
:
On input
ϕ
, compute
f(ϕ) = Ψ 0 1
k
. Let
m = |Ψ|
.
∞
SAT ≤
p
SAT
H
ϕ Ψ 0 1
k
f
Ladner’s theorem: Proof
P ≠ NP
Suppose
SAT
H
is NP-complete. Then
H(m)
with
m.
This also implies a poly-time algorithm for
SAT
:
On input
ϕ
, compute
f(ϕ) = Ψ 0 1
k
. Let
m = |Ψ|
.
Compute
H(m)
and check if
k = m
H(m)
.
∞
SAT ≤
p
SAT
H
ϕ Ψ 0 1
k
f
Ladner’s theorem: Proof
P ≠ NP
Suppose
SAT
H
is NP-complete. Then
H(m)
with
m.
This also implies a poly-time algorithm for
SAT
:
On input
ϕ
, compute
f(ϕ) = Ψ 0 1
k
. Let
m = |Ψ|
.
Compute
H(m)
and check if
k = m
H(m)
.
∞
SAT ≤
p
SAT
H
ϕ Ψ 0 1
k
f
Either
m
is small (in which case the task reduces to
checking if a small
Ψ
is satisfiable),
Ladner’s theorem: Proof
P ≠ NP
Suppose
SAT
H
is NP-complete. Then
H(m)
with
m.
This also implies a poly-time algorithm for
SAT
:
On input
ϕ
, compute
f(ϕ) = Ψ 0 1
k
. Let
m = |Ψ|
.
Compute
H(m)
and check if
k = m
H(m)
.
∞
SAT ≤
p
SAT
H
ϕ Ψ 0 1
k
f
or
H(m) > 2c
(as
H(m)
tends to infinity with
m
).
Ladner’s theorem: Proof
P ≠ NP
Suppose
SAT
H
is NP-complete. Then
H(m)
with
m.
This also implies a poly-time algorithm for
SAT
:
On input
ϕ
, compute
f(ϕ) = Ψ 0 1
k
. Let
m = |Ψ|
.
Compute
H(m)
and check if
k = m
H(m)
.
Hence, w.lo.g.
|f(ϕ)| ≥ m
2c
∞
SAT ≤
p
SAT
H
ϕ Ψ 0 1
k
f
Ladner’s theorem: Proof
P ≠ NP
Suppose
SAT
H
is NP-complete. Then
H(m)
with
m.
This also implies a poly-time algorithm for
SAT
:
On input
ϕ
, compute
f(ϕ) = Ψ 0 1
k
. Let
m = |Ψ|
.
Compute
H(m)
and check if
k = m
H(m)
.
Hence, w.l.o.g.
n
c
=
|f(ϕ)| ≥ m
2c
∞
SAT ≤
p
SAT
H
ϕ Ψ 0 1
k
f
Ladner’s theorem: Proof
P ≠ NP
Suppose
SAT
H
is NP-complete. Then
H(m)
with
m.
This also implies a poly-time algorithm for
SAT
:
On input
ϕ
, compute
f(ϕ) = Ψ 0 1
k
. Let
m = |Ψ|
.
Compute
H(m)
and check if
k = m
H(m)
.
Hence,
√n ≥ m
∞
SAT ≤
p
SAT
H
ϕ Ψ 0 1
k
f
Ladner’s theorem: Proof
P ≠ NP
Suppose
SAT
H
is NP-complete. Then
H(m)
with
m.
This also implies a poly-time algorithm for
SAT
:
On input
ϕ
, compute
f(ϕ) = Ψ 0 1
k
. Let
m = |Ψ|
.
Compute
H(m)
and check if
k = m
H(m)
.
Hence,
√n ≥ m.
Also
ϕ
∈
SAT
iff
Ψ
∈
SAT
∞
SAT ≤
p
SAT
H
ϕ Ψ 0 1
k
f
Ladner’s theorem: Proof
P ≠ NP
Suppose
SAT
H
is NP-complete. Then
H(m)
with
m.
This also implies a poly-time algorithm for
SAT
:
On input
ϕ
, compute
f(ϕ) = Ψ 0 1
k
. Let
m = |Ψ|
.
Compute
H(m)
and check if
k = m
H(m)
.
Hence,
√n ≥ m.
Also
ϕ
∈
SAT
iff
Ψ
∈
SAT
∞
SAT ≤
p
SAT
H
ϕ Ψ 0 1
k
f
Thus, checking if an
n
-size formula
ϕ
is satisfiable reduces to checking if a
√n
-
size formula
Ψ
is satisfiable.
Ladner’s theorem: Proof
P ≠ NP
Suppose
SAT
H
is NP-complete. Then
H(m)
with
m.
This also implies a poly-time algorithm for
SAT
:
On input
ϕ
, compute
f(ϕ) = Ψ 0 1
k
. Let
m = |Ψ|
.
Compute
H(m)
and check if
k = m
H(m)
.
Hence,
√n ≥ m.
Also
ϕ
∈
SAT
iff
Ψ
∈
SAT
∞
SAT ≤
p
SAT
H
ϕ Ψ 0 1
k
f
Do this recursively! Only
O(log log n)
recursive steps required.
Ladner’s theorem: Proof
P ≠ NP
Suppose
SAT
H
is NP-complete. Then
H(m)
with
m.
This also implies a poly-time algorithm for
SAT
:
On input
ϕ
, compute
f(ϕ) = Ψ 0 1
k
. Let
m = |Ψ|
.
Compute
H(m)
and check if
k = m
H(m)
.
Hence,
√n ≥ m.
Also
ϕ
∈
SAT
iff
Ψ
∈
SAT
Hence
SAT
H
is not NP-complete, as
P ≠ NP
.
∞
SAT ≤
p
SAT
H
ϕ Ψ 0 1
k
f
Ladner’s theorem: Properties of H
∞
m
H(m)
Construction of H
Observation.
The value of
H(m)
determines
membership in
SAT
H
of strings whose length is
≥ m
.
Therefore, it is OK to define
H(m)
based on strings in
SAT
H
whose length is
< m
(say,
log m
).
Construction of H
Observation.
The value of
H(m)
determines
membership in
SAT
H
of strings whose length is
≥ m
.
Therefore, it is OK to define
H(m)
based on strings in
SAT
H
whose length is
< m
(say,
log m
).
Construction.
H(m)
is the smallest
k < log log m
s.t.
1.
M
k
decides membership of
all
length up to
log m
strings
x
in
SAT
H
within
k.|x|
k
time.
2.
If no such
k
exists then
H(m) = log log m
.
Construction of H
Observation.
The value of
H(m)
determines
membership in
SAT
H
of strings whose length is
≥ m
.
Therefore, it is OK to define
H(m)
based on strings in
SAT
H
whose length is
< m
(say,
log m
).
Homework.
Prove that
H(m)
is computable from
m
in
O(m
3
)
time.
Construction of H
Claim.
If
SAT
H
∈
P
then
H(m) ≤ C
(a constant).
Proof.
There is a poly-time
M
that decides
membership of every
x
in
SAT
H
within
c.|x|
c
time.
Construction of H
Claim.
If
SAT
H
∈
P
then
H(m) ≤ C
(a constant).
Proof.
There is a poly-time
M
that decides
membership of every
x
in
SAT
H
within
c.|x|
c
time.
As
M
can be represented by infinitely many strings,
there’s an
α ≥ c
s.t.
M = M
α
decides membership of
every
x
in
SAT
H
within
α
.|x|
α
time.
So, for every
m
satisfying
α
< log log m
,
H(m) ≤
α.
Construction of H
Claim.
If
H(m) ≤ C
(a constant)
then
SAT
H
∈
P
.
Proof.
There’s a
k
≤
C
s.t.
H(m) = k
for infinitely many
m
.
Construction of H
Claim.
If
H(m) ≤ C
(a constant)
then
SAT
H
∈
P
.
Proof.
There’s a
k
≤
C
s.t.
H(m) = k
for infinitely many
m
.
Pick any
x
∈
{0,1}*. Think of a large enough
m
s.t.
|x| ≤ log m
and
H(m) = k
.
Construction of H
Claim.
If
H(m) ≤ C
(a constant)
then
SAT
H
∈
P
.
Proof.
There’s a
k
≤
C
s.t.
H(m) = k
for infinitely many
m
.
Pick any
x
∈
{0,1}*. Think of a large enough
m
s.t.
|x| ≤ log m
and
H(m) = k
.
This means
x
is correctly decided by
M
k
in
k.|x|
k
time.
So,
M
k
is a poly-time machine deciding
SAT
H
.
Natural NP-intermediate problem?
Integer factoring.
FACT =
{(N, U):
there’s a prime
≤ U
dividing
N
}
Claim.
FACT
∈
NP
∩
co-NP
So,
FACT
is NP-complete if and only if
NP
= co-NP
.
Ladner's Theorem is a significant result in computational complexity theory that deals with NP-intermediate problems, which are languages in NP neither in P nor NP-complete. The theorem states that if P is not equal to NP, then there must exist an NP-intermediate language. The proof involves a delicate argument using diagonalization techniques.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Computational Complexity Theory Lecture 6: Ladner s theorem Indian Institute of Science
Recap: Diagonalization Diagonalization refers to a class of techniques used in complexity theory to separate complexity classes. These techniques are characterized by two main features: 1. There s a universal TM U that when given strings and x, simulates M on x with only a small overhead. 2. Every string represents some TM, and every TM can be represented by infinitely many strings.
Recap: Time Hierarchy Theorem Let f(n) and g(n) be time-constructible functions s.t., f(n) . log f(n) = o(g(n)). Theorem. DTIME(f(n)) DTIME(g(n)) Theorem. P EXP
Ladners Theorem - Another application of Diagonalization
NP-intermediate problems Definition. A language L in NP is NP-intermediate if L is neither in P nor NP-complete.
NP-intermediate problems Definition. A language L in NP is NP-intermediate if L is neither in P nor NP-complete. NPC NP-intermediate NP P
NP-intermediate problems Definition. A language L in NP is NP-intermediate if L is neither in P nor NP-complete. NPC NP-intermediate (integer factoring, graph isomorphism ??) NP P
NP-intermediate problems Definition. A language L in NP is NP-intermediate if L is neither in P nor NP-complete. the notion makes sense only if P NP
NP-intermediate problems Definition. A language L in NP is NP-intermediate if L is neither in P nor NP-complete. Theorem. (Ladner) If P NP then there is an NP- intermediate language.
NP-intermediate problems Definition. A language L in NP is NP-intermediate if L is neither in P nor NP-complete. Theorem. (Ladner) If P NP then there is an NP- intermediate language. Proof. A delicate argument using diagonalization.
NP-intermediate problems Definition. A language L in NP is NP-intermediate if L is neither in P nor NP-complete. Theorem. (Ladner) If P NP then there is an NP- intermediate language. Proof. Let H: N N be a function.
NP-intermediate problems Definition. A language L in NP is NP-intermediate if L is neither in P nor NP-complete. Theorem. (Ladner) If P NP then there is an NP- intermediate language. Proof. Let H: N N be a function. Let SATH = { 0 1 : SAT and | | = m} mH(m)
NP-intermediate problems Definition. A language L in NP is NP-intermediate if L is neither in P nor NP-complete. Theorem. (Ladner) If P NP then there is an NP- intermediate language. Proof. Let H: N N be a function. Let SATH = { 0 1 : SAT and | | = m} mH(m) H would be defined in such a way that SATH is NP-intermediate (assuming P NP )
Ladners theorem: Constructing H Theorem. There s a function H: N N such that 1. H(m) is computable from m in O(m3) time
Ladners theorem: Constructing H Theorem. There s a function H: N N such that 1. H(m) is computable from m in O(m3) time 2. SATH P H(m) C (a constant) for every m
Ladners theorem: Constructing H Theorem. There s a function H: N N such that 1. H(m) is computable from m in O(m3) time 2. SATH P H(m) C (a constant) 3. If SATH P then H(m) with m
Ladners theorem: Constructing H Theorem. There s a function H: N N such that 1. H(m) is computable from m in O(m3) time 2. SATH P H(m) C (a constant) 3. If SATH P then H(m) with m Proof: Later (uses diagonalization).
Ladners theorem: Proof P NP Suppose SATH P. Then H(m) C.
Ladners theorem: Proof P NP Suppose SATH P. Then H(m) C. This implies a poly-time algorithm for SAT as follows:
Ladners theorem: Proof P NP Suppose SATH P. Then H(m) C. This implies a poly-time algorithm for SAT as follows: On input , find m = | |.
Ladners theorem: Proof P NP Suppose SATH P. Then H(m) C. This implies a poly-time algorithm for SAT as follows: On input , find m = | |. mH(m) Compute H(m), and construct the string 0 1
Ladners theorem: Proof P NP Suppose SATH P. Then H(m) C. This implies a poly-time algorithm for SAT as follows: On input , find m = | |. mH(m) Compute H(m), and construct the string 0 1 mH(m) Check if 0 1 belongs to SATH
Ladners theorem: Proof P NP Suppose SATH P. Then H(m) C. This implies a poly-time algorithm for SAT as follows: On input , find m = | |. mH(m) Compute H(m), and construct the string 0 1 mH(m) Check if 0 1 belongs to SATH length at most m + 1 + mC
Ladners theorem: Proof P NP Suppose SATH P. Then H(m) C. This implies a poly-time algorithm for SAT as follows: On input , find m = | |. mH(m) Compute H(m), and construct the string 0 1 mH(m) Check if 0 1 belongs to SATH As P NP, it must be that SATH P .
Ladners theorem: Proof P NP Suppose SATH is NP-complete. Then H(m) with m.
Ladners theorem: Proof P NP This also implies a poly-time algorithm for SAT: Suppose SATH is NP-complete. Then H(m) with m. f 0 1k SAT p SATH
Ladners theorem: Proof P NP This also implies a poly-time algorithm for SAT: Suppose SATH is NP-complete. Then H(m) with m. f 0 1k SAT p SATH | | = n | 0 1k| = nc
Ladners theorem: Proof P NP Suppose SATH is NP-complete. Then H(m) with m. This also implies a poly-time algorithm for SAT: f 0 1k SAT p SATH On input , compute f( ) = 0 1k. Let m = | |.
Ladners theorem: Proof P NP Suppose SATH is NP-complete. Then H(m) with m. This also implies a poly-time algorithm for SAT: f 0 1k SAT p SATH On input , compute f( ) = 0 1k. Let m = | |. Compute H(m) and check if k = mH(m).
Ladners theorem: Proof P NP Suppose SATH is NP-complete. Then H(m) with m. This also implies a poly-time algorithm for SAT: f 0 1k SAT p SATH On input , compute f( ) = 0 1k. Let m = | |. Compute H(m) and check if k = mH(m). Either m is small (in which case the task reduces to checking if a small is satisfiable),
Ladners theorem: Proof P NP Suppose SATH is NP-complete. Then H(m) with m. This also implies a poly-time algorithm for SAT: f 0 1k SAT p SATH On input , compute f( ) = 0 1k. Let m = | |. Compute H(m) and check if k = mH(m). or H(m) > 2c (as H(m) tends to infinity with m).
Ladners theorem: Proof P NP Suppose SATH is NP-complete. Then H(m) with m. This also implies a poly-time algorithm for SAT: f 0 1k SAT p SATH On input , compute f( ) = 0 1k. Let m = | |. Compute H(m) and check if k = mH(m). Hence, w.lo.g. |f( )| m2c
Ladners theorem: Proof P NP Suppose SATH is NP-complete. Then H(m) with m. This also implies a poly-time algorithm for SAT: f 0 1k SAT p SATH On input , compute f( ) = 0 1k. Let m = | |. Compute H(m) and check if k = mH(m). Hence, w.l.o.g. nc = |f( )| m2c
Ladners theorem: Proof P NP Suppose SATH is NP-complete. Then H(m) with m. This also implies a poly-time algorithm for SAT: f 0 1k SAT p SATH On input , compute f( ) = 0 1k. Let m = | |. Compute H(m) and check if k = mH(m). Hence, n m
Ladners theorem: Proof P NP Suppose SATH is NP-complete. Then H(m) with m. This also implies a poly-time algorithm for SAT: f 0 1k SAT p SATH On input , compute f( ) = 0 1k. Let m = | |. Compute H(m) and check if k = mH(m). Hence, n m. Also SAT iff SAT
Ladners theorem: Proof P NP Suppose SATH is NP-complete. Then H(m) with m. This also implies a poly-time algorithm for SAT: f 0 1k SAT p SATH On input , compute f( ) = 0 1k. Let m = | |. Compute H(m) and check if k = mH(m). Hence, n m. Also SAT iff SAT Thus, checking if an n-size formula is satisfiable reduces to checking if a n-size formula is satisfiable.
Ladners theorem: Proof P NP Suppose SATH is NP-complete. Then H(m) with m. This also implies a poly-time algorithm for SAT: f 0 1k SAT p SATH On input , compute f( ) = 0 1k. Let m = | |. Compute H(m) and check if k = mH(m). Hence, n m. Also SAT iff SAT Do this recursively! Only O(log log n) recursive steps required.
Ladners theorem: Proof P NP Suppose SATH is NP-complete. Then H(m) with m. This also implies a poly-time algorithm for SAT: f 0 1k SAT p SATH On input , compute f( ) = 0 1k. Let m = | |. Compute H(m) and check if k = mH(m). Hence, n m. Also SAT iff SAT Hence SATH is not NP-complete, as P NP.
Ladners theorem: Properties of H Theorem. There s a function H: N N such that 1. H(m) is computable from m in O(m3) time 2. SATH P H(m) C (a constant) 3. If SATH P then H(m) with m mH(m) SATH = { 0 1 : SAT and | | = m}
Construction of H Observation. The value of H(m) determines membership in SATH of strings whose length is m. Therefore, it is OK to define H(m) based on strings in SATH whose length is < m (say, log m).
Construction of H Observation. The value of H(m) determines membership in SATH of strings whose length is m. Therefore, it is OK to define H(m) based on strings in SATH whose length is < m (say, log m). Construction. H(m) is the smallest k < log log m s.t. 1. Mk decides membership of all length up to log m strings x in SATH within k.|x|k time. 2. If no such k exists then H(m) = log log m.
Construction of H Observation. The value of H(m) determines membership in SATH of strings whose length is m. Therefore, it is OK to define H(m) based on strings in SATH whose length is < m (say, log m). Homework. Prove that H(m) is computable from m in O(m3) time.
Construction of H Claim. If SATH P then H(m) C (a constant). Proof. There is a poly-time M that decides membership of every x in SATH within c.|x|c time.
Construction of H Claim. If SATH P then H(m) C (a constant). Proof. There is a poly-time M that decides membership of every x in SATH within c.|x|c time. As M can be represented by infinitely many strings, there s an c s.t. M = M decides membership of every x in SATH within .|x| time. So, for every m satisfying < log log m, H(m) .
Construction of H Claim. If H(m) C (a constant) then SATH P. Proof. There s a k C s.t. H(m) = k for infinitely many m.
Construction of H Claim. If H(m) C (a constant) then SATH P. Proof. There s a k C s.t. H(m) = k for infinitely many m. Pick any x {0,1}*. Think of a large enough m s.t. |x| log m and H(m) = k.
Construction of H Claim. If H(m) C (a constant) then SATH P. Proof. There s a k C s.t. H(m) = k for infinitely many m. Pick any x {0,1}*. Think of a large enough m s.t. |x| log m and H(m) = k. This means x is correctly decided by Mk in k.|x|k time. So, Mk is a poly-time machine deciding SATH.
Natural NP-intermediate problem? Integer factoring. FACT = {(N, U): there s a prime U dividing N} Claim. FACT NP co-NP So, FACT is NP-complete if and only if NP = co-NP.
