Bài giảng Phân tích thiết kế giải thuật - Chương 12: NP-Đầy đủ (NP-Completeness)

NP-Ñaày Ñuû

13.11.2004

Ch. 12: NP-Completeness

1

Vaøi khaùi nieäm cô baûn

ª Baøi toaùn

– caùc tham soá

– caùc tính chaát maø lôøi giaûi caàn phaûi thoûa maõn

ª Moät thöïc theå (instance) cuûa baøi toaùn laø baøi toaùn maø caùc tham soá coù

trò cuï theå.

13.11.2004

Ch. 12: NP-Completeness

2

Hình thöùc hoùa khaùi nieäm baøi toaùn

ª Ví duï: baøi toaùn SHORTEST-PATH laø

– “khoâng hình thöùc”: baøi toaùn tìm ñöôøng ñi ngaén nhaát giöõa hai

ñænh cho tröôùc trong moät ñoà thò voâ höôùng, khoâng coù troïng soá G =

(V, E).

– “hình thöùc”:

°

Moät thöïc theå cuûa baøi toaùn laø moät caëp ba goàm moät ñoà thò cuï

theå vaø hai ñænh cuï theå.

°

Moät lôøi giaûi laø moät daõy caùc ñænh cuûa ñoà thò .

Baøi toaùn SHORTEST-PATH laø quan heä keát hôïp moãi thöïc

theå goàm moät ñoà thò vaø hai ñænh vôùi moät ñöôøng ñi ngaén nhaát

(neáu coù) trong ñoà thò noái hai ñænh:

SHORTEST-PATH  I  S

13.11.2004

Ch. 12: NP-Completeness

3

Baøi toaùn tröøu töôïng

ª Ñònh nghóa: moät baøi toaùn tröøu töôïng Q laø moät quan heä nhò phaân treân

moät taäp I, ñöôïc goïi laø taäp caùc thöïc theå (instances) cuûa baøi toaùn, vaø

moät taäp S, ñöôïc goïi laø taäp caùc lôøi giaûi cuûa baøi toaùn:

Q  I  S

13.11.2004

Ch. 12: NP-Completeness

4

Baøi toaùn quyeát ñònh

ª Moät baøi toaùn quyeát ñònh Q laø moät baøi toaùn tröøu töôïng maø quan heä

nhò phaân Q laø moät haøm töø I ñeán S = {0, 1}, 0 töông öùng vôùi “no”, 1

töông öùng vôùi “yes”.

ª Ví duï: baøi toaùn quyeát ñònh PATH laø

Cho moät ñoà thò G = (V, E), hai ñænh u, v  V, vaø moät soá nguyeân

döông k.

Ñaët i = G, u, v, k, moät thöïc theå cuûa baøi toaùn quyeát ñònh PATH,

– PATH(i) = 1 (yes) neáu toàn taïi moät ñöôøng ñi giöõa u vaø v coù chieàu

daøi  k

– PATH(i) = 0 (no) trong caùc tröôøng hôïp khaùc.

13.11.2004

Ch. 12: NP-Completeness

5

Baøi toaùn toái öu

ª Moät baøi toaùn toái öu laø moät baøi toaùn trong ñoù ta caàn xaùc ñònh trò lôùn

nhaát hay trò nhoû nhaát cuûa moät ñaïi löôïng.

ª Ñoái töôïng cuûa lyù thuyeát NP-ñaày ñuû laø caùc baøi toaùn quyeát ñònh, neân

ta phaûi eùp (recast) caùc baøi toaùn toái öu thaønh caùc baøi toaùn quyeát ñònh.

Ví duï: ta ñaõ eùp baøi toaùn toái öu ñöôøng ñi ngaén nhaát thaønh baøi toaùn

quyeát ñònh PATH baèng caùch laøm chaän k thaønh moät tham soá cuûa baøi

toaùn.

13.11.2004

Ch. 12: NP-Completeness

6

Maõ hoaù (encodings)

ª Ñeå moät chöông trình maùy tính giaûi moät baøi toaùn tröøu töôïng thì caùc

thöïc theå cuûa baøi toaùn caàn ñöôïc bieåu dieãn sao cho chöông trình maùy

tính coù theå ñoïc vaø “hieåu” chuùng ñöôïc.

ª Ta maõ hoùa (encode) caùc thöïc theå cuûa moät baøi toaùn tröøu töôïng ñeå

moät chöông trình maùy tính coù theå ñoïc chuùng ñöôïc.

– Ví duï: Maõ hoaù taäp N = {0, 1, 2, 3, 4,...} thaønh taäp caùc chuoãi {0,

1, 10, 11, 100,...}. Trong maõ hoaù naøy, e(17) = 10001.

– Maõ hoùa moät ñoái töôïng ña hôïp (chuoãi, taäp, ñoà thò,...) baèng caùch

keát hôïp caùc maõ hoùa cuûa caùc thaønh phaàn cuûa noù.

13.11.2004

Ch. 12: NP-Completeness

7

Maõ hoaù (tieáp)

ª Moät baøi toaùn cuï theå laø moät baøi toaùn maø taäp caùc thöïc theå cuûa noù laø

taäp caùc chuoãi nhò phaân.

ª Moät giaûi thuaät giaûi moät baøi toaùn cuï theå trong thôøi gian O(T(n)) neáu,

khi ñöa noù moät thöïc theå i coù ñoä daøi n =  i  , thì noù seõ cho ra lôøi giaûi

trong thôøi gian O(T(n)).

ª Moät baøi toaùn cuï theå laø coù theå giaûi ñöôïc trong thôøi gian ña thöùc neáu

toàn taïi moät giaûi thuaät giaûi noù trong thôøi gian O(n^k) vôùi moät haèng soá k

naøo ñoù.

13.11.2004

Ch. 12: NP-Completeness

8

Lôùp P

ª Ñònh nghóa: Lôùp P (complexity class P) laø taäp caùc baøi toaùn quyeát

ñònh cuï theå coù theå giaûi ñöôïc trong thôøi gian ña thöùc.

13.11.2004

Ch. 12: NP-Completeness

9

Baøi toaùn tröøu töôïng vaø baøi toaùn cuï theå

ª Ta duøng maõ hoaù ñeå aùnh xaï caùc baøi toaùn tröøu töôïng ñeán caùc baøi toaùn

cuï theå.

– Cho moät baøi toaùn quyeát ñònh tröøu töôïng Q, Q aùnh xaï moät taäp caùc

thöïc theå I ñeán {0, 1}, ta coù theå duøng moät maõ hoùa e : I → {0, 1}^

ñeå sinh ra moät baøi toaùn quyeát ñònh cuï theå töông öùng, kyù hieäu

e(Q).

Maõ hoùa e phaûi thoõa ñieàu kieän

°

Neáu Q(i)  {0, 1} laø lôøi giaûi cho i  I, thì lôøi giaûi cho thöïc

theå e(i)  {0, 1}^cuûa baøi toaùn quyeát ñònh cuï theå e(Q) cuõng

laø Q(i).

Q

I

{0, 1}

e(Q)

{0, 1}^*

13.11.2004

Ch. 12: NP-Completeness

10

Caùc maõ hoaù

ª Moät haøm f : {0, 1}^→ {0, 1}^laø coù theå tính ñöôïc trong thôøi gian ña

thöùc neáu toàn taïi moät giaûi thuaät thôøi gian ña thöùc A sao cho, vôùi moïi

input x  {0, 1}^, A cho ra output laø f(x).

ª Cho I laø moät taäp caùc thöïc theå cuûa moät baøi toaùn, ta noùi raèng hai maõ

hoaù e₁vaø e₂laø coù lieân quan ña thöùc neáu toàn taïi hai haøm coù theå tính

ñöôïc trong thôøi gian ña thöùc f₁₂vaø f₂₁sao cho vôùi moïi i  I ta coù

f₁₂(e₁(i)) = e₂(i) vaø f₂₁(e₂(i)) = e₁(i).

13.11.2004

Ch. 12: NP-Completeness

11

Lieân quan giöõa caùc maõ hoùa

ª Lemma 36.1

Cho Q laø moät baøi toaùn quyeát ñònh tröøu töôïng treân moät taäp caùc thöïc

theå I, vaø cho e₁vaø e₂laø caùc maõ hoaù treân I coù lieân quan ña thöùc



e₁(Q)  P  e₂(Q)  P.

ª Theo Lemma treân, “ñoä phöùc taïp” cuûa moät baøi toaùn tröøu töôïng maø

caùc thöïc theå cuûa noù ñöôïc maõ hoùa trong cô soá 2 hay 3 thì nhö nhau.

ª Yeâu caàu: seõ chæ duøng caùc maõ hoùa maø lieân quan ña thöùc vôùi “maõ hoùa

chuaån”.

13.11.2004

Ch. 12: NP-Completeness

12

Maõ hoùa chuaån (standard encoding)

ª Maõ hoùa chuaån

aùnh xaï caùc thöïc theå vaøo caùc “chuoãi coù caáu truùc” treân taäp caùc kyù töï

 = {0, 1, - , [, ], (, ), ,}.

Caùc chuoãi coù caáu truùc (structured string) ñöôïc ñònh nghóa ñeä quy. ÔÛ

ñaây chæ trình baøy vaøi ví duï

– Soá nguyeân 13 ñöôïc bieåu dieãn bôûi chuoãi coù caáu truùc 1101.

– Soá nguyeân -13 ñöôïc bieåu dieãn bôûi chuoãi coù caáu truùc -1101.

– Chuoãi [1101] laø moät chuoãi coù caáu truùc coù theå duøng laøm “teân” (ví

duï, cho moät phaàn töû cuûa moät taäp, moät ñænh trong moät ñoà thò,...)

13.11.2004

Ch. 12: NP-Completeness

13

Maõ hoùa chuaån (tieáp)

– Taäp {a, b, c, d} coù theå ñöôïc bieåu dieãn bôûi chuoãi coù caáu truùc

([0], [1], [10], [11])

– Ñoà thò

coù theå ñöôïc bieåu dieãn bôûi chuoãi coù caáu truùc

(([0], [1], [10]), (([0], [1]), ([1], [10])))

taäp caùc caïnh

taäp caùc ñænh

ª Maõ hoùa chuaån cuûa moät ñoái töôïng D ñöôïc kyù hieäu laø <D>.

13.11.2004

Ch. 12: NP-Completeness

14

Moät khung ngoân ngöõ hình thöùc

ª Moät baûng chöõ caùi  laø moät taäp höõu haïn caùc kyù hieäu.

ª Moät ngoân ngöõõ L treân  laø moät taäp caùc chuoãi taïo bôûi caùc kyù hieäu töø

.

– Ví duï: neáu  = {0, 1}, thì L = {10, 11, 101, 111, 1011,...} laø

ngoân ngöõ cuûa caùc bieåu dieãn nhò phaân cuûa caùc soá nguyeân toá.

– Chuoãi roãng ñöôïc kyù hieäu laø , ngoân ngöõ roãng ñöôïc kyù hieäu laø 

.

ª Ngoân ngöõ cuûa taát caû caùc chuoãi treân  ñöôïc kyù hieäu laø ^.

– Ví duï: neáu  = {0, 1}, thì ^= {, 0, 1, 00, 01, 10, 11, 000,…} laø

taäp taát caû caùc chuoãi nhò phaân.

– Moãi ngoân ngöõ L treân  ñeàu laø moät taäp con cuûa ^.

– Hôïp vaø giao cuûa caùc ngoân ngöõ ñöôïc ñònh nghóa gioáng nhö trong

L

lyù thuyeát taäp hôïp

– Phaàn buø cuûa L laø = ^- L .

13.11.2004

Ch. 12: NP-Completeness

15

Baøi toaùn quyeát ñònh vaø ngoân ngöõ töông öùng

ª Ñoàng nhaát moät baøi toaùn quyeát ñònh vôùi moät ngoân ngöõ:

– Taäp caùc thöïc theå cho baát kyø baøi toaùn quyeát ñònh Q naøo laø taäp ^.

Vì Q laø hoaøn toaøn ñöôïc ñaëc tröng bôûi taäp cuûa taát caû caùc thöïc theå

naøo cuûa noù maø lôøi giaûi laø 1 (yes), neân coù theå xem Q nhö laø moät

ngoân ngöõ L treân  = {0, 1}, vôùi

L = {x  ^: Q(x) = 1}

13.11.2004

Ch. 12: NP-Completeness

16

Baøi toaùn quyeát ñònh vaø ngoân ngöõ töông öùng (tieáp)

– Ví duï: baøi toaùn quyeát ñònh PATH laø ngoân ngöõ

{G, u, v, k : G = (V, E) laø moät ñoà thò voâ höôùng,

u, v  V,

k  0 laø moät soá nguyeân, vaø toàn taïi moät

ñöôøng ñi giöõa u vaø v trong G maø chieàu daøi  k}

Ta vieát:

PATH = {G, u, v, k : G = (V, E) laø moät ñoà thò voâ höôùng,

u, v  V,

k  0 laø moät soá nguyeân, vaø toàn taïi moät

ñöôøng ñi giöõa u vaø v trong G maø chieàu daøi

 k}

13.11.2004

Ch. 12: NP-Completeness

17

Ngoân ngöõ vaø giaûi thuaät

ª Moät giaûi thuaät A chaáp nhaän (accept) moät chuoãi x  {0, 1}^neáu, vôùi

input laø x, A outputs A(x) = 1.

ª Moät giaûi thuaät A töø choái (reject) moät chuoãi x  {0, 1}^neáu A(x) = 0.

ª Ngoân ngöõ ñöôïc chaáp nhaän bôûi moät giaûi thuaät A laø taäp caùc chuoãi L =

{x  {0, 1}^: A(x) = 1}.

ª Moät ngoân ngöõ L ñöôïc quyeát ñònh bôûi moät giaûi thuaät A neáu

– moïi chuoãi nhò phaân trong L ñöôïc chaáp nhaän bôûi A vaø

– moïi chuoãi nhò phaân khoâng trong L ñöôïc töø choái bôûi A.

13.11.2004

Ch. 12: NP-Completeness

18

Chaáp nhaän vaø quyeát ñònh ngoân ngöû trong thôøi gian ña thöùc

ª Moät ngoân ngöõ L ñöôïc chaáp nhaän trong thôøi gian ña thöùc bôûi moät giaûi

thuaät A neáu

1. noù ñöôïc chaáp nhaän bôûi A vaø neáu

2. coù moät haèng soá k sao cho vôùi moïi chuoãi x  L coù ñoä daøi n thì A

chaáp nhaän x trong thôøi gian O(n^k).

ª Moät ngoân ngöõ L ñöôïc quyeát ñònh trong thôøi gian ña thöùc bôûi moät giaûi

thuaät A neáu coù moät haèng soá k sao cho vôùi moïi chuoãi x  {0, 1}^coù

chieàu daøi n thì A quyeát ñònh chính xaùc x coù trong L hay khoâng trong

thôøi gian O(n^k).

13.11.2004

Ch. 12: NP-Completeness

19

Lôùp P

ª Moät ñònh nghóa khaùc cuûa lôùp P:

P = {L  {0, 1}^: toàn taïi moät giaûi thuaät A quyeát ñònh L trong thôøi

gian ña thöùc}

ª Ñònh lyù 36.2

P = {L : L ñöôïc chaáp nhaän bôûi moät giaûi thuaät chaïy trong thôøi gian ña

thöùc}

13.11.2004

Ch. 12: NP-Completeness

20