Громкович Ю. Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию
Подождите немного. Документ загружается.
NP
U = (Σ
I
, Σ
0
, L, M, cost, goal )
NPO U
Lang
U
= {(x, a) ∈ L × Σ
∗
bool
| Opt
U
(x) ≤ Number(a)},
goal = minimum
Lang
U
= {(x, a) ∈ L × Σ
∗
bool
| Opt
U
(x) ≥ Number(a)},
goal = maximum
U NP NP
Lang
U
NP
Lang
U
U /∈ PO
P 6= NP
PO 6= NPO
U ∈ PO Lang
U
∈ P
U ∈ PO
A x U
x Opt
U
(x)
A
Lang
U
ut
U ∈ NPO Lang
U
NP P 6= NP
U /∈ PO
U ∈ PO Lang
U
∈ P Lang
U
NP Lang
U
∈ P P = NP ut
MAX SAT NP
NP
Lang
MAX SAT
SAT NP
SAT ≤
p
Lang
MAX SAT
.
x Φ
x
m
(Lang
MAX
SAT
, Σ
∗
)
(x, m)
(x, m) ∈ Lang
MAX
SAT
⇐⇒ Φ
x
ut
MAX CL
G
MAX CL NP
CLIQUE = Lang
MAX CL
CLIQUE NP MAX CL NP ut
MAX CUT MIN VC NP
MMT f
f(n)
n
P
P
MMT M w
M w
NP
P
NP
NP
P
P NP
NP
L /∈ P L
P 6= NP
NP
NP NP
P NP
NP
NP
NP
NP
2
n
n = 100
Time(n)
n
(1.2)
n
n = 100 10 · 2
√
n
n = 300
n = 10 n = 50 n = 100 n = 300
2
n
2
n
2
≈ 33 · 10
6
(1.2)
n
≈ 6 ≈ 9100 ≈ 83 · 10
6
10 · 2
√
n
≈ 89 ≈ 1345 ≈ 1.64 · 10
6
10
−9
{0, 1, #}
∗
#
x = x
1
#x
2
# . . . #x
n
, x
i
∈ {0, 1}
∗
i = 1, 2, . . . , n
{0, 1, #}
∗
x
Int(x) = (Number(x
1
), Number (x
2
), . . . , Number(x
n
)),
n
0 1
TSP
x = x
1
#x
2
# . . . #x
n
x
i
∈ {0, 1}
∗
i = 1, 2, . . . , n
MaxInt(x) = max{Number(x
i
) | i = 1, 2, . . . , n}.
x
MaxInt(x)
|x| y Number (y)
y
1
2
3
U A
A
U p
x U
Time
A
(x) ∈ O (p(|x|, MaxInt(x))).
h
MaxInt(x) ≤ h(|x|) Time
A
(x)
|x|
U h
IN
0
IN
0
h
U Value(h) U
MaxInt(x) ≤ h(|x|).
U A
h
Value(h) U
A U
p
x U
Time
A
(x) ∈ O(p(|x|, MaxInt(x)).
h c
x Value(h) U
MaxInt(x) ∈ O(|x|
c
).
Time
A
(x) ∈ O (p(|x|, |x|
c
)).
A Value(h) U
ut
NP
4
U Value(h) U ∈ P U
Value(h) U ∈ PO
2n + 1 w
1
, w
2
, . . . , w
n
, c
1
, c
2
, . . . , c
n
, b n ∈ IN
n w
i
i
c
i
i = 1, 2, . . . , n b
n
I = (w
1
, w
2
, . . . , w
n
, c
1
, . . . , c
n
, b)
M(I) =
(
T ⊆ {1, . . . , n}
X
i∈T
w
i
≤ b
)
.
I
b
I T ∈ M(I)
cost (T, I) =
X
i∈T
c
i
.
T
maximum
I = (w
1
, w
2
, . . . , w
n
, c
1
, . . . , c
n
, b)
I
1
= (w
1
, c
1
, b)
I
i
= (w
1
, w
2
, . . . , w
i
, c
1
, . . . , c
i
, b)
i = 2, 3, . . . , n I = I
n
I
i
k ∈
{0, 1, 2, . . .
P
i
j=1
c
j
}
(k, W
i,k
, T
i,k
) ∈
0, 1, 2 , . . . ,
i
X
j=1
c
j
× {0, 1, 2, . . . , b} ×P({1, . . . , i});
W
i,k
k
I
i
T
i,k
⊆ {1, . . . , i}
k W
i,k
X
j∈T
i,k
c
j
= k
X
j∈T
i,k
w
j
= W
i,k
.
k W
i,k
(k, W
i,k
) k
I
i
k
I
i
TRIPLE
i
|TRIPLE
i
| ≤
i
X
j=1
c
j
+ 1.
TRIPLE
i+1
TRIPLE
i
O(TRIPLE
i
)
TRIPLE
i+1
SET
i+1
= TRIPLE
i
∪ {(k + c
i+1
, W
i,k
+ w
i+1
, T
i,k
∪ {i + 1}) |
(k, W
i,k
, T
i,k
) ∈ TRIPLE
i
W
i,k
+ w
i+1
≤ b}
(i + 1) TRIPLE
i
b
TRIPLE
i+1
SET
i+1
k TRIPLE
n
I = I
n
DPR
I = (w
1
, w
2
, . . . , w
n
, c
1
, . . . , c
n
, b) ∈ IN
2n+1
n ∈ IN
TRIPLE(1) = {(0, 0, ∅)} ∪ {(c
1
, w
1
, {1})} | w
1
≤ b}
i = 1 n − 1
SET(i + 1) := TRIPLE(i)
(k, w, T ) ∈ TRIPLE(i)
w + w
i+1
≤ b
SET(i + 1) := SET(i + 1 )
∪ {(k + c
i+1
, w + w
i+1
, T ∪ {i + 1})}
TRIPLE(i + 1)
SET(i + 1)
k
SET(i + 1)
k
k
c := max{k ∈ {1, 2 , . . . ,
n
X
i=1
c
i
} | (k, w, T ) ∈ TRIPLE(n)}.
5
k W
i,k