Громкович Ю. Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию

Подождите немного. Документ загружается.

T (c, w, T ) ∈ TRIPLE(n)

DPR I =

, w

, . . . , w

, c

, . . . , c

, b)

= 23, w

= 15, w

= 33, w

= 32,

= 33, c

= 23, c

= 11, c

= 35, c

= 11,

b = 65.

= (23, 33, 65)

TRIPLE

= {(0 , 0, ∅), (33, 23, {1})}.

= (23, 15, 33, 23, 65) I

TRIPLE

= {(0 , 0, ∅), (23, 15, {2}), (33, 23, {1} ), (56, 38 , {1, 2})}.

= (23, 15, 15, 33, 23, 11, 65)

TRIPLE

SET

= TRIPLE

TRIPLE

= {(0, 0, ∅), (11, 15, {3}), (23, 15, {2}),

(33, 23, {1}), (34, 30, {2, 3}), (44, 38, {1, 3}),

(56, 38, {1, 2}), (67, 53, {1, 2, 3 })}.

(44, 38, {1, 3}) (56, 38, {1, 2}) (67, 53, {1, 2, 3}) TRIPLE

TRIPLE

= TRIPLE

∪ {(35, 33, {4}), (46, 48, {3, 4}),

(58, 48, {2, 4}), (68, 56, {1, 4}), (69, 63, {2 , 3, 4})}.

I = I

TRIPLE

= {(0, 0, ∅), (11 , 15, {3}), (2 2, 4 7, {3, 5}),

(23, 15, {2}), (33, 23, {1}), (34, 30, {2, 3}),

(35, 33, {4}), (44, 38, {1, 3}), (45, 62, {2, 3, 5}),

(46, 48, {3, 4}), (56, 38, {1, 2}), (58, 48, {2 , 4}),

(67, 53, {1, 2, 3}), (68, 56, {1, 4}), (69, 63, {2, 3, 4})}.

{2, 3, 4} I (69, 63, {2, 3, 4})

TRIPLE

DPR

(1, 3, 5, 6, 7, 4, 8, 5, 9)

DPR

Time

DPR

(I) ∈ O(|I|

·MaxInt(I)),

DPR

O(1)

I = (w

, w

, . . . , w

, c

, . . . , c

, b) DPR

n − 1 TRIPLE(i + 1) TRIPLE(i + 1)

TRIPLE(i) O(|TRIPLE(i + 1)|)

i ∈ { 0, 1, . . . , n}

|TRIPLE(i + 1)| ≤

j=1

≤ n · MaxInt(I),

O(n

· MaxInt(I))

O(n · MaxInt(I))

n · MaxInt(I)

n ≤ |I|

Time

DPR

(I) ∈ O(|I|

·MaxInt(I)).

• NP

P 6= NP NP

U NP

NP p

Value(p) U NP

U NP P 6= NP

U NP

p Value(p) U NP

U h

Value(h) U

NP Value(p) U

P = NP P 6= NP ut

NP TSP

TSP NP

HC NP

HC ≤

Lang

Value(p) TSP

p(n) = n

G = (V, E) HC |V | = n

n (K

, c) K

= (V, E

complete

)

complete

= {{u, v} | u, v ∈ V, u 6= v},

c : E

complete

→ {1, 2}

c(e) = 1 c ∈ E;

c(e) = 2

c /∈ E.

TSP (K

, c) n

((K

, c), n) ∈ Lang

Value(p)

TSP

Lang

Value(p) TSP

HC ut

G G

G = (V, E) w : V → IN

S S

U = (Σ

, Σ

, L, M, cost, goal)

A U

x ∈ L A(x) x

A(x) ∈ M(x)

A U x ∈ L

(x) A x

(x) = max



cost (A(x))

Opt

(x)

Opt

(x)

cost (A(x))



Opt

(x) x U

δ > 1 A

δ U x ∈ L

(x) ≤ δ.

G = (V, E) M ⊆ E

V M

e ∈ E − M

M ∪ {e} G

VCA

G = (V, E)

C := ∅

V G

A := ∅

E G

:= E

⊆ E

C E

= ∅

6= ∅

{u, v} E

C := C ∪ {u, v}

A := A ∪ {{u, v}}

:= E

− { u v}

VCA

{b, c}

C = {b, c}, A = {{b, c}}, E

= E − {{b, a}, {b, c}, {c, e}, {c, d}}

VCA

{e, f}

C = {b, c, e, f}, A = {{b, c}, {e, f }} E

= {{d, h} , {d, g}, {h, g}}.

VCA {d, g}

C = {b, c, e, f, d, g}, A = {{b, c}, {e, f }, {d, g}} E

= ∅.

C 6

{b, e, d, g}

VCA

b c

f f

VCA

MIN VCP G = (V, E)

Time

VCA

(G) ∈ O (|E|).

Time

VCA

(G) ∈ O(|E|)

E VCA

= ∅ VCA

G MIN VCP

VCA

(G) ≤ 2,

• |C| = 2 · |A|

• A G

|A| A |A|

A ⊆ E G

|A|

Opt

MIN VCP

(G) ≥ |A|.

|C|

Opt

MIN

VCP

(G)

2 · |A|

Opt

MIN

VCP

(G)

≤ 2.

n ∈ IN G

n VCA

P 6= NP d

TSP

P 6= NP d

d TSP

d A TSP

B NP

HC P 6= NP

B HC G = (V, E)

B (K

|V |

, c) TSP

|V |

= (V, E

), E

= {{u, v} | u, v ∈ V, u 6= v},

c(e) = 1 e ∈ E,

c(e) = (d −1) · |V | + 2

e /∈ E.

B A (K

|V |

, c)

|V | B G B G

TSP (K

|V |

, c)

O(|V |

) B

A G K

|V |

B HC

G K

|V |

Opt

TSP

|V |

, c) = |V |.

|V |

− E

|V | − 1 + (d − 1) · |V | + 2 = d ·|V | + 1 > d · |V |.

G = (V, E) ∈ HC B

|V |

G = (V, E) ∈ HC G

C c

|V |

Opt

TSP

|V |

, c) = |V |.

|V |

d · |V | + 1 > d ·|V |.

d A

|V | B G

G = (V, E) HC

|V |

, c) |V | cost(A(K

|V |

, c)) >

|V |

B G

B NP

HC P 6= NP ut

TSP

TSP ∆ TSP

TSP

2 ∆ TSP

G = (V, E) c : E → IN

u, v, w ∈ V

c({u, v}) ≤ c({u, w}) + c({w, v}).

SB T G

SB v V

T v SB

H = H, v

2 2



B ∆ TSP

T = ({v

, v

}, {{v

, v

}, {v

, v

}, {v

, v

}, {v

, v

}}

T v

H = v

, v

G = (V, E) T = (V, E

) E

⊆ E

G T

T E

H = v

, v

= H, v

SB H

2 + 3 + 2 + 3 + 1 = 11

, v

1 + 2 + 2 + 2 + 1 = 8

SB 2

∆ TSP

G = (V, E) O(|E|)

T = (V, E

) O (|V |)

Time

(G) ∈ O (|E|),

2 H

Opt

cost (H

Opt

) =

Opt

∆

TSP

(G)

I = ((V, E), c) ∆ TSP

H SB(I) SB I T = (V, E

)

cost(T ) =

c∈E

c(e) < cost(H

Opt

)

Opt

G T

W T

cost(W )

cost (W ) = 2 · cost(T ).

cost(W ) < 2 · cost(H

Opt

H W

u, v

, . . . , v

, v W {u, v}

u v

W T

, . . . , v

u W v