3. Kriptográfia (Jörg Rothe)

3. Kriptográfia (Jörg Rothe)

probléEbben a fejezetben a kriptográában használatos protokollokat, valamint alapveto egyik alaphelyzetet látmákat és algoritmusokat mutatunk be. A kriptográában jellemzo hatjuk a 3.1. ábrán. Aliz és Bob híreket cserélnek valamilyen nem biztonságos csatornán, számítógép közötti például nyilvános telefonvonalon, vagy két hálózati kapcsolatban lévo elektronikus posta segítségével. Erik megcsapolja a vezetéket, és lehallgatja a kommunikációt. Mivel Aliz és Bob tudják ezt, a küldeményeiket rejtjelezik.

Erik

3.1. ábra. A kriptográában tipikus alaphelyzet.

A 3.1. alfejezetben olyan szimmetrikus kriptográai rendszereket mutatunk be, amelyek az illetéktelen rejtjelfejtést hivatottak akadályozni. Szimmetrikusnak akkor nevezünk egy kriptográai rendszert, ha ugyanaz a kulcs használható rejtjelezésre (sifrírozásra) és visszafejtésre (desifrírozásra) is. Vajon hogyan kell Aliznak és Bobnak egy közös kulcsban megegyeznie, ha csupán egy megbízhatatlan csatornán tudnak kommunikálni egymással? Ha például Aliz választ egy kulcsot és rejtjelezi (mondjuk egy szimmetrikus rejtjelrendszerrel), majd elküldi Bobnak, azonnal felmerül a kérdés, milyen kulcsot használjanak ezeknek a kulcsoknak a rejtjelezéséhez. kérdés amely egy kicsit emlékeztet arra a másikra, hogy vajon Ez a paradoxnak tun o a tojás, vagy a tyúk volt-e elobb kulcscsere-problémaként ismert. A kriptográa kezde megoldhatatlannak tartották ezt a problémát. Annál nagyobb volt a meglepetés, amitétol kor Whiteld Diffie és Martin Hellman 1976-ban megoldották. Egy protokollt javasoltak, amelyben Aliz és Bob információkat cserélnek, s ennek segítségével végül ki tudják számí tani a közös kulcsukat. Az oket lehallgató Eriknek ugyanakkor fogalma sincs a kulcsukról, minden egyes bitet el tudja fogni. A 3.2. alfemég akkor sem, ha az adatcserében résztvevo jezet bemutatja a DiffieHellman-protokollt.

3.1. Alapok

95

A történet némileg ironikus része az, hogy éppen ez a protokoll, amely a szimmetrikus kriptográában oly fontos kulcscsere megoldhatatlannak tartott problémáját megoldotta, egyengette az utat, s ez utóbbiban a megbízhatatlan egy másik protokoll felfedezése elott titkos kulcscsere már semmilyen szerepet nem játszik. Diffie és Hellman csatornán történo 1976-ban megjelent munkájukkal kaput nyitottak a modern nyilvános kulcsú kriptográ ának, és már két évvel késobb, 1978-ban, Rivest, Shamir és Adleman szélesre tárták ezt a nyilvános kulcsú kriptokaput, amikor megalkották jól ismert RSA-rendszerükkel az elso rendszert. A 3.3. alfejezetben szerepel az RSA-rendszer, valamint egy, az RSA-n alapuló digitális aláírásra vonatkozó protokoll. Egy ilyen protokollal Aliz el tudja látni kézjegyével Bobnak küldött üzeneteit úgy, hogy Bob az üzenet küldojének azonosságát ellenorizni tudja. A digitális aláírások célja annak megakadályozása, hogy Erik Aliz üzenetét meghamisítva úgy tegyen, mintha azt Aliz küldte volna. A DiffieHellman-protokoll biztonsága azon a feltételezésen alapszik, hogy a diszkrét logaritmus nem számítható ki hatékonyan. A moduláris hatványozás amelynek inverz függvénye a diszkrét logaritmus egy lehetséges egyirányú függvény. Az RSA biztonsága is egy probléma feltételezett nehézségén nyugszik, nevezetesen azon a feltételezésen, hogy szorzatára. A jogos címzett Bob nagy számok nem bonthatók hatékonyan prímtényezok ugyanakkor képes hatékonyan visszafejteni a rejtjelezett üzenetet, miközben egy általa választott szám faktorizációját saját

csapóajtó információjaként használja fel. A 3.4. alfejezetben bemutatunk egy RivestSherman-protokollt, amelyik az úgyneve-

zett erosen nem invertálható, asszociatív egyirányú függvényeken nyugszik, és a Diffie Hellman-protokollhoz hasonlóan titkos kulcscserére szolgál. Ez a protokoll is módosítható oly módon, hogy digitális aláírás számára használható legyen. Végül a 3.5. alfejezet az interaktív bizonyításrendszerek és a zéró-ismeretu protokollok érdekes területére vezet, amely a kriptográában gyakorlati felhasználásra kerül, nevezetesen a hitelesség problémájának megoldása során. Bemutatunk egy zéró-ismeretu protokollt a grázomorzmus problémára. Másrészt ez a terület a bonyolultságelmélethez is kapcso lódik, és ezért a 4. fejezetben újból elokerül, ismét a grázomorzmus problémával kapcsolatban.

3.1. Alapok muvészet A kriptográa évezredek óta létezo és tudomány, írások és üzenetek titkos anyagba olyan rejtjelezésével foglalkozik, amely illetéktelen személyek számára akadályozza történo a visszafejtést. Ebben az alfejezetben két klasszikus szimmetrikus kriptorendszert mutatunk alfejezetekben pedig a manapság használatos legfontosabb protokollok és be, a következo aszimmetrikus kriptorendszerek közül foglalkozunk néhánnyal. Protokollon két vagy több közötti párbeszédet értünk, miközben egy résztvevo lehet egy ember, de lehet egy résztvevo számítógép is. A kriptográai protokollok szövegek rejtjelezésére szolgálnak, oly módon, hogy a jogosult fogadó képes legyen egyszeruen és hatékonyan visszafejteni a rejtett szöve hajt végre. get. Egy protokoll algoritmusként is felfogható, melyet több résztvevo és tudomány is, amely rejtjelezett A kriptoanalízis szintén több évezredes muvészet kriptorendszerek feltörésével foglalkoüzenetek (illetéktelen) visszafejtésével és a létezo zik. A kriptológia ezt a két területet öleli fel, a kriptográát és a kriptoanalízist. Ebben a fejezetben foként olyan kriptograkus algoritmusokra koncentrálunk, amelyek lehetové

96


teszik a biztonságos rejtjelezést. A kriptoanalízis algoritmusait amelyekkel az ember próbálkozik, hogy kriptograkus protokollokat és rendszereket feltörjön , megemlítjük, de nem vizsgáljuk teljes részletességgel.

3.1.1. Kriptográfia alaphelyzete a 3.1. ábrán látható: Aliz és Bob olyan nem A kriptográa egyik jellemzo biztonságos csatornán kommunikálnak egymással, amelyet Erik lehallgat, és ezért az üzenetüket rejtjelezik egy kriptorendszer segítségével. 3.1. deníció (kriptorendszer). A kriptorendszer egy (P, C, K, E, D) ötös a következo tulajdonságokkal: 1.

P, C és K

P a nyílt szöveg tér, C a rejtett szöveg tér és K a kulcstér. P C elemeit pedig rejtett szövegnek nevezzük. Egy üzenet a nyílt

véges halmazok,

elemeit nyílt szövegnek

szöveg szimbólumaiból álló szó. 2.

E = {Ek |

k

∈ K}

P → C függvényeknek a családja, amelyeket a D = {Dk | k ∈ K} azoknak a Dk : C → P függvényeknek a

azoknak az E k :

rejtjelezéshez használunk.

családja, amelyeket a visszafejtéshez használunk. 3.

Mindegyik e

∈K

kulcshoz van egy d

∈K

kulcs, melyekre minden p

∈ P nyílt szöveg

esetén Dd (E e ( p))

=

p

.

(3.1)

Egy kriptorendszerre azt mondjuk, hogy szimmetrikus (vagy titkos kulcsú), ha d vagy legalábbis d

=

e

könnyen kiszámítható e-bol. Egy kriptorendszerre azt mondjuk, hogy

aszimmetrikus (vagy nyilvános kulcsú,

public-key), ha d , e, és gyakorlatilag nem végezheto el az a feladat, hogy a d kulcsot e-bol kiszámítjuk. Ekkor e-t nyilvános kulcsnak nevezzük, és d az e-hez tartozó titkos kulcs. kulcstereket használnak a rejtjelezéshez és a visszafejtéshez, ami a Néha különbözo módosítását vonja maga után. fenti deníció megfelelo A klasszikus kriptorendszerek bemutatására példaként legyen a

Σ = {A, B, . . . , Z} ábécé

a nyílt szöveg tér és ugyanakkor a rejtett szöveg tér is. Abból a célból, hogy a betukkel úgy tudjunk számolni, mintha számok lennének, feleltessük meg

Σ-nak Z26 = {0, 1, . . . , 25}-öt.

A 0 szám tehát az A betunek felel meg, az 1 a B betunek stb. A nyílt szöveg szimbólumainak ez a természetes számokkal való kódolása természetesen nem tartozik hozzá a tényleges rejtjelezéshez, illetve visszafejtéshez. Az üzenetek

Σ∗

elemei, ahol

Σ∗

a

Σ fölötti szavak halmazát jelöli. Ha valamely m ∈ Σ∗

üzenet n hosszúságú blokkokra van felosztva, és blokkonként van rejtjelezve ahogyan az sok kriptorendszerben szokásos , akkor m egyes blokkjait 3.1. példa. Legyen

Zn26

elemeiként értelmezhetjük.

Az elso példa egy monoalfabetikus szimmetrikus kriptorendszer. Eltolásos rejtjelezo.

K = P = C = Z26 .

Az eltolásos rejtjel az a rejtett üzenet, amelyben a nyílt szöveg minden

jelének az ábécében a k számú betuvel eltolt jel felel meg (modulo 26), ahol k rögzített szám. Az itt k szereplo

∈ Z26

a kulcs. Ha a rejtett szöveg minden jelét ugyanennek a k kulcsnak a felhasználásával

függvényt és a Dk visszafejto visszatoljuk, akkor feltárul elottünk a nyílt szöveg. Az E k rejtjelezo

3.1. Alapok

97 m

B U D A P E S T

c

E X G D S H V W N H O H W S D U L C V D

K E L E T

P Á R I Z S A

sifrírozásra. 3.2. ábra. Példa a Caesar-rejtjelezovel történo

függvényt mindegyik k

∈ Z26

kulcs esetén az alábbi módon deniáljuk: E k (m)

=

(m

Dk (c)

=

(c

+ k) mod 26

− k) mod 26 ,

ahol a k-val való összeadást és kivonást jelenként, modulo 26 kell elvégezni. rejtjelezése k A 3.2. ábrán látható egy magyar m üzenetnek a c kóddal történo Az eltolással való rejtjelezés ezzel a speciális k

=

=

3 esetén.

1

3 kulccsal Caesar-rejtjelezo néven is ismeretes,

mert feltehetoen a római császár ezt használta háborúiban a katonai üzenetek titkosítására.

2

Ez egy

amelyikben a nyílt szöveg minden betujét nagyon egyszeru helyettesítéses rejtjelezo, a rejtjel ábécé egy meghatározott betujével helyettesítenek.

Mivel a kulcstér nagyon kicsi, az eltolásos rejtjelet igen könnyu feltörni. Ez a rejtjel már arra a támadásra is érzékeny, amelynek során a támadó csupán a rejtett szöveget ismeri (rejtett szövegu támadás. Ha egyszeruen a 26 lehetséges kulcs mindegyikét végigpróbáljuk, kiderül, hogy melyik kulcs esetén adódik értelmes nyílt szöveg, ha pedig a rejtjelezés adódik. rejtett szöveg elég hosszú, csak egy megfelelo monoalfabetikus kriptorendszer, mert a nyílt szöveg minden betuA Caesar-rejtjelezo jének a rejtett szövegben mindig ugyanaz a betu felel meg. Ezzel szemben egy polialfabetikus kriptorendszerben lehetséges, hogy ugyanannak a nyílt szövegbeli szimbólumnak kü rejtett szövegbeli szimbólumok felelnek meg, attól függoen, lönbözo hogy a szöveg melyik helyén állnak. Egy ilyen polialfabetikus kriptorendszert, amelyik az eltolásos rejtjelezésre épül, de jóval nehezebb feltörni, Blaise de Vigenère (15231596) francia diplomata javasolt. Rendszere Leon Battista Alberti (szül. 1404) itáliai matematikus, Johannes Trithemius (szül. 1492) német apát és Giovanni Porta (szül. 1535) itáliai természettudós elomunkáira úgy muködik, azzal a különbséggel, hogy épül. Ez a rejtjelezo mint az eltolásos rejtjelezo, a betuk, amelyekkel a nyílt szöveg egy szimbóluma sifrírozva van, most még a szövegbeli helyüknek megfeleloen is változnak. 3.2. példa.

Vigenère-rejtjelezo. Ez a szimmetrikus polialfabetikus kriptorendszer egy úgynevezett

Vigenère-négyzetet használ (lásd a 3.3. ábrát). Ez egy 26 sorból és 26 oszlopból álló mátrix. Mindegyik sorban az ábécé 26 betuje szerepel, sorról sorra mindig egy pozícióval balra tolva. Ez azt jelenti, hogy az egyes sorok felfoghatók egy-egy eltolásos rejtjelezoként, ahol a kulcsok sorban 0, 1, . . . , 25. függ az, hogy a Vigenère-négyzet melyik sorát használja az ember A szimbólum szövegbeli helyétol egy nyílt szövegbeli szimbólum rejtésére. Az üzeneteket n állandó hosszúságú blokkra osztjuk és blokkonként rejtjelezzük, vagyis

P = C = Zn26 . Az n

K =

blokkhosszat a rendszer periódusának is nevezik. Egy w szóban az i-edik betut

wi -vel jelöljük.

1

ékezet nélkülieké. A fordító. Az ékezetes betuk kódja ugyanaz, mint a megfelelo

2

Történelmi megjegyzés: Gaius Julius Caesar De Bello Gallico címu muvében tudósít arról, hogy a gall háborúban

(5850 Kr.e.) hogyan küldött egy rejtjelezett üzenetet Q. Tullius Ciceronak (a híres szónok testvéröccsének), aki légiójával ostrom alatt volt. Az alkalmazott rendszer monoalfabetikus volt, és a latin betuket göröggel helyettesí ol volt-e szó. Ezt tette, Caesar írásaiból nem derül ki azonban az, hogy valóban a k = 3 kulcsú eltolásos rejtjelezor az információt késobb Suetonius adta.

98

3. Kriptográfia (Jörg Rothe) 0

A

B

C

D

E

F

G

H

I

J

K

L

1

B

C

D

E

F

G

H

I

J

K

L

M N

M N

2

C

D

E

F

G

H

I

J

K

L

M N

3

D

E

F

G

H

I

J

K

L

M N

4

E

F

G

H

I

J

K

L

M N

5

F

G

H

I

J

K

L

M N

6

G

H

I

J

K

L

M N

7

H

I

J

K

L

M N

8

I

J

K

L

M N

9

J

K

L

M N

10

K

L

M N

11

L

M N

12

M N

O

13

N

O

14

O

15

P

16

Q

17

R

O

P

Q

R

S

T

U

O

P

Q

R

S

T

U

V W X

V W X

O

P

Q

R

S

T

U

O

P

Q

R

S

T

U

V W X

O

P

Q

R

S

T

U

V W X

V W X

O

P

Q

R

S

T

U

O

P

Q

R

S

T

U

V W X

V W X

O

P

Q

R

S

T

U

O

P

Q

R

S

T

U

V W X

O

P

Q

R

S

T

U

V W X

O

P

Q

R

S

T

U

V W X

O

P

Q

R

S

T

U

V W X

P

Q

R

S

T

U

V W X

P

Q

R

S

T

U

V W X

P

Q

R

S

T

U

V W X

Q

R

S

T

U

V W X

R

S

T

U

V W X

S

T

U

V W X

V W X

18

S

T

U

19

T

U

V W X

20

U

V W X

21

V W X

V W X

A B

Y

Z

A

Y

Z

A

B

C

Y

Z

A

B

C

D

Y

Z

A

B

C

D

E

Y

Z

A

B

C

D

E

F

Y

Z

A

B

C

D

E

F

G

Z

A

B

C

D

E

F

G

H

Y

Z

A

B

C

D

E

F

G

H

I

Y

Z

A

B

C

D

E

F

G

H

I

J K

Y

Z

A

B

C

D

E

F

G

H

I

J

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

M N

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M N

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M N

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M N

M N

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M N

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M N

M N

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M N

23

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M N

24

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M N

25

Z

A

B

C

D

E

F

G

H

I

J

K

L

M N

3.3. ábra. Vigenère-négyzet: a

H nyílt szöveget a

O

O

O

P

O

P

Q R

O

P

Q

O

P

Q

R

S

O

P

Q

R

S

T

O

P

Q

R

S

T

U

O

P

Q

R

S

T

U

V

O

P

Q

R

S

T

U

V W

O

P

Q

R

S

T

U

V W X

P

Q

R

S

T

U

V W X

T kulccsal rejtjelezve

Y

A-t kapunk.

függvényt és a Dk visszafejto függvényt, amelyek mindketten Az E k rejtjelezo

∈ Zn26

Z

Z

Y

22 W X

képeznek, mindegyik k

Y

Y

n Z26 -be Zn26 -bol

kulcs esetén a következoképpen deniáljuk:

E k (b)

=

(b

+ k) mod 26

Dk (c)

=

(c

− k) mod 26 ,

ahol a k-val való összeadást és kivonást megint jelenként kell elvégezni modulo 26. Ez azt jelenti, hogy a megbeszélt k

∈ Zn26

beture kulcsot betur ol a b

∈ Zn26

blokk szimbólumai fölé írjuk. Ha a

nyílt szöveg utolsó blokkjának kevesebb szimbóluma van, mint n, akkor a kulcsnak csak annyi jelét használjuk fel, amennyi szükséges. Amikor a nyílt szöveg i-edik bi szimbólumát rejtjelezzük, fölötte a ki kulcsszimbólum áll, és a Vigenère-négyzet ki -edik sorát használjuk eltolásos rejtjelezoként. Válasszuk például az n

=

4 blokkhosszat, és a k

=

TONY kulcsot. A 3.4. ábra egy angol nyelvu

m nyílt szöveg rejtjelezését mutatja, amelyik hét blokkból áll, és a c rejtett szövegben a Vigenère alkalmaztuk a k kulccsal. A nyílt szöveg elso betujéhez, rejtjelezot a

H-hoz a T kulcsszimbólu H-oszlopának és a T-sorának keresztezodésében A szimbóluma, amint azt a 3.3. ábrán láthatjuk. található, ez lesz a rejtett szöveg elso

mot rendeljük hozzá. A Vigenère-négyzet

3.1. Alapok

99 k

T O N Y T O N Y T

O N Y T O N Y T O N Y T

m

H U N G A R I A N

I

S

A L L

G R E E K

T O G E R M A N S

O N Y T O N Y

c

A I A E T F V Y G W F

Y E Z

T P X S X

R H U R P F O A Q

használó sifrírozásra. 3.4. ábra. Példa a Vigenère-rejtjelezot

Még számos további klasszikus kriptorendszer létezik, amelyeket azonban itt nem vizs Több lehetoség gálunk meg közelebbrol. van arra is, hogy a kriptorendszereket jellegük és tulajdonságaik alapján osztályozzuk. A 3.1. deníció megvilágítja a szimmetrikus és az aszimmetrikus kriptorendszerek közötti különbséget. A két bemutatott szimmetrikus rend és a Vigenère-rejtjelezo) rámutat a monoalfabetikus és a polialszer (az eltolásos rejtjelezo helyettesítéses rejtjelezo. fabetikus rendszerek közötti eltérésekre. Mindketto Ezek szembeállíthatók a permutációs rejtjelezokkel (más néven transzpozíciós rejtjelezokkel), amelyeknél a nyílt szöveg betuit nem a rejtjelábécé bizonyos betui helyettesítenek, hanem csupán a szövegbeli helyük változik, egyébként azonban nem változnak meg. Ha blokkonként n periódussal rejtjelezünk és mazzuk kulcstérként, ahol

Σ

Σn összes permutációinak halmazát alkaln

lehetoségünk m betus ábécé, akkor m ! különbözo van arra,

hogy egy kulcsot kiválasszunk. Továbbá a blokkrejtjelezot amelyben, mint a Vigenèrerendszer esetén a nyílt szöveget blokkokra osztjuk, blokkonként rejtjelezzük , egybevethetjük a folyamrejtjelekkel, amelyek egy folyamatos kulcsfolyamot hoznak létre. A blokkrejt különbözo változatait vizsgálhatjuk. Egy fontos típust képviselnek az affin blokkjelezok rejtjelezok. Ezeket a következoképpen deniáljuk: az E D

(A−1 ,~ b)

függvények visszafejto

n Zm -be Znm -bol

(A,~ b)

függvények, és a rejtjelezo

képeznek, és affin leképezések, ami azt je-

lenti, hogy az alábbi alakúak: E

(A,~ b)

D

(~ x)

(A−1 ,~ b)

Itt (A, ~ b) és (A elemekkel. A

−1

−1

, ~b)

(~ y)

= =

A~ x A

+ ~b mod m ,

−1

(~ y

(3.2)

− ~b) mod m . × n)-es mátrix Zm -beli Znm -beli vektorok, a muveleteket pedig

a rejtjelezés illetve visszafejtés kulcsai; A (n

az A inverz mátrixa; ~ x, ~ y és ~ b mind

modulo m végezzük. Nézzünk néhány matematikai kiegészítést (lásd a 3.1.3. pontban a 3.2.

Zm gyur u fölötti (n × n)-es A mátrixnak pontosan akkor van multip= 1. A inverz mátrixát A−1 = (det A)−1 Aadj segítségével i+ j deniáljuk, ahol det A az A determinánsa és Aadj = ((−1) det A j,i ) az A adjungált mátrixa. A det A determinánsát rekurzív módon deniáljuk: n = 1 és A = (a) esetén det A = a; Pn i+ j n > 1 esetén minden i-re, ahol i ∈ {1, 2, . . . , n}, det A = (−1) ai, j det Ai, j , ahol ai, j az j=1 A-nak az (i, j) indexu eleme és az (n − 1) × (n − 1)-es Ai, j mátrixokat az A-ból úgy kapjuk, deníciót is): egy a

likatív inverze, ha lnko(det A, m)

hogy az i-edik sort és a j-edik oszlopot törüljük. Egy mátrix determinánsát hatékonyan ki lehet számítani (lásd a 3-3. feladatot). affin rejtjelezo, amelynek kulcstere, Példaként megemlítjük, hogy a Vigenère-rejtjelezo

K = Znm

b nullvektor, akkor lineáris pontosan m elemu (lásd a 3.2. példát). Ha (3.2)-ben a ~ n

blokkrejtjelezor ol van szó. Erre klasszikus példa a Hill-rejtjelezo, amit 1929-ben Lester Hill

× n)-es Zm -beli elemeket tartal= 1. Emiatt a kulcsként megengedett mátrixok inver-

talált ki. Ennél a rejtjelezonél a kulcstér az összes olyan (n mazó A mátrix, melyre lnko(det A, m) tálhatók, s az A

−1

inverz mátrixszal fejthetjük vissza az A mátrixszal rejtjelezett üzenetet.

az E A (~ A Hill-rejtjelezot x)

=

függvénnyel és a DA−1 (~ A~ x mod m rejtjelezo y)

= A~y mod m

100


függvénnyel deniáljuk. Ez a legáltalánosabb lineáris rejtjelezo. A permutációs visszafejto szintén lineáris rejtjelezok, speciális esetei. rejtjelezok és így a Hill-rejtjelezok

3.1.2. Kriptoanalízis A kriptoanalízis feladata az, hogy adott kriptorendszereket feltörjön, elsosorban azért, hogy a szükséges kulcsot a visszafejtéshez megállapítsa. Attól függoen, hogy milyen információk állnak a kriptoanalízis rendelkezésére, a támadások több típusát lehet megkülönböztetni, és ezzel a vizsgált kriptorendszer biztonságát, illetve sérülékenységét jellemezni. Az eltolásos rejtjelezovel kapcsolatban már említettük a rejtett szövegu támadást. Ez a leggyengébb formája a támadásnak, és az a kriptorendszer, amelyik ennek a támadásnak sem áll ellen, nem sokat ér. érzékenyek az Az affin blokkrejtjelezok, mint például a Vigenère- és a Hill-rejtjelezok olyan támadásokra, amelyeknél a támadó egy elcsípett rejtjelezett szöveget és a hozzátar az alkalmazott kulcsra tozó nyílt szöveget is ismeri (ismert nyílt szövegu támadás), és ebbol következtetni tud. Még inkább érzékenyek az olyan támadásokra, amelyeknél a támadó saját maga ki tud választani egy nyílt szöveget, és utána látja, hogy milyen rejtett szöveg tartozik hozzá (választott nyílt szövegu támadás. A negyedik fajta támadás foként az aszimmetrikus kriptorendszerekre hatásos. Az ilyen rejtjelezo kulcs támadás, encryption-key-attacks esetén a támadó csupán a nyilvánosságra hozott kulcsot ismeri, de nem ismer rejtett üzene az információból próbálja meghatározni a titkos kulcsot. A különbség tet, és egyedül ebbol az, hogy a támadónak van ideje számításokat végezni, a többi támadás esetén azonban sietnie kell, mert az üzenetet már elküldték. Ezért kell aszimmetrikus kriptorendszerek esetén a kulcsteret nagynak választani, s ezzel szavatolni a rendszer biztonságát. Ennek következménye az, hogy a gyakorlatban sokszor kevéssé hatékonyak az aszimmetrikus rendszerek. Az ilyen támadások gyakran a rejtjelezett szövegben eloforduló betuk gyakoriságát vizsgálják. Emellett a nyílt szöveg számára alkalmazott természetes nyelv redundanciáját is kihasználják. Például sok természetes nyelvben az

E betu statisztikusan szignikáns tipikus szövegek vizsgálata szerint az E gyakorisága az angolban 12.31%, a franciában 15.87%, a németben pedig 18.46%. Más

Hosszú módon a leggyakrabban fordul elo.

nyelvekben más betuk léphetnek fel a legnagyobb gyakorisággal.

Tipikus nn szövegek A a leggyakoribb betu. A gyakoriságelemzés szemmel láthatóan hasznos a monoalfabetikus kriptorendszerek

ben például 12.06%-kal az

elleni támadás során. Ha például egy eltolásos rejtjelezovel rejtett német szövegben az

Y betu lép fel leggyakrabban, ami a németben akárcsak a legtöbb nyelvben ritka, akkor

arra következtethetünk, hogy ez az E rejtett változata, az alkalmazott kulcs pedig az ebbol U (k = 20) (lásd a 3.3. ábrát). Az egyes betuk gyakorisága mellett vizsgálhatjuk a betupá rok (digrammok), a betuhármasok (trigrammok) stb. A támadásnak ez a módja muködik a polialfabetikus kriptorendszerek esetében is, feltéve, hogy a periódus (vagyis a blokkhossz) ismert. Az ismeretlen periódusú polialfabetikus kriptorendszerek ezzel szemben nagyobb biz például hosszú ideig ellenállt minden feltörési tonságot nyújtanak. A Vigenère-rejtjelezo kísérletnek. Csak 1863-ban, mintegy 300 évvel a feltalálása után, talált módszert Friedrich feltörésére. Megmutatta, hoWilhelm Kasiski német kriproanalitikus a Vigenère-rejtjelezo gyan lehet meghatározni az alkalmazott periódust a kulcsszöveg szavainak ismétlodéséb ol akkor is, ha a periódus kezdetben ismeretlen volt. Végül a gyakoriságelemzés segítségével a

3.1. Alapok

101

Singh írja, hogy a rendkívül sokoldalú Charles Babbage, rejtjelezett szöveg visszafejtheto. akit sokan kora zsenijének tartanak, a Kasiski-féle módszert valószínuleg korábban,1854ben felfedezte, bár nem hozta nyilvánosságra. A kriptográa történetében mérföldkoként kell megemlítenünk Claude Shannonnak munkáját. Shannon be(19162001). a modern kód- és információelmélet atyjának úttöro bizonyította, hogy vannak kriptorendszerek, amelyek egy bizonyos szigorú matematikai ér telemben tökéletes titkosságot tesznek lehetové. Pontosabban szólva egy kriptorendszer ak-

|C| = |K|, a kulcsok K -ban egyenletes eloszlásúak, és minden ∈ C-re pontosan egy k ∈ K kulcs van, amelyre Ek ( p) = c. Ez azt

kor tökéletes titkosságú, ha p

∈ P-re

és minden c

jelenti, hogy egy ilyen kriptorendszer a legtöbb gyakorlati célra nem használható, mert ahhoz, hogy tökéletes titkosságot garantálhassunk, egyrészt minden kulcsnak legalább olyan üzenet, másrészt egyszeri használat után minden hosszúnak kell lennie, mint a rejtjelezendo kriptorendszereket késobb kulcsot el kell dobni. Gyakorlati célra megfelelo fogunk ebben a fejezetben bemutatni.

3.1.3. Algebra, számelmélet és gráfelmélet algoritmusok és problémák közül néhánynak a megértéséhez seA késobb sorra kerülo néhány alapveto gítségünkre lesz az algebra, és foként a csoport- és számelmélet körébol fogalom és tétel. Vonatkozik ez mind a 3. fejezetbeli kriptorendszerekre és zéró-ismeretu protokollokra, mind pedig néhány, a 4. fejezetben vizsgált problémára. Az Olvasó megteheti, hogy ezt a pontot átugorja, és a szükséges fogalmaknak, eredményeknek csak akkor néz utána, ha késobb felbukkannak. A bizonyításoktól ebben a fejezetben többnyire eltekintünk. 3.2. deníció (csoport, gyur u, test).

•

G=

(S , ◦) csoport, ha S nem üres halmaz,

◦ kétváltozós muvelet S -en és teljesülnek a

következo axiómák:

zártság: (∀ x

asszociativitás: (∀ x

∈ S ) (∀y ∈ S ) [x ◦ y ∈ S ]; ∈ S ) (∀y ∈ S ) (∀z ∈ S ) [(x ◦ y) ◦ z = x ◦ (y ◦ z)]; semleges elem: (∃e ∈ S ) (∀ x ∈ S ) [e ◦ x = x ◦ e = x]; −1 inverz elem: (∀ x ∈ S ) (∃ x ∈ S ) [x ◦ x−1 = x−1 ◦ x = e].

G csoport semleges elemének, az x−1 elemet x inverzének nevezzük. G G-ben az asszociativitás és a zártság teljesül a ◦ muveletre, akkor is, ha G-nek nincs semleges eleme, vagy nem minden elemnek van inverze. Egy G = (S , ◦) félcsoport, vagy csoport kommutatív, ha x ◦ y = y ◦ x minden x, y ∈ S esetén teljesül. Egy G véges csoport elemeinek a száma a G rendje és ezt |G| jelöli. H = (T , ◦)-t a G = (S , ◦) csoport részcsoportjának nevezzük (H ≤ G jelöli), ha T ⊆ S és H kielégíti a csoportaxiómákat. Egy R = (S , +, ·) hármas gyur u, ha (S , +) Abel-csoport, (S , ·) félcsoport és a disztribuAz e elemet a

félcsoport, ha

• •

tivitási szabály érvényben van: (∀ x

∈ S ) (∀y ∈ S ) (∀z ∈ S ) [(x · (y + z) = (x · y) + (x · z)) ∧ ((x + y) · z = (x · z) + (y · z))].

Egy

R=

(S , +, ·) gyur u kommutatív, ha az (S , ·) félcsoport kommutatív. Az (S , +) cso-

port semleges elemét (ha létezik) az

R gyur u nullelemének (röviden nullának), az (S , ·)

102

3. Kriptográfia (Jörg Rothe) félcsoport semleges elemét az

•

Legyen

R =

(S , +, ·) egységelemes gyur u.

invertálhatónak (vagy

R valamely · y = y · x = 0.

ható. x

•

R gyur u egységelemének (röviden egy) nevezzük.

R

R

egy x elemét pontosan akkor nevezzük

egységének), ha ez az elem az (S , ·) félcsoportban invertál-

x eleme nullosztó, ha nem nulla, és egy

R-beli nem nulla y elemmel

Test egy kommutatív, egységelemes gyur u, amelyben minden, a nullától különbözo elem invertálható.

3.3. példa.

<

Csoport, gyur u, test. Legyen 1

k

∈ N.

A

Zk = {0, 1, . . . , k − 1}

halmaz az egész

számok modulo k tekintett összeadásával véges csoport, amiben semleges elem a 0.

Zk

a modulo k

vett összeadással és szorzással kommutatív egységelemes gyur u (lásd a 3. 3-1. feladatot). Abban az

Z p a modulo k tekintett összeadásra és szorzásra test. ∗ Legyen lnko(n, m) az n és m számok legnagyobb közös osztója. Legyen 1 < k ∈ N esetén Zk = {i 1 ≤ i ≤ k és lnko(i, k) = 1}. A számok modulo k vett szorzásával Z∗k véges csoport az 1 semleges

esetben, ha p prímszám, akkor

elemmel.

egyértelmuen Ha a szövegösszefüggésbol kiderül, hogy valamely G a

◦

= (S , ◦) csoportban Z∗k csoport

a muvelet, akkor nem szükséges explicit módon megadni. A 3.3. példabeli

fontos szerepet játszik a 3.3. alfejezetben, ahol az RSA kriptorendszert mutatjuk be. Ennek a csoportnak a rendjét az Euler-féle

ϕ

függvény adja meg, vagyis

ϕ(k) = |Z∗k |. ϕ

alábbi

tulajdonságai a deníció következményei:

•

ϕ(m · n) = ϕ(m) · ϕ(n) minden m, n ∈ N esetén, ha lnko(m, n) = 1 és

•

ϕ( p) =

p

− 1 minden

p prímszámra.

Ezeknek a tulajdonságoknak a bizonyítását az Olvasóra hagyjuk (lásd a 3.1-3. gyakorlatot). a tulajdonságokból Foként a 3.3.1. pontban használjuk az alábbi állítást, amely ezekbol közvetlenül következik. 3.3. állítás. Ha n

=

p

· q, ahol

p és q különbözo prímszámok, akkor

ϕ(n) = ( p − 1)(q − 1).

G csoport minden a elemére és az e = e összefüggés, ahol |G| a csoport rendjét jelöli. Az alábbi, ∗ úgynevezett Euler-tétel ennek speciális esete (a Zn csoportra). Az Euler-tétel speciális esete A Lagrange-tétel szerint egy véges, multiplikatív

|G|

semleges elemre fennáll az a

pedig, ha n prímszám, és a-nak nem osztója, 3.4. tétel (Euler). Minden a

∈ Z∗n

ϕ(n)

esetén a

kis Fermat-tételként lett ismert.

≡ 1 mod n.

3.5. következmény (kis Fermat-tétel). Ha p prímszám és a

∈ Z∗p , akkor a p−1 ≡ 1 mod

p.

A 4.4. alfejezetben grázomorzmus problémára mutatunk algoritmusokat. Ez a probléma, amely a 3.5.2. pontban található zéró-ismeretu protokollnál fontos szerepet játszik, bizonyos csoportelméleti problémák speciális eseteként is felfogható. Különösen fontosak itt a permutációcsoportok. 3.6. deníció (permutációcsoport).

3.1. Alapok •

103 ≥ 1 természetes = {1, 2, . . . , n}. Az [n] összes permutációinak halmazát Sn jelöli. a π ∈ Sn permutációt n darab [n] × [n]-beli (i, π(i)) rendezett

Egy permutáció valamely halmaz bijektív leképezése önmagára. Egy n szám esetén legyen [n] Algoritmikus célokra

párból álló listával reprezentáljuk.

•

Sn -en permutációk kompozíciójaként deniálunk egy muveletet, akkor Sn csoport π és τ Sn -beli permutációk, akkor πτ kompozíciójuk az az Sn -beli permutáció, amelyet úgy kapunk, hogy eloször π-t, azután τ-t alkalmazzuk [n] elemeire, tehát (πτ)(i) = τ(π(i)) minden i ∈ [n] esetén. Az Sn permutációcsoport semleges eleme az identikus permutáció, amelyet a következoképpen deniálunk: id(i) = i minden i ∈ [n] esetén. Sn -nek azt a részcsoportját, amely csupán az id elemet tartalmazza, id jelöli. Ha

lesz. Ha

•

Sn -nek valamely T részhalmaza esetén a T által generált hTi permutációcsoportot Sn T-t tartalmazza. Az Sn valamely G részcsoportját az ot generáló halmazzal reprezentáljuk, amelyet G generátorrendszerének is nevezzük. G-ben valamely i ∈ [n] elem pályáját G(i) = {π(i) | π ∈ G} legszukebb olyan részcsoportjaként deniáljuk, amely

deniálja.

•

[n] valamely T részhalmaza esetén elemét önmagára képezi. Ha i

≤

STn

n és

Sn -nek az a részcsoportja, amelyik T minden Sn részcsoportja G, akkor [i] G-beli (ponton-

az

kénti) stabilizátorát az alábbi módon deniáljuk:

G(i) = {π ∈ G | π( j) = A

•

∈ [i] esetén} .

G(n) = id és G(0) = G összefüggések fennállnak.

Legyenek

H

j minden j

G

és

H

permutációcsoportok, és

jobb oldali mellékosztálya

vagy diszjunkt. Emiatt a

G

G-ben. H

H ≤ G. τ ∈ G

esetén

Hτ = {πτ | π ∈ H} G-ben azonos,

két jobb oldali mellékosztálya

permutációcsoportot

H G-beli

jobb oldali mellékosztályai

osztályozzák:

G = Hτ1 ∪ Hτ2 ∪ · · · ∪ Hτk .

(3.3)

H mindegyik G-beli jobb oldali mellékosztályának a számossága |H|. A {τ1 , τ2 , . . . , τk } (3.3) halmazt H G-beli jobb oldali reprezentánsrendszerének nevezzük. A pontonkénti stabilizátor fogalma különösen fontos olyan algoritmusok tervezésénél, amelyek permutációcsoportokkal dolgoznak. Az a lényeges struktúra, amelyet ilyenkor használunk azt úgy nevezzük, hogy id

G permutációcsoportbeli stabilizátor lánc:

= G(n) ≤ G(n−1) ≤ · · · ≤ G(1) ≤ G(0) = G .

G(i) -nek G(i−1) -ben teljes jobb oldali reprezenSn−1 tánsrendszere. Ekkor azt mondjuk, hogy T = generátora G-nek, és G = hTi. Ti eros i= 1 Ekkor minden π ∈ G egyértelmuen faktorizálható π = τ1 τ2 · · · τn alakban, ahol τi ∈ Ti . A Minden i-re 1

≤

i

≤

n esetén legyen

Ti

a

permutációcsoportokra vonatkozó alábbi algoritmuselméleti eredmények hasznosak lesz nek késobb, a 4.4. alfejezetben. 3.7. tétel. Ha a következo:

G ≤ Sn

permutációcsoport a generátorrendszerével adott, akkor fennáll a

104


1.

Minden i

2.

Az id

∈ [n] esetén i G(i) pályája G-ben polinomiális ido alatt kiszámítható.

= G(n) ≤ G(n−1) ≤ · · · ≤ G(1) ≤ G(0) = G

stabilizátorlánc kiszámítható n-ben

polinomido alatt, ami azt jelenti, hogy meghatározzuk minden i, 1 teljes jobb oldali reprezentánsrendszerét

Ti -t G

(i−1)

-ben és ezzel

≤

i

≤

n esetén

G(i)

G egy eros generátor-

rendszerét.

Azokat a fogalmakat, amelyeket a 3.6. denícióban vezettünk be a permutációcsoporttal vett konkrét példák alapján fogjuk megvilágítani. Elso kapcsolatban, most a gráfelméletbol sorban gráfok automorzmuscsoportját és izomorzmuscsoportját vizsgáljuk. Ehhez szükségünk lesz néhány gráfelméleti fogalomra. 3.8. deníció (gráfok izomorzmusa és automorzmusa). Egy G gráf egy véges V (G) csúcshalmazból, és egy véges E(G) élhalmazból áll, melyben lévo élek bizonyos csúcsokat összekötnek egymással. Feltesszük, hogy nincsenek párhuzamos- és hurokélek. Ebben az alfejezetben kizárólag irányítatlan gráfokat vizsgálunk, ami azt jelenti, hogy az éleknek nincs irányításuk és rendezetlen csúcspárokként foghatjuk fel oket. Két gráf, G és H, diszjunkt egyesítését, G ∪ H-t, amelyek V (G) és V (H) csúcshalmazai átnevezéssel diszjunkttá tehetok, a V (G)

∪ V (H) csúcshalmazzal és az E(G) ∪ E(H) élhalmazzal deniáljuk.

Legyen G és H két gráf ugyanannyi csúccsal. G és H közötti izomorzmus G csúcshalmazáról H csúcshalmazára képezo éltartó bijekció. Állapodjunk meg abban, hogy V (G)

{1, 2, . . . , n} = V (H). Ekkor tehát G és H pontosan akkor izomorf (röviden G olyan π ∈ Sn permutáció, hogy minden i, j ∈ V (G) csúcsra fennáll a következo: { i, j} ∈

E(G)

⇐⇒ {π(i), π( j)} ∈

E(H)

=

H), ha van

.

(3.4)

G egy automorzmusa G csúcshalmazának önmagára való éltartó bijekciója. Minden gráf esetén fennáll az id triviális automorzmus. Jelöljük Iso(G , H)-val a G és H közötti összes izomorzmus halmazát, Aut(G)-vel pedig G összes automorzmusának halmazát. A gráfizomorzmus problémát (röviden

GI)

és a gráfautomorzmus problémát (röviden

GA)

a

következo módon deniáljuk:

GI = {(G, H) | G és H izomorf gráfok} ; GA = {G | G tartalmaz nem triviális automorzmust} . Algoritmikus célokra a gráfokat vagy csúcs- és él-listájukkal, vagy csúcsmátrixukkal reprezentáljuk, amelyben az (i, j) helyen 1 áll, ha {i, j} egy él a gráfban, különben pedig 0. Valamely gráfnak ehhez az eloállításához elegendo a

Σ = {0, 1}

ábécével való kódolás. Ha

gráfpárokat kívánunk szemléltetni, akkor olyan bijektív párosítási (·, ·) függvényt alkalmazunk, amely

Σ∗ × Σ∗ -ról Σ∗ -ra képez, polinomiális idoben kiszámítható, és van polinomiális

idoben kiszámítható inverze.

3.4. példa. (Gráfok izomorzmusa és automorzmusa.) A 3.5. ábrán látható G és H gráfok izomorfak. Egy

π

: V (G)

→

V (H) izomorzmus, amelynél (3.4)-nek megfeleloen adjuk meg a csúcsok

módon: szomszédosságát, megadható például a következo

π=

π =

1 2 3 4 5

(3

4 1 5 2

), illetve ciklikus módon írva

(1 3)(2 4 5). G és H között van még három további izomorzmus, és így |Iso(G , H)|

=

4, (lásd a

3.1-4. gyakorlatot). G és H azonban nem izomorfak F-fel. Ez azonnal látható, ha a fokszámok soro élek számát). A G-hez, illetve H-hoz zatát nézzük (vagyis minden csúcs esetén a csúcsra illeszkedo

3.1. Alapok

105 F

1

2

3

5

4 G

H

5

3

2

1

4 3

1

2

5

4

3.5. ábra. A három gráf: G és H izomorfak, de F nem izomorf velük.

tartozó sorozat különbözik az F-hez tartozótól: G és H esetén ez a sorozat (2, 3, 3, 4, 4), miközben F esetén (3, 3, 3, 3, 4). G egy nem triviális

ϕ

: V (G)

→

ϕ=( ), il) illetve τ = (1)(2)(3 4)(5)

V (G) automorzmusa például

1 2 3 4 5 2 1 4 3 5

ϕ = (1 2)(3 4)(5) segítségével adható meg, egy másik pedig τ = ( segítségével. G-nek van még két további automorzmusa és így |Aut(G)| = 4 (lásd a 3.1-4. gyakorla1 2 3 4 5

letve

1 2 4 3 5

tot). Az Iso(G , H), Aut(F), Aut(G) és Aut(H) permutációcsoportok

S5 részcsoportjai. Aut(G)-ben az ≤ · · · ≤ Aut(G)(1) ≤ Aut(G)(0) stabilizátorlánc az Aut(G)(5) = Aut(G)(4) = (3) (2) Aut(G) id, Aut(G) = Aut(G)(1) = h{id, τ}i és Aut(G)(0) = Aut(G) részcsoportokból áll. G automorzmuscsoportjában, Aut(G)-ben az 1 és 2 csúcsok pályája {1, 2}, a 3 és 4 csúcsok pályája {3, 4}, és az 5 pályája {5}. Aut(G)

(5)

≤ =

Aut(G)

(4)

Az Iso(G , H) és Aut(G) permutációcsoportok rendje pontosan akkor azonos, ha G és H izomorfak. Ha ugyanis G és H izomorfak, akkor |Iso(G , H)| hogy Aut(G)

=

Iso(G , G). Másrészt ha G

= |Aut(G)|

következik abból,

H, akkor Iso(G , H) üres, ugyanakkor Aut(G)-

következik a 3.9. lemma (3.5) ben mindig benne van az id triviális automorzmus. Ebbol állítása, amire késobb a 4.4. alfejezetben szükségünk lesz. A (3.6) igazolására tegyük fel, esetben G illetve H helyett a G illetve H komplemenhogy G és H összefüggoek; ellenkezo ter gráfokat tekintjük, (lásd a 3.1-5. gyakorlatban). G

∪

H egy automorzmusa, amely G

és H csúcsait felcseréli, egy Iso(G , H)-beli és egy Iso(H, G)-beli izomorzmusból tevodik össze. Így |Aut(G

(3.5) felhasználásával ∪ H)| = |Aut(G)| · |Aut(H)| + |Iso(G, H)|2 , amibol

következik (3.6). 3.9. lemma. Bármely két G és H gráf esetén fennállnak a következok:

(

|Iso(G, H)| = ( |Aut(G ∪ H)| =

|Aut(G)| = |Aut(H)|, 0, · |Aut(G)| · |Aut(H)|, |Aut(G)| · |Aut(H)|, 2

ha G ha G

ha G ha G

H

(3.5)

H ;

H H

.

(3.6)

106

3. Kriptográfia (Jörg Rothe) Ha G és H izomorf gráfok, és

τ ∈

Iso(G , H), akkor Iso(G , H)

lenti, hogy Iso(G , H) Aut(G)-nek jobb oldali mellékosztálya mellékosztály azonos, vagy diszjunkt,

= Aut(G)τ. Ez azt jeSn -ben. Mivel két jobb oldali

Sn (3.3) szerint Aut(G) jobb oldali mellékosztályaira

bomlik:

Sn = Aut(G)τ1 ∪ Aut(G)τ2 ∪ · · · ∪ Aut(G)τk ,

(3.7)

ahol |Aut(G)τi |

= |Aut(G)| minden i, 1 ≤ i ≤ k esetén. Ezek szerint az Sn permutációiból {τ1 , τ2 , . . . , τk } halmaz Aut(G)-nek Sn -beli jobb oldali reprezentánsrendszerét alkotja. Ha π(G) azt a H G gráfot jelöli, amelyet akkor kapunk, ha a π ∈ Sn permutációt G csúcsaira alkalmazzuk, akkor {τi (G) | 1 ≤ i ≤ k} = { H | H G }. Mivel Sn -ben pontosan következik: n! = n(n − 1) · · · 2 · 1 permutáció van, (3.7)-bol álló

|{H | H G}| = k =

|Sn | n! = . |Aut(G)| |Aut(G)|

Ezzel beláttuk az alábbi következményt. 3.10. következmény. Ha a G gráfnak n csúcsa van, akkor pontosan n!/|Aut(G)| vele izomorf gráf van. G gráffal így pontosan 5!/4 A 3.4. példa 3.5. ábráján lévo

=

30 gráf izomorf. A következo

lemmára késobb, a 4.4. alfejezetben lesz szükségünk. 3.11. lemma. Legyenek G és H n csúcsú gráfok. Deniáljuk az alábbi halmazt: A(G , H)

=

{(F, ϕ) | F G és ϕ ∈ Aut(F)} ∪ {(F, ϕ) | F

H és

ϕ ∈ Aut(F)}.

Ekkor fennáll a következo:

( |A(G, H)| =

n!,

ha G

2n!,

ha G

Bizonyítás. Ha F és G izomorfak, akkor |Aut(F)|

H H.

= |Aut(G)|.

A 3.10. következménybol

adódik, hogy

|{(F, ϕ) | F G és ϕ ∈ Aut(F)}| = és hasonlóan megmutatható az is, hogy

|{(F, ϕ) |

n!

|Aut(F)| F

H és

· |Aut(F)| = n!, ϕ ∈ Aut(F)}| =

n!. Ha G és H

izomorfak, akkor

{(F, ϕ) | F G és ϕ ∈ Aut(F)}

= {(F, ϕ) | F

H és

ϕ ∈ Aut(F)} .

következik, hogy | A(G , H)| = n!. Ha pedig G és H nem izomorfak, akkor Ebbol {(F, ϕ) | F G és ϕ ∈ Aut(F)} és {(F, ϕ) | F H és ϕ ∈ Aut(F)} diszjunkt halmazok. Eszerint | A(G , H)| = 2n!.

Gyakorlatok 3.1-1. A 3.6. ábrán láthatunk két elfogott rejtjelezett szöveget, c1 -et és c2 -t. Tudjuk, hogy

3.2. Kulcscsere Diffie és Hellman szerint

107

c1

W K L V V H Q W H Q F H L V H Q F U B S W H G E B F D H V D U V N H B

c2

N U O S J Y A Z E E W R O S V H P X Y G N R J B P W N K S R L F Q E P

3.6. ábra. Ugyanannak a nyílt szövegnek két rejtett változata a 3.1-1. gyakorlatban.

ugyanannak az m nyílt szövegnek a rejtett változata, és az egyik eltolásos rejtjelemindketto zovel, a másik pedig Vigenère-rejtjelezovel lett sifrírozva. Mindkét szöveget fejtsük vissza. módszernél egy Útmutatás. A visszafejtés után megállapítható, hogy az egyik rejtjelezo igaz, a másiknál egy hamis állítás adódik. Van esetleg értelme gyakorisági elemzést alkalmazni?

Z a szokásos összeadással és szorzással nullosztómentes gyur u. Z test? Mit mondhatunk az (N, +), (N, ·) és (N, +, ·) algebrai struktúrák tulajdonsága-

3.1-2. Mutassuk meg, hogy Vajon iról?

ϕ-függvény alábbi tulajdonságait: ϕ(m · n) = ϕ(m) · ϕ(n) minden m, n ∈ N esetén, ha lnko(m, n) = 1. b. ϕ( p) = p − 1 minden p prímszám esetén.

3.1-3. Bizonyítsuk be az Euler-féle a.

Ezeknek a tulajdonságoknak a segítségével bizonyítsuk be a 3.3. állítást. 3.1-4. Adottak az F, G és H gráfok a 3.5. ábrán. a. Határozzuk meg a G és H közötti összes izomorzmust. b. Határozzuk meg F, G és H összes automorzmusát. c. A G és H közötti melyik izomorzmus esetén lesz Iso(G , H) Aut(G)-nak jobb oldali mellékosztálya

S5 -ben,

vagyis melyik

τ ∈

Iso(G , H) esetén lesz Iso(G , H)

Határozzuk meg Aut(F), Aut(G) és Aut(H) jobb oldali reprezentánsrendszerét

= Aut(G)τ? S5 -ben.

d. Határozzuk meg F minden csúcsának pályáját Aut(F)-ben és H minden csúcsának pályáját Aut(H)-ban. e. Határozzuk meg az Aut(F)

≤ S5 és Aut(H) ≤ S5 részcsoportok stabilizátorláncát.

f. Hány 5 csúcsú gráf izomorf F-fel? 3.1-5. Valamely G gráf komplementer gráfját a következoképpen deniáljuk: a csúcshalmaza V (G)

= V (G), az élhalmaza pedig E(G) = {{i, j} | i, j ∈ V (G) és {i, j} <

E(G)}. Mutas-

suk meg, hogy: a. Aut(G)

= Aut(G). = Iso(G, H).

b. Iso(G , H)

ha G nem összefüggo. c. G összefüggo,

3.2. Kulcscsere Diffie és Hellman szerint Ebben az alfejezetben, valamint a következokben is szükségünk lesz a 3.1.3. pontban látott számelméleti alapfogalmakra. Elsosorban a 3.3. példabeli Euler-féle

Z∗k

multiplikatív csoportra és az

ϕ függvényre gondolunk; a maradékosztálygyur uk aritmetikáját a fejezet végén

fogjuk megvilágítani a 3-1. feladatban. A 3.7. ábra a kulcscserére vonatkozó DiffieHellman-protokollt mutatja. Ez a protokoll az r alapú, p modulusú moduláris exponenciális függvényen alapszik, ahol p prímszám és r primitív gyök modulo p. r 1

≤

d

< ϕ(n)

∈ Z∗n

primitív gyök modulo n, ha r

d

.

1 mod n minden d,

esetén. Egy r modulo n primitív gyök eloállítja az egész

Z∗n

csoportot, ami

108


Lépés

Aliz

Erik

Bob

1

Aliz és Bob megállapodnak egy nagy p prímszámban, és egy r modulo p primitív gyökben;

2

véletlenszeruen választ egy nagy, tit-

véletlenszeruen választ egy nagy, tit-

kos a számot, és kiszámítja a követkea α = r mod p zot:

kos b számot, és kiszámítja a követke-

p és r nyilvánosak

zot:

β = rb

mod p

α⇒

3

⇐β 4

kiszámítja kA

=β

a

mod p értékét

kiszámítja k B

= αb

mod p értékét

3.7. ábra. Diffie és Hellman szerinti kulcscserére vonatkozó protokoll.

Z∗n = {ri | 0 ≤ i < ϕ(n)}. Emlékeztetünk arra, hogy ha p prímszám, akkor a Z p multiplikatív csoport rendje ϕ( p) = p − 1. Z∗p -nak pontosan ϕ( p − 1) primitív gyöke van

azt jelenti, hogy

∗

(lásd a 3.2-1. gyakorlatot is). 3.5. példa. Nézzük

Z∗5 = {1, 2, 3, 4}-et.

Mivel

Z∗4 = {1, 3},

így

ϕ(4) =

2, tehát a modulo 5 primitív Z∗5 -ot,

gyökök száma 2, modulo 5 primitív gyökök a 2 és a 3, így mind 2 mind 3 eloállítja az egész mivel 0

2

0

3

= 1; = 1;

2

1

3

1

= 2; = 3;

2

2

3

2

= 4; ≡ 4 mod 5;

2

3

3

3

≡ 3 mod 5 ; ≡ 2 mod 5 .

Nem minden n számnak van modulo n primitív gyöke; a 8 a legkisebb ilyen példa. tudjuk, hogy valamely n számra pontosan akkor van modulo n Az elemi számelméletbol primitív gyök, ha n vagy {1, 2, 4}-nek eleme, vagy pedig n

=

k

q , illetve n

=

k

2q alakú, ahol

q páratlan prímszám.

3.12. deníció (diszkrét logaritmus). Legyen p prímszám és r egy modulo p primitív gyök. Az r alapú, p modulusú képez,

expr, p (a) =

r

a

expr, p

moduláris exponenciális függvényt, amely

mod p-vel deniáljuk. Az inverz függvényét diszkrét logaritmusnak

nevezzük, ez rögzített p és r esetén az logr

expr, p (a) mod

∗ Z p−1 -rol Z p -re

expr, p (a)

értéket a-ra képezi. Fennáll, hogy a

=

p.

A 3.7. ábra protokollja muködik, mert kA

= βa =

r

ba

=

r

ab

= αb =

k B miatt (modulo

p aritmetikával) Aliz valójában ugyanazt a kulcsot számolja ki, mint Bob. Ezt a kulcsot könnyen kiszámíthatják, mivel az

 ´ ´

expr, p

moduláris exponenciális függvény a M ´

algoritmussal hatékonyan meghatározható. Ezzel szemben Erik arra irányuló

törekvése, hogy a kulcsukat meghatározza, nehézségekbe ütközik, mert a diszkrét logaritmus igen nehéz problémának számít. Az

expr, p

moduláris exponenciális függvény így egy

lehetséges egyirányú függvény, olyan függvény, amelyik bár könnyen kiszámítható, de csak nehezen invertálható. Sajnos máig nem tudjuk, hogy van-e egyáltalán egyirányú függvény. S ami még inkább kár: jóllehet nem tudjuk, hogy van-e ilyen, a kriptográában az egyirányú függvények kulcsszerepet játszanak, mert sok kriptorendszer biztonsága azon a feltevésen alapszik, hogy egyirányú függvények valóban vannak.

3.2. Kulcscsere Diffie és Hellman szerint

109

M - ´ (a, b, m) ´ ´ 1

B m a modulus, b < m az alap és a a kitevo

2

a kitevot kettes számrendszerben: a állítsuk elo i

2

3

számoljuk ki egymás után a b

értékeket, ahol 0

=

a

4

számoljuk ki modulo m aritmetikával b

Qk

i=0

i

ai 2 , ahol ai

i

2

b

i+1

B ha beleszámoltuk a szorzatba b2 -t, és kiszámítottuk b2

6

return b a

=

=

i = 0 ai =1

2

b

i

2

i

kiszámítása helyes, mert a modulo m aritmetikában fennáll a követ-

a

b

Pk

=b

i=0

i

ai 2

=

k Y

2

b

i

a

i=0

Miért lehet hatékonyan kiszámítani az

i

=

k Y

2

b

i

.

i = 0 ai =1

expr, p (a) =

r

a

mod p hatványfüggvényt? Ha

mindegyik ezt a számítást naivan hajtjuk végre, sok szorzásra lehet szükségünk az a kitevo értékére. A M - ´ algoritmussal azonban Aliznak nem a ´ ´

− 1 szorzást kell

végeznie, mint a naiv módszernél, hanem csupán legfeljebb 2 log a szorzásra van szüksége. A M - ´ algoritmus egy exponenciális tényezovel gyorsítja a moduláris ´ ´ hatványozást. 3.6. példa. (M - ´ a DiffieHellman-protokollban.) Aliz és Bob a p ´ ´

= 5 prímszámot = 3-at, mint modulo 5 primitív gyököt választja. Aliz az a = 17 titkos számot választja. Mivel 17 Aliz Bobnak az α számot akarja küldeni, ki szeretné számítani az α = 3 = 129140163 ≡ 3 mod 5 0 4 bináris alakban felírva 17 = 1 + 16 = 2 + 2 . Aliz lépésenként számítja ki az értéket: számot. A kitevo és az r

2

3

0

= 3;

1

2

3

= 32 ≡ 4 mod 5; 17

kiszámítja a 3 Ebbol

≡

2

3

0

2

2

3

4

≡ 42 ≡ 1 mod 5;

· 32 ≡

3

·1 ≡

2

3

3

≡ 12 ≡ 1 mod 5;

4

2

3

≡ 12 ≡ 1 mod 5.

3 mod 5 értéket. Figyeljük meg, hogy Aliz ahelyett,

hogy 16-szor szorzott volna, csupán négyszer emelt négyzetre és egyszer szorzott határozása érdekében. Ha Bob saját magának a b

=

α=

3 mod 5 meg-

választja, akkor ugyanezzel az 23 titkos kitevot

β = 323 = 94143178827 ≡ 2 mod 5, végül 3.7. ábrán látható DiffieHellman-protokollal meghatározzák

részét, tehát eljárással ki tudja számítani a kulcs orá eso Aliz és Bob a közös titkos kulcsukat a

(lásd a 3.2-2. gyakorlatot). A protokoll biztonsága ebben az esetben természetesen nincs garantálva, hiszen p

=

5-tel nagyon kicsi prímszámot választottak; ez a játékpélda csak a könnyebb megértést

szolgálja.

Ha Erik gyelmesen lehallgatja Aliz és Bob társalgását, amely a 3.7. ábra szerinti DiffieHellman-protokoll szerint zajlik, akkor ismeri a p, r, szeretné meghatározni a kA bol

=

α

és

β

értékeket, amelyek-

k B titkos kulcsukat. Eriknek ezt a problémáját Diffie

= logr α mod p és = logr β mod p titkos számokat, akkor, akárcsak Aliz és Bob, ki tudná számolni a = βa mod p = αb mod p = kB kulcsot, és megoldaná a DiffieHellman-problémát. Ez

Hellman-problémának nevezik. Ha Erik meg tudná határozni az a a b kA

a probléma tehát nem nehezebb, mint a diszkrét logaritmus problémája. A fordított kérdés, hogy vajon a DiffieHellman-probléma legalább olyan nehéz-e, mint a diszkrét logaritmusé, tehát hogy ugyanolyan nehezek-e, ez máig csupán nem bizonyított sejtés. Mint sok

2

b

-t, akkor b -t kitörölhetjük

a

Qk

kezo:

i+1

értékét.

5

A b

∈ {0, 1}.

≤ i ≤ k, felhasználva, hogy b2

i = 0 ai =1

i

Pk

=

i

2

.

110


más protokoll, a DiffieHellman-protokoll biztonságossága mindezidáig nem bizonyított. Mivel szerencsére eddig sem a diszkrét logaritmus, sem a DiffieHellman-probléma hatékonyan nem oldható meg, ez a közvetlen támadás nem jelent valóságos veszélyt. Másrészt azonban vannak más, nem közvetlen támadások, amelyeknél a kulcsot nem közvetlenül a DiffieHellman-protokollban átadott

α,

illetve

β

határozzák meg. Így értékekbol

például a DiffieHellman nem biztonságos a középen állás támadással szemben. A fent leírt támadás passzív, ez pedig aktív abban az értelemben, hogy a támadó Erik nem elégszik meg a passzív hallgatózással, hanem megpróbálja a protokollt aktívan a saját ízlésé nek megfeleloen megváltoztatni. Úgyszólván beáll

α = ra mod p, és αE = rc mod p értékét

Aliz Bobnak küldött

középre, Aliz és Bob közé és elfogja b Bob Aliznak küldött β = r mod p üzenetét. α

β helyett saját továbbítja Bobnak, Aliznak pedig a szintén saját βE = rd mod p értéket, miközben Erik a titkos c és d értékeket maga választotta. Ha most a Aliz a kA = (βE ) mod p értéket kiszámítja, kA valójában ezentúl nem a Bobbal mint és

ahogy azt Aliz hiszi , hanem az Erikkel való kommunikáció kulcsa, mert Erik ezt a kulcsot (modulo p aritmetikával): kE ugyanúgy értékeli ki, mint ok

= αd =

r

ad

=

r

da

= (βE )a =

kA

segítségével. Ugyanígy lefolytathat Erik egy észrevehetetlen kulcscserét Bobbal, és a jö voben vele kommunikálhat anélkül, hogy ezt Bob sejtené. A hitelességnek ezzel a problé májával késobb fogunk alaposabban foglalkozni a zéró-ismeretu protokollokról szóló 3.5. alfejezetben.

Gyakorlatok

Z∗13 -ban, illetve Z∗14 -ban? ∗ valamint Z14 összes primitív gyökét,

3.2-1. a. Hány primitív gyök van b. Határozzuk meg

∗

Z13

és bizonyítsuk be, hogy

ezek valóban primitív gyökök. hogy a teljes c. Mutassuk meg az összes modulo 13, illetve modulo 14 primitív gyökrol, Z∗13 -ot, illetve a teljes Z∗14 -ot eloállítják. 23 3.2-2. a. Határozzuk meg a β = 3 = 94143178827 ≡ 2 mod 5 értéket (Bob 3.6. példabeli értékét) a M - ´ algoritmussal. ´ ´ b. Határozzuk meg a 3.6. példában az α és β számokhoz Aliz és Bob közös titkos kulcsát DiffieHellman-protokoll szerint. a 3.7. ábrán lévo

3.3. RSA és faktorizálás 3.3.1. RSA Az RSA-kriptorendszer, amelyet három feltalálójáról, Ron Rivest, Adi Shamir és Leonard ismert nyilvános kulcsú kriptorendszer. Manapság is igen Adleman-ról neveztek el, az elso népszeru, és sok kriptográai alkalmazásba beillesztik. A 3.8. ábrán összefoglaltuk az RSA protokoll egyes lépéseit, amelyeket végül részletesen is leírunk, valamint lásd a 3.7. példát. Kulcsgenerálás. Bob választ véletlenszeruen két nagy prímszámot, p-t és q-t úgy, hogy p

,

q, és kiszámítja n

=

pq szorzatukat. Azután választ egy e

∈ N

az alábbiak kitevot

szerint

1

< e < ϕ(n) = ( p − 1)(q − 1)

és

lnko(e, ϕ(n))

=1,

(3.8)

3.3. RSA és faktorizálás Lépés

111

Aliz

Erik

Bob

1

Véletlenszeruen választ két nagy prímszámot, p-t és q-t és kiszámítja az n

=

pq és

ϕ(n) =

(p

− 1)(q − 1)

értékeket, nyilvános (n, e) kulcsát, és d titkos kulcsát, amelyek megfelelnek (3.8) és (3.9)-nek

⇐ (n, e)

2 3

c

=

e

m

mod n szerint

rejtjelezi m-et 4

c

⇒

5

visszafejti c-t m

= cd

mod n szerint

3.8. ábra. Az RSA-protokoll.

majd meghatározza e mod 1

ϕ(n) inverzét, vagyis azt az egyértelmu d számot, amelyre: < d < ϕ(n)

és

e

· d ≡ 1 mod ϕ(n).

(3.9)

Az (n, e) pár Bob nyilvános kulcsa, d pedig Bob titkos kulcsa. Rejtjelezés. Mint már a 3.1. alfejezetben is, az üzenetek egy blokkonként, állandó hosszúságú blokkhosszal

|Σ|-adikus

Σ

ábécé feletti szavak és

természetes számokként kódol-

juk oket. Ezeket a számokat azután rejtjelezzük. Legyen m

<

n az üzenet egyik rejtjelezett

szám, amelyet Aliz szeretne Bobnak küldeni. Aliz ismeri Bob nyilblokkjának megfelelo vános (n, e) kulcsát, és m-et rejtjelezi c

=

függvény E (n,e) (m) számként, ahol a rejtjelezo

deníciója az alábbi: E (n,e) (m) Visszafejtés. Legyen c, 0

≤

c

<

= me

mod n

.

n az a szám, amely a rejtjelezett szöveg egyik blokk-

jának kódja, amelyet Bob megkap, Erik pedig lehallgatja. Bob desifrírozza c-t a d titkos függvény segítségével: kulcsa és az alábbi visszafejto Dd (c)

= cd

mod n

.

Azt, hogy az RSA-módszer valóban kriptorendszer a 3.1. deníció értelmében, a 3.13. tétel állítja. Ennek a tételnek a bizonyítását az Olvasóra hagyjuk (lásd a 3.3-1. gyakorlatot). 3.13. tétel. Legyenek (n, e) a nyilvános, d a titkos kulcsok az RSA-protokollban. Ekkor minden m, 0

≤

m

<

n üzenet esetén m

=

e d

(m )

mod n. Így az RSA (nyilvános kulcsú) kripto-

rendszer. Az RSA-eljárás hatékonysága érdekében megint a M - ´ algoritmust ´ ´ használjuk a gyors-hatványozásra. Hogyan válasszuk meg a 3.8. ábrán bemutatott RSA pro tokollban a p és q prímszámokat? Eloször is elég nagyoknak kell lenniük, egyébként Erik az n számot Bob nyilvános (n, e) kulcsában faktorizálná, és n p és q prímfaktorait meghatározná, így a kiterjesztett euklideszi algoritmussal könnyen meghatározhatná Bob d titkos kulcsát, amely e mod

ϕ(n) egyértelmu inverze, ahol ϕ(n) =

(p

− 1)(q − 1). A

p és q prím-

számoknak titkosaknak kell maradniuk, s ezért elegendoen nagyoknak kell lenniük. A gya kell tehát korlatban p-t és q-t mindig legalább 80 decimális jegyunek kell választani. Elo állítani ilyen nagyságú véletlen számokat, és tesztelni kell egy ismert véletlen prímteszttel, hogy vajon valóban prímek-e. Mivel a prímszámok elmélete szerint körülbelül N / ln N Nnél kisebb prímszám van, nagy a valószínusége annak, hogy nem túl sok próbálkozás után

112


prímszámra akadjunk. hogy p és q prímek-e. Elméletileg determinisztikusan polinomiális idoben eldöntheto, eredményt publikálták, hogy a Agrawal, Kayal és Saxena a közelmúltban azt a meglepo

PRIMES = {bin(n) | n prím} prímszámprobléma a P bonyolultsági osztályba tartozik. Ez az áttörés megoldotta a bonyolultságelmélet régóta nyitott problémáját, mert a grázomorzmus probléma mellett a prímszámprobléma tunt olyannak, amely se nem P-beli, se nem 3

NP-teljes.

12

Bár az algoritmus futási idejének eredeti O(n

6

) korlátját azóta O(n )-ra

javították, az algoritmus a gyakorlati alkalmazások számára nem elég gyors. algoritmusa, amely Miller deterA legkedveltebb véletlen prímteszt Rabin következo minisztikus algoritmusának elvére épül. MR(n) 1 2 3 4

− 1 = 2k m átalakítást, ahol m és n páratlanok válasszunk véletlenszeruen egy z ∈ {1, 2, . . . , n − 1} számot egyenletes eloszlással m számítsuk ki az x = z mod n értéket if x ≡ 1 mod n

végezzük el az n

5

then return

6

else for j

7

n prímszám

← 0 to k − 1 do if x ≡ −1 mod n

8

then return

9

else x

10

←

x

n prímszám

2

return

mod n

n nem prímszám

A MR teszt úgynevezett Monte-Carlo-algoritmus,

nem válasza megbíz A MillerRabinigen válasza azonban egy bizonyos hibavalószínuséggel értendo. 3 O(n ) idoben teszthez hasonló Solovay és Strassen prímtesztje. Mindketto dolgozik. A ható,

SolovayStrassen-teszt azonban kevésbé népszeru, mert a gyakorlatban nem olyan hatékony, mint a MillerRabin-teszt és kevésbé pontos. Azon problémák osztályának, amelyek a Monte-Carlo-algoritmussal mindig megbízható

igen válasszal oldódnak meg, külön nevük van: RP, a Randomized Polynomial Time származó betuszó. kifejezésbol A komplementer osztály, coRP = { L | L ∈ RP}, mindazokat a

problémákat tartalmazza, amelyekre a Monte-Carlo-algoritmus mindig megbízható nem választ ad. RP-t formálisan a nemdeterminisztikus polinomiális ideju Turing-gépekkel de niáljuk (röviden NPTM; lásd a 4.1. alfejezetet és foként a 4.1., 4.2. és 4.3. deníciókat), amelyeknek a muködése véletlen folyamatként fogható fel: minden nemdeterminisztikus két elágazás mindeelágazásnál a gép úgymond pénzfeldobással muködik, és a következo gyike 1/2 valószínuséggel következik be. Az NPTM-ben megvalósuló utak száma szerint minden bemeneti adathoz tartozik egy bizonyos megvalósulási valószínuség, ahol hibák is felléphetnek. RP deníciója megkívánja, hogy az elfogadott bemeneti értékek esetén a hibavalószínuség soha nem lehet nagyobb 1/2-nél, miközben az elutasított bemenetek esetén egyáltalán nem léphet fel hiba. 3.14. deníció (véletlenített polinomiális ido). Az RP osztály pontosan azokat az A problémákat tartalmazza, amelyekhez van olyan NPTM M, hogy M mindegyik x 1/2 valószínuséggel fogadja el, x

3

<

∈

A-t legalább

A-t pedig 0 valószínuséggel fogadja el.

A P és NP bonyolultsági osztályokat a 4.1. alfejezetben deniáljuk, az NP-teljességet pedig a 4.2. alfejezetben.

3.3. RSA és faktorizálás 3.15. tétel. A

113

PRIMES a coRP ben van.

A fenti tétel azt mondja, hogy a MillerRabin-teszt a prímszámproblémára MonteCarlo-algoritmus. A bizonyítást itt csak vázoljuk. Megmutatjuk, hogy a MillerRabin-teszt

PRIMES-t

egyoldalú hibavalószínuséggel fogadja el: ha a (binárisan eloállított) n bemeno

érték prímszám, akkor az algoritmus nem válaszolhatja tévesen azt, hogy n nem prímszám. Hogy ellentmondásra jussunk, tegyük fel, hogy n prím, de a MillerRabin-teszt azzal a n nem prímszám. Következésképpen z . 1 mod n áll fenn. Mik−1 m 2m 2 m vel x-et a for ciklus minden lefutásakor négyzetre emeljük, modulo n a z , z , . . ., z m

kimenettel áll le, hogy

egymás utáni értékeket vizsgáljuk. Ezen értékek egyikénél sem válaszolja azt az algoritmus, n

j

. −1 mod n minden j, 0 ≤ j ≤ k − 1 esetén. Mivel 2 m z − 1 = 2k m, a kis-Fermat-tételbol ≡ 1 mod n következik (lásd a 3.5. következményt).

következik, hogy z hogy n prím. Ebbol

2 m

k

2

Ezért z

k−1

m

1 négyzetgyöke modulo n. Mivel n prím, 1-nek modulo n csak két négyzet-

2

tehát z

k −1

±1 mod n,

k −1

. −1 mod n miatt ≡ 1 mod n teljesül. De ekkor megint z 1-nek négyzetgyöke modulo n. Mint − 2 m megint z fent, ebbol ≡ 1 mod n következik. Ezt a érvet ismételten alkalmazva végül m azt kapjuk, hogy z ≡ 1 mod n, ami ellentmondás. Következésképpen a MillerRabin-teszt

gyöke van, nevezetesen a

(lásd a 3.3-2. gyakorlatot). z

m

2

k−2

2

m

m

k 2

minden prímszám esetén helyes választ ad. Ha n nem prímszám, akkor megmutatható, hogy a MillerRabin-teszt valószínusége nem lépi túl az 1/4 küszöböt. Ismételt független teszt kárára, ami mindamellett log n-ben futtatásokkal azt kapjuk, természetesen a futási ido polinomiális marad hogy a hibavalószínuség tetszolegesen közel kerül nullához. RSA. Bob a p = 67 és q = 11 prímszámokat választja. Így n = 67 · 11 = 737 és − 1)(q − 1) = 66 · 10 = 660. Ha most Bob a ϕ(n) = 660-hoz a leheto legkisebb kitevot nyilvános kulcsa az (n, e) = (737, 7) pár. A kiterjesztett euklideválasztja, ami e = 7, akkor az o szi algoritmus Bobnak a d = 283 titkos kulcsot szolgáltatja, és fennáll e · d = 7 · 283 = 1981 ≡ 1 mod 660 (lásd a 3.3-3. gyakorlatot). Amint a 3.1. alfejezetben is tettük, a Σ = {A, B, . . . , Z} ábécét a Z26 = {0, 1, . . . , 25} halmazzal azonosítjuk. Az üzenetek a Σ fölötti szavak, és azonos hosszú-

3.7. példa.

ϕ(n) =

(p

ságú blokkonként 26-os számrendszerben eloállított számokként kódoljuk. Példánkban a blokkhossz

` = blog26 nc = blog26 737c = 2. Egy b = b1 b2 · · · b` blokkot, amelynek a hossza `, és bi ∈ Z26 , ábrázolja. Az ` = blog26 nc blokkhossz deníció következtében: 0

≤ mb ≤ 25 ·

` X

`−i

26

az mb

=

P`

i=1

bi

·

26

`−i

szám

= 26` − 1 < n.

i=1

függvénnyel a b blokkot, illetve a megfelelo mb számot cb Az RSA rejtjelezo rejtett szöveg ekkor cb sifrírozzuk. A b blokknak megfelelo az

`

hosszúságú blokkokat injektíven képezi le

`+1

=

e

(mb ) mod n szerint

= c0 c1 . . . c` , ahol ci ∈ Z26 . Az RSA tehát

hosszúságú blokkokra. A 3.9. ábrán láthatjuk,

hogy egy 34 hosszú üzenetet 17 darab 2 hosszú blokkba tördeltünk és az egyes blokkokat számokként blokkot, amely rejtjeleztük. Például az elso nek a 17 és

RS, számmá transzformáltuk a következoképpen:

· 261 + 18 · 260 = 442 + 18 = 460. eloállíthatjuk 26-os számrendszerben és ` +

S-nek a 18 felel meg, és 17

R-

A kapott cb számot megint 1 lehet a hossz: cb `−i c · 26 , ahol c ∈ Z (lásd a 3.3-3. gyakorlatot is). Így az els o blokk 697 = 676 + 21 i i 26 i=0

P` 1

= =

· 262 + 0 · 261 + 21 · 260 , a rejtjelezett szövegben

BAV lett belole. blokkot a d A visszafejtés is blokkonként történik. Ahhoz, hogy az elso

697 visszafejtsük, kiszámoljuk a következot:

 ´ ´

283

=

283 titkos kulccsal

mod 737, ismét gyors-hatványozással, a M ´

algoritmus segítségével. Azért, hogy a számok ne legyenek nagyon nagyok, ajánlatos

minden szorzásnál modulo n

=

bináris kifejtése 283 737 redukálni a kapott értékeket. A kitevo

=

114


Üzenet

R S

A I

S T

H E

K E

Y T

O P

U B

L I

C K

E Y

C R

Y P

T O

G R

A P

H Y

mb

460

8

487

186

264

643

379

521

294

62

128

69

639

508

173

15

206

cb

697

387

229

340

165

223

586

5

189

600

325

262

100

689

354

665

673

rejtjelezésre. 3.9. ábra. Példa RSA-val történo

Lépés

Aliz

Erik

=

értékeket választja: n A következo

1

Bob

pq,

(n, e) nyilvános kulcs és d titkos kulcs, RSAahogyan Bob tette a 3.8. ábrán lévo protokollban (n, e)

2 3

Aláírja az m üzenetet: sigA (m)

=

d

m

⇒

mod

n

(m, sigA (m))

4

⇒ Aliz aláírását m Ellenorzi

5

sigA (m) vel

e

≡

mod n segítségé-

3.10. ábra. Digitális aláírás RSA-val.

0

2

+ 21 + 23 + 24 + 28 , és amint kívántuk adódik a következo: 697

283

0

1

3

4

8

≡ 6972 · 6972 · 6972 · 6972 · 6972 ≡ 697 · 126 · 9 · 81 · 15 ≡ 460 mod 737.

3.3.2. Digitális aláírás RSA segítségével RSA nyilvános kulcsú kriptorendszer módosítható úgy, hogy protoA 3.8. ábrán szereplo od kollként digitális aláírásra alkalmas legyen. Ilyet mutattunk be a 3.10. ábrában. Meggyoz hetünk arról, hogy a protokoll muködik (lásd a 3.3-4. gyakorlatot). Ez a protokoll érzékeny nyílt szöaz olyan támadásra, amelynél a támadó maga meg tudja választani a rejtjelezendo veget (választott nyílt szövegu támadás.

3.3.3. Az RSA biztonsága és lehetséges támadások az RSA ellen mértékben attól függ, hogy nagy számok Már említettük, hogy az RSA biztonsága dönto nem könnyen faktorizálhatók. Mivel elszánt keresés ellenére sem sikerült ezidáig hatékony faktorizáló algoritmust találni, azt gyanítjuk, hogy ilyen algoritmus nincs, vagyis a faktorizálási probléma nehéz. Erre a sejtésre azonban még nem született bizonyítás. Önmagában ennek a sejtésnek a bizonyításából nem következne, hogy az RSA-rendszer biztonságos. Tudjuk, hogy az RSA feltörése legfeljebb olyan nehéz, mint a faktorizálási probléma, azt az is, hogy az RSA könnyen azonban nem tudjuk, hogy ugyanolyan nehéz-e. Elképzelheto n faktorizálása nélkül is. feltörheto Az RSA-rendszer elleni lehetséges támadások listája helyett, amely különben is hiányos lenne, utalunk a további hivatkozásokat tartalmazó idevágó irodalomra, valamint a ellenintézke3-4. feladatra. Mindegyik eddig ismert RSA elleni támadásra van megfelelo dés, amelyek meghiúsítják, vagy hatástalanítják a támadást, tehát a támadás sikerességének

3.3. RSA és faktorizálás

115

Foként a valószínusége elhanyagolhatóan kicsivé teheto. a p és q prímszámokat, az n mo és a d titkos kulcsot kell megfelelo gondossággal megválasztani. dulust, az e kitevot Mivel az RSA elleni faktorizálási támadás különösen központi szerepet játszik, bemutatunk egy egyszeru ilyen támadást, amely John Pollard ( p (p

− 1)-módszer

− 1)-módszerén alapszik. A

p prímfaktorú összetett n szám esetén akkor muködik, ha p − 1 prímfakto-

rai kicsik. Ekkor ugyanis meg lehet határozni p

− 1 egyik ν többszörösét anélkül, hogy

p-t

ismernénk, és alkalmazhatjuk a kis Fermat-tételt (lásd a 3.5. következményt), amely szerint

ν

a

≡

1 mod p minden a egész szám esetén fennáll, amely p-hez relatív prím. Következés-

ν

képpen p egy osztója a

− 1-nek. Ha n nem osztója aν − 1-nek, akkor lnko(aν − 1, n) valódi

osztója n-nek, s így n-et faktorizáltuk. Hogyan lehet meghatározni p − 1 egy

ν többszörösét? Pollard ( p − 1)-eljárása ν számára

azt a számot alkalmazza jelöltként, amely egy választott S korlát alatti összes prímszámhat ványok szorzataként áll elo:

Y

ν=

q q prím, q

k

≤S
k

.

k +1

− 1 mindegyik prímhatvány osztója kisebb S -nél, akkor ν többszöröse p − 1-nek. Az ν − 1, n) értékét egy alkalmas a alappal. Ha eközben nem sikerül 0 n egyetlen valódi osztóját sem meghatározni, akkor az algoritmus újra indul egy új S > S Ha p

algoritmus kiszámítja lnko(a értékkel.

egyszeru Más faktorizálási módszer többek között a négyzetes szita. Ez a következo ötleten alapul. Az n szám faktorizálásához egy bizonyos szitával olyan a és b számokat keresünk, amelyekre: 2

a

≡ b2 2

Következésképpen n osztja az a

mod n

és

a

. ±b mod n .

(3.10)

− b2 = (a − b)(a + b) számot, de nem osztja sem a − b-t, sem

a + b-t. Így lnko(a − b, n) egy nem triviális tényezoje n-nek. A négyzetes szita mellett vannak abban a módszerben különböznek, ahogyan a (3.10)-et más szitamódszerek is, amelyek ettol a és b számokat meghatározzák. Egy példa erre az kielégíto

általános számtest-szita.

Gyakorlatok

3.3-1.? Bizonyítsuk be a 3.13. tételt. Útmutatás. A kis Fermat-tétel 3.5. következményére e d

támaszkodva mutassuk meg, hogy (m ) prímszámok, p

,

q és n

=

≡

e d

m mod p és (m )

≡

m mod q. Mivel p és q e d

következik az (m ) pq, a kínai maradéktételbol

≡

m

mod n

állítás. 3.3-2.? A 3.15. tétel bizonyításának vázlatában felhasználtuk azt, hogy egy n prímszám esetén 1-nek csak két négyzetgyöke van modulo n, nevezetesen a

±1 mod n. Bizonyítsuk be

ezt. Útmutatás. Használjuk fel azt, hogy r pontosan akkor négyzetgyöke 1-nek modulo n, ha n az (r

− 1)(r + 1) számot osztja.

3.3-3. a. Mutassuk meg, hogy a 3.7. példában szereplo

ϕ(n) = 660 és e = 7 értékekre a = 283 titkos kulcs adódik, amely

kiterjesztett euklideszi algoritmus segítségével valóban a d 7 mod 660 inverze.

b. Kódoljuk a 3.7. példában a 3.9. ábrabeli nyílt szöveget a

Σ = {A, B, . . . , Z}

ábécé

betuivel mind a 17 blokk esetén. c. Fejtsük vissza a 3.9. ábrán látható rejtett szövegnek mind a 17 blokkját, és mutassuk meg, hogy az eredeti nyílt szöveget kapjuk vissza.

116

3. Kriptográfia (Jörg Rothe) Lépés

Aliz

1

Erik

Bob

véletlenszeruen választ két nagy számot, x-et és y-t, x-et titokban

tartja, és kiszámolja az xσy értékét (y, xσy)

2

⇒

3

véletlenszeruen

választ

egy

z

nagy számot, z-t titokban tartja, és kiszámolja az yσz értéket

⇐ yσz

4 5

kiszámolja a kA

= xσ(yσz)

érté-

kiszámolja a k B

ket 3.11. ábra. A kulcscserére vonatkozó,

3.3-4.

=

(xσy)σz érté-

ket

σ-n alapuló RivestSherman-protokoll.

digitális aláírásra vonatkozó RSA Mutassuk meg, hogy a 3.10. ábrában szereplo

protokoll muködik.

3.4. Rivest, Rabi és Sherman protokolljai Rivest, Rabi és Sherman javasoltak kulcscserére és digitális aláírásra protokollokat. A 3.11. és Sherman tól ered. Könnyen módosítható úgy, hogy ábra kulcscsere protokollja Rivest-tol digitális aláírásra alkalmas legyen (lásd 3.4-1. gyakorlatot). Rivest és Sherman protokollja egy totális, erosen neminvertálható, asszociatív egyirá értjük. Egy totális (tehát mindenhol deniált) nyú függvényen alapszik. Ezen a következot N-be képez, pontosan akkor asszociatív, ha (xσy)σz = σ függvény, amelyik N × N-bol xσ(yσz) minden x, y, z ∈ N esetén teljesül, ahol a σ(x, y) jelölés helyett az xσy jelölést a tulajdonságból következik, hogy a protokoll muködik, alkalmaztuk. Ebbol mert kA = xσ(yσz) = (xσy)σz = k B miatt Aliz és Bob valójában ugyanazt a kulcsot számítják ki. neminvertálhatóságot itt nem kívánjuk formálisan deniálni. Tájékoztatásul Az eros annyit mondunk, hogy

σ-t erosen neminvertálhatónak nevezzük, ha σ nem csupán egyirá-

nyú függvény, hanem akkor sem invertálható hatékonyan, ha a függvényérték mellett ehhez a függvényértékhez tartozó két argumentum egyikét is ismerjük. Ez a tulajdonság megakadályozza azt, hogy Erik y és xσy, illetve yσz ismeretében a titkos x, illetve z számokat ki tudja számolni, amelynek a segítségével a kA

= kB kulcsot könnyen meg tudná határozni.

Gyakorlatok 3.4-1. Módosítsuk Rivest és Sherman 3.11. ábrán látható, kulcscserére vonatkozó protokollját úgy, hogy digitális aláírásra alkalmas protokollt kapjunk. RivestSherman-protokoll 3.4-2. Melyik közvetlen támadás lenne a 3.11. ábrán szereplo ellen hatásos, és hogyan akadályozhatnánk meg? Útmutatás. Érveljünk a irányú függvény

σ asszociatív egy-

neminvertálhatóságának fogalmával, amelyen a protokoll alapszik. eros

neminvertálhatóság fogalmára. eros Nasszociativitás fogalmára parciális, N × N-bol függvények számára. Egy ilyen deníciónak nem kell mindenhol érvényesnek be képezo 3.4-3. a. Adjunk formális deníciót az b. Adjunk formális deníciót az

deníció kísérletnél: lennie. Mi okoz gondot a következo

Egy (esetleg parciális) σ : N (xσy)σz minden olyan x, y, z

N → N függvényt asszociatívnak nevezzük, ha xσ(yσz) =

× ∈

3.5. Interaktív bizonyítási rendszerek és zéró ismeret N

117

esetén érvényben van, amikor az (x, y), (y, z), (x, yσz) és (xσy, z) párok mindnyájan

σ

értelmezési tartományában vannak. denícióját találjuk Hemaspaandra munÚtmutatás. Ezeknek a fogalmaknak kielégíto kájában.

3.5. Interaktív bizonyítási rendszerek és zéró ismeret 3.5.1. Interaktív bizonyítási rendszerek, ArtúrMerlin-játékok és zéró-ismeret¶ protokollok Az a probléma, amelyet a DiffieHellman-protokoll elleni középen állás támadásnál a 3.2. alfejezetben említettünk, nyilvánvalóan abból adódik, hogy Bob a protokoll lejátszása elott odött partnere valódi kilétérol. Bob azt hiszi, hogy Alizzal hajtja nem gyoz meg beszélgeto végre a protokollt, a valóságban azonban Erikkel. Másképpen megfogalmazva Aliznak az a feladata, hogy Bobot kétséget kizáróan meggyozze személyazonosságáról. A kriptográának ezt a feladatát személyazonosításnak nevezzük. A digitális aláírással szemben, amely az elektronikus úton közvetített dokumentum, mint például az e-mail valódiságát hitele van szó, akik a protokollban a résztvevo síti, most azoknak a személyeknek a hitelesítésérol nem személy, vagy résztvevo személy lehet, hanem például egy számítógép, amelyik egy másik számítógépcsak egy élo

felek. Ennek a fogalomnak további értelmezése is van: pel automatikusan lefolytat egy protokollt.

Önmaga hitelességének bizonyítására Aliz felhasználhatna egy csupán általa ismert titkos adatot, mondjuk a PIN kódját (Personal Identifaction Number), vagy más információt, Aliz kénytelen titkát Bobnak amit rajta kívül más nem ismer. Itt azonban van egy bökkeno. elárulni személyazonossága valódiságának bizonyítására. Ekkor azonban az nem lesz többé már titok. Bob egy harmadik féllel lefolytatott protokoll során közölhetné mondjuk Kris Aliz, mert már ismeri Aliz titkát. Az a kérdés tehát, hogyan bizonyíthatná az tóffal, hogy o van szó a ember egy titok ismeretét anélkül, hogy magát a titkot elárulná. Pontosan errol zéró-ismeretu protokollokban. Ezek speciális interaktív bizonyítási rendszerek, amelyeket Goldwasser, Micali és Rackoff vezettek be. Tolük függetlenül fejlesztette ki Babai és Moran az ezzel lényegében ekvivalens ArtúrMerlin-játékok tervét, amelyet most informálisan leírunk. A hatalmas Merlin varázsló, akit egy M NP gép reprezentál, és a bizalmatlan Artúr király, akit egy A randomizált polinomideju gép reprezentál, közösen meg akarnak oldani egy L problémát, tehát el akarják dönteni, hogy egy x bemenet L-hez tartozik-e, vagy sem. adatért játszanak, miközben felváltva lépnek. Merlin szándéka mindig Mindegyik bemeno szavuk L-hez tartozik, függetlenül az, hogy Artúrt meggyozze arról, hogy a közös x bemeno attól, hogy ez valóban így van-e. Merlin egy lépése az x ∈ L (állítólagos) bizonyítására vonatkozó adat. Ezt megkapja egy M(x, y) szimulációval, ahol x a bemenetet és y az eddigi lépéseket kódolja. Az y szó tehát leírja az M eddigi nemdeterminisztikus választásait, illetve A eddigi véletlen választásait. Artúr király azonban bizalmatlan. A hatalmas varázsló állítólagos bizonyítását termé szetesen nem tudja közvetlenül ellenorizni, ehhez nincs meg a számítási ereje. Kétségbe tudja azonban vonni Merlin bizonyítását, és képes egy ügyes kihívással válaszolni, amely ta választott részleteihez ellenorizhet o ben a Merlin szolgáltatta bizonyítás véletlenszeruen valószínuséggel núsítványt követel. Hogy Artúrt kielégítse, Merlinnek lenyugöz o meg kell

118


gyoznie Artúr egyik lépése tehát abból áll, hogy A(x, y) ot bizonyításának helyességérol. számításokat szimuláljon, ahol x megint a bemenetet, y pedig a játék eddigi lefutását írják le. váltakozva egzisztenciális és valószínuAz ArtúrMerlin-játék gondolata kifejezheto ségi kvantorokkal, ahol az elobbiek Merlin NP-számítását, az utóbbiak pedig Artúr randomizált polinomiális számításait formalizálják.

4

Ilyen módon bonyolultsági osztályok hie-

rarchiáját deniálhatjuk, az úgynevezett ArtúrMerlin-hierarchiát. Itt az MA osztály deníciójára szorítkozunk, ez egy olyan két lépéses ArtúrMerlin-játéknak felel meg, amelynél Merlin lép eloször. 3.16. deníció (MA az ArtúrMerlin-hierarchiában). Az MA osztály pontosan azokat az L problémákat tartalmazza, amelyekre van egy M NPTM és egy A randomizált polinomideju Turing-gép, hogy minden x bemenetre fennáll:

•

Ha x

∈

L, akkor van egy olyan y út M(x)-ben, hogy A(x, y)

elfogad, (vagyis Arthur Merlinnek az megcáfolni, és Merlin nyer).

•

Ha x

<

x

∈

L, akkor M(x) mindegyik y útját A(x, y)

Artúrt Merlin

x

∈

≥

3/4 valószínuséggel

L-re vonatkozó y bizonyítását nem tudja

≥ 3/4 valószínuséggel elutasítja (vagyis

L-re vonatkozó hamis bizonyítása nem téveszti meg, és nyer).

Ennek megfeleloen lehet deniálni az AM, MAM, AMA, . . . osztályokat (lásd a 3.5-1. gyakorlatot). A 3/4 valószínuségi küszöb a 3.16. denícióban, amely szerint Artúr elfogad vagy elutasít, önkényesen lett megválasztva, és eleinte nem tunik elég nagynak. Valójában lehet nö velni a siker valószínuségét, és 1-hez tetszolegesen közel hozni. Másként megfogalmazva, a denícióban alkalmazhatunk 1/2

+ ε valószínuséget egy tetszoleges rögzített ε > 0 kons-

tanssal, s így még mindig ugyanazt az osztályt kapjuk. Továbbá ismert az, hogy a lépések egy konstans száma esetén ez a hierarchia beleolvad az AM osztályba ( stabilizálódik): NP ⊆ MA ⊆ AM = AMA = MAM = · · · . Az a kérdés azonban még nyitott, hogy az NP

⊆ MA ⊆ AM tartalmazás valódi-e. A fent említett interaktív bizonyítási rendszerek az ArtúrMerlin-játékok változatai.

Jelentéktelen különbség a terminológiában az, hogy Merlin az

igazoló, Artúr pedig az o, ellenorz és a kommunikáció nem játékként zajlik, hanem protokoll formájában. Elso különbség, hogy Artúr véletlen bitje nyilvánosan pillantásra a két modell között az a jelentos o véletlen bitje az és elsosorban Merlin számára ismert, ezzel ellentétben az ellenorz interaktív bizonyítási rendszerekben titkos. Goldwasser és Sipser megmutatták azonban, hogy valójában lényegtelen az, hogy a véletlen bit titkos, vagy nyilvános. Tehát az Artúr Merlin-játékok és az interaktív bizonyítási rendszerek egymással ekvivalensek. Ha a játékban konstans számú lépés helyett polinomiálisan sokat engedünk meg és többet a polinomiális idokorlátozás miatt nem lehet , akkor az IP osztályt kapjuk. Dení ció szerint IP tartalmazza az egész NP-t, és foként a grázomorzmus-problémát. Késobb látni fogjuk, hogy IP tartalmaz coNP

= {L | L ∈

felNP}-beli problémákat is, amelyekrol

tesszük, hogy nincsenek NP-ben. A 4.21. tétel bizonyítása elsosorban azt mutatja meg, hogy a grázomorzmus-probléma komplementere AM-ben és így IP-ben van. Shamir egyik híres eredménye azt mondja, hogy IP még PSPACE-szel is megegyezik, azon problémák osz-

4

Ez hasonlít a polinomiálisido-hierarchia lépéseinek a 4.4. alfejezetet és foként a 4.16. tétel 3. részét).

∃ és ∀ kvantorokkal váltakozva történo jellemzéséhez, (lásd

3.5. Interaktív bizonyítási rendszerek és zéró ismeret

119

tályával, amelyek a polinomiális térben eldönthetok. Térjünk azonban vissza a hitelesség elobb vázolt problémájához, és a zéró-ismeretu protokollok fogalmához. Nézzük az alapgondolatot. Tegyük fel, hogy Artúr és Merlin egyik játékukat játsszák. Az interaktív bizonyítási rendszerek terminológiája szerint ebben az IPprotokollban Merlin nehéz bizonyítást küld Artúrnak. Hogy honnan varázsolta ezt a bizo ismeri, ezzel hitelesíteni tudja magát Artúr elott. nyítást, az Merlin titka, és mivel csak o Amit egyikük sem tud: a gonosz varázsló Marvin varázsital segítségével Merlin ha sonmásává változott, és Artúr elott Merlinként akarja kiadni magát. Merlin titkát azonban nem ismeri. Hasonlóképpen nincs meg neki Merlin hatalmas varázslóereje sem, mágiája nem nagyobb, mint egy közönséges randomizált polinomideju Turing-gép számítási ereje. Ugyanolyan csekély, mint amennyire Artúr képes Marvinnak Merlin-bizonyítást találni. Ennek ellenére megkísérli, hogy a Merlin és Artúr közötti kommunikációt szimulálja. Egy IP-protokoll pontosan akkor zéró-ismeretu, ha az az információ, amely Marvin és Artúr között kicserélésre kerül, nem különbözik a Merlin és Artúr közötti kommunikációtól. Ekkor Marvin, aki Merlin titkos bizonyítását nem ismeri, természetesen nem tud róla a szimuláló protokollba semmiféle információt sem áramoltatni. Bár abban a helyzetben van, hogy az eredeti protokollt pontosan lemásolta, úgy, hogy egy független meggyelo semmiféle különbséget nem tudna felfedezni, a protokoll semmilyen információt nem tud közölni: Ahol nincs, ott ne keress! 3.17. deníció (zéró-ismeretu protokoll). L

∈

IP esetén legyen M NPTM és A pedig ran-

domizált polinomideju Turing-gép úgy, hogy (M, A) interaktív bizonyítási rendszer L számára. Az (M, A) IP-protokoll pontosan akkor zéró-ismeretu protokoll L számára, ha van

b randomizált polinomideju Turing-gép, hogy ( M b, A) az (M, A) eredeti protokollt egy olyan M szimulálja, és minden x

∈

b, A)-beli kommunikációt L esetén az (M, A)-beli, illetve az ( M

b1 , m b2 , . . . , m bk ) sorozatoknál azonos a pénzfeldobás elreprezentáló (m1 , m2 , . . . , mk ) és (m oszlása. A fent deniált fogalmat az irodalomban úgy nevezik, hogy tökéletes zéró ismeret becsületes igazolóval (honest-verier perfect zero-knowledge). Ez a következoket jelenti: o Artúr becsületes (aminek nem feltétlenül kell teljesülnie (a) feltesszük, hogy az ellenorz a kriptográai alkalmazásokban), és (b) megkívánjuk, hogy a szimuláló protokollban közölt információ tökéletesen megegyezzék az eredeti protokollban közölt információval. Az feltétel némileg idealista, a második alkalmasint túl szigorú. Ezért vizsgálják a zéróelso megjegyzéseket). ismeretu protokollok más változatait (lásd a fejezet végén levo

3.5.2. Zéró-ismeret¶ protokoll gráfizomorfizmusra GI NP-ben van, a komplementer GI, AM-ben (lásd a 4.21. tétel bizonyítását). Így mindkét probléma IP-ben van. Most adunk egy zéró-ismeretu protokollt GI-re. Bár manapság nincs hatékony eljárás GI-re, Merlin meg tudja oldani ezt a problémát, mert GI NP-ben van. Jóllehet nem szükséges, hogy ezt tegye. Megteheti, hogy egyszeruen választ egy nagy G 0 gráfot, amelynek n csúcsa van, valamint véletlenszeruen egy π ∈ Sn permutációt, és eloállítja a G 1 = π(G 0 ) gráfot. A (G 0 , G 1 ) párt nyilvánosságra hozza, a G 0 és G 1 közötti π izomorzmust saját információjaként titokban tartja. A 3.12. ábra mutatja a Most egy konkrét példát vizsgálunk. Már említettük, hogy probléma pedig

Merlin és Artúr közötti IP-protokollt.

120


Lépés 1

Merlin választ egy ra és egy a

ρ(Ga )-t

Artúr

ρ véletlen permutációt V (G0 )∈ {0, 1} bitet, kiszámolja H =

2

H

⇒

3

választ egy b

∈ {0, 1}

véletlen bitet,

majd G b és H között követel egy izomorzmust

⇐b

4 5

kiszámolja a

σ

izomorzmust

σ(Gb ) =

H-

val: ha b

= a, akkor σ = ρ; = b , a = 1, akkor σ = πρ; −1 ha 1 = b , a = 0, akkor σ = π ρ. ha 0

σ⇒

6

ellenorzi, hogy σ(G b ) = H, és akkor fogadja el, ha ez teljesül

7

3.12. ábra. Goldreich, Micali és Wigderson

GI-re vonatkozó zéró-ismeretu protokollja.

Természetesen Merlin nem küldheti el Artúrnak egyszeruen

π-t, mert akkor elárulná a

titkát. Annak bizonyítására, hogy az adott G 0 és G 1 gráfok valóban izomorfak, Merlin vá ρ izomorzmust és egy a bitet, és eloállítja egy kihívással válaszol: küld Merlinnek = ρ(Ga ) gráfot. Ezután elküldi Artúrnak H-t. O egy véletlenszeruen egyenletes eloszlással választott b bitet, és követel tole egy σ izomorzmust G b és H között. Ezt pontosan akkor fogadja el Artúr, ha Merlin σ-jára valóban teljesül σ(Gb ) = H. A protokoll muködik, mert Merlin ismeri saját titkos π izomorzmusát és véletlenszeruen választott ρ permutációját. Nem okoz problémát Merlinnek, hogy kiszámolja a σ hitelesítse magát. A π titkot azonban nem árulja izomorzmust G b és H között és Artúr elott

laszt véletlenszeruen egyenletes eloszlással egy aH

el. Mivel G 0 és G 1 izomorfak, Artúr 1 valószínuséggel elfogad. Itt egyáltalán nem kell vizs gálni két nem izomorf gráf esetét, mivel Merlin a protokollnak megfeleloen izomorf G 0 és G 1 gráfokat választ (lásd a 4.21. tétel bizonyítását is). Merlinként kiadni. Ismeri a G 0 és Tegyük fel, hogy Marvin szeretné magát Artúr elott

π izomorzmust. Mégis szeretné színlelni, hogy ismeri π-t. Ha az Artúr által választott b bit véletlenül megegyezik az a bittel, amelyet Marvin elore −1 nyer. Ha azonban b , a, akkor a σ = πρ vagy σ = π ρ kiszámítása határozott meg, akkor o igényli π ismeretét. Mivel GI egy randomizált polinomideju Turing-gép számára túl nehéz,

G 1 gráfokat, de nem ismeri a titkos

és hatékonyan nem számítható ki, Marvin elég nagy G 0 és G 1 gráfok esetén nem tudja

π-t, csak találgathat. Az o esélye arra, = a, legfeljebb 1/2. Természetesen Marvin sikervalószínusége mindig találgathat, és így az o pontosan 1/2. Ha Artúr azt kívánja, hogy meghatározni a

π

izomorzmust. Nem ismerve a

hogy véletlenül elcsípjen egy b bitet, amelyre b

r független körben végezzék el a protokollt, akkor a csalás valószínusége a 2 szorítható le. Ez már r

=

−r

értékre

20 esetén is elenyészoen csekély: Marvin sikervalószínusége

kisebb, mint egy a millióhoz. protokoll valóban zéró-ismeretu Meg kell még mutatnunk, hogy a 3.12. ábrán szereplo protokoll. A 3.13. ábrán látható egy szimuláló protokoll Marvinnal, aki Merlin

π titkát nem

ismeri, de azt színleli, hogy ismeri. Az az információ, amelyik a protokoll egy lefutása alatt kicserélésre kerül, a (H, b, σ) hármasként adható meg. Ha Marvin véletlenszeruen választ

3. fejezet feladatai

121

Lépés

Marvin

1

Artúr

ρ véletlen permutációt V (G0 )a ∈ {0, 1} bitet, kiszámolja H =

választ egy ra, és egy

ρ(Ga )-t 2

H

⇒

3

választ egy b

∈ {0, 1}

véletlen bitet,

és követel egy izomorzmust G b és H között

⇐b

4 5

ha b

,

b kitöröl minden ebben a a, akkor M

körben eddig közvetített információt és ismétel; ha b

b elküldi σ = ρ-t = a, akkor M σ⇒

6 7

b

=

a esetén

σ(Gb ) =

H, ezért Ar-

túr elfogadja Marvin hamis személyazonosságát 3.13. ábra. A

egy a bitet, és a

=

GI-re vonatkozó zéró-ismeretu protokoll szimulációja π ismerete nélkül.

b, akkor egyszeruen elküldi

σ = ρ-t

és nyer: Artúr, vagy bárki más

nem tud semmilyen szabálytalanságot felfedezni. Másrészt, ha a független meggyelo

, b,

Marvin csalása leleplezodik. Ez azonban nem okoz gondot az álnok varázslónak: egyszeruen kitörli a szimuláló protokollból ezt a kört és újra próbálkozik. Így (H, b, σ) formájú hármasok sorozatát tudja eloállítani, amelyek a Merlin és Artúr közötti eredeti protokoll sorozataitól megkülönböztethetetlenek. Így Goldreich, Micali hármasaiból álló megfelelo és Wigderson

GI protokollja zéró-ismeretu protokoll.

Gyakorlatok

3.5-1. Deniáljuk az ArtúrMerlin-hierarchia AM, MAM, AMA, . . . osztályait a 3.16. deníció MA osztályához hasonlóan. 3.5-2. Melyik osztályt kapjuk egy olyan ArtúrMerlin-játékban, amelyik csak egy lépésbol áll, amelyet Merlin, illetve amelyet Artúr végez? 3.5-3. Folytassuk le a 3.12. ábrán látható zéró-ismeretu protokollt a G 0 gráfok, valamint a G és H közötti

π=

(13

=

G és a G 1

=

H

) izomorzmus esetén, ahol G és H a 3.1.3. 2

2 3 4 5 4 1 5

pontban a 3.4. példabeli gráfok. Játsszuk le ezt az ArtúrMerlin-játékot egy magunk választotta

ρ izomorzmussal a ∈ {0, 1} és b ∈ {0, 1} mindegyik változatára. Ismételjük meg ezt a ρ izomorzmussal, amelyet valaki más választott.

játékot egy számunkra ismeretlen

−10

3.5-4. Módosítsuk a 3.12. ábra protokollját úgy, hogy Marvin csalásvalószínusége a 2

érték alá kerüljön. Adjuk meg ennek a valószínuségnek egy formálisan helyes elemzését.

Feladatok Z k maradékosztálygyur uben ∈ N és x, y, z ∈ Z. Azt mondjuk, hogy x kongruens y-nal modulo k (röviden: x ≡ y mod k), ha k osztja az y − x különbséget. Az x + kZ = {y ∈ Z | y ≡ x mod k} halmazt x mod k vett maradékosztályának nevezzük.

3-1. Aritmetika a Legyenek k

122


Például 3 mod 7 maradékosztálya a 3 + 7Z

= {3, 3 ± 7, 3 ± 2 · 7, . . .} = {3, 10, −4, 17, −11, . . .}

halmaz. Egy x mod k maradékosztály reprezentánsa legyen mindig a legkisebb természetes szám x

+ kZ-ben;

például 3 reprezentálja a 3 mod 7 maradékosztályt. Az összes mod k

Zk = {0, 1, . . . , k − 1}. Zk -n deniálunk összeadást az + kZ) + (y + kZ) = (x + y) + kZ és szorzást az (x + kZ) · (y + kZ) = (x · y) + kZ szabályok segítségével. A modulo 7 vett aritmetikában például (3 + 7Z) + (6 + 7Z) = (3 + 6) + 7Z = 2 + 7Z és (3 + 7Z) · (4 + 7Z) = (3 · 4) + 7Z = 5 + 7Z. vett maradékosztály reprezentánsa (x

Bizonyítsuk be, hogy modulo k aritmetikát alkalmazva: a.

(Zk , +, ·) kommutatív egységelemes gyur u;

b.

A 3.3. példában deniált

c.

(Z p , +, ·) minden p prímszám esetén test. Milyen struktúra (Z p

Z∗k halmaz multiplikatív csoport; ∗

∪ {0}, +, ·),

ha p prím-

szám? d.

Bizonyítsuk be, hogy egy csoport semleges eleme, valamint minden csoportelem inverze egyértelmuen meghatározott.

e.

f.

portot alkotnak, az

R gyur u invertálható elemei csoR úgynevezett egységcsoportját. Mi a Zk gyur u egységcsoportja?

Határozzuk meg a

Zk

Mutassuk meg, hogy egy kommutatív egységelemes

maradékosztálygyur u nullosztóit. Mutassuk meg, hogy

Zk -ban

nincs nullosztó, ha k prímszám.

3-2. Faizomorzmus Speciális gráfosztályok esetén, például a fák osztályában, a

GI probléma hatékonyan meg-

körmentes gráf, ahol egy kör egymásután követoldható. Egy (irányítatlan) fa összefüggo, élekbol áll, úgy, hogy a kiindulási csúcsba visszatérünk, és minden csúcs legfeljebb kezo egyszer szerepel benne. Egy fa levelei az 1-fokú csúcsok. Tervezzünk hatékony algoritmust a faizomorzmusra, amely P-ben van. Ezt a problémát így deniáljuk:

TI

=

{(G, H) | G és H izomorf fák} .

számsorozatokkal, és Útmutatás. Jelöljük meg fokozatosan az adott fák csúcsait megfelelo sorozatokat. Kezdjük a levelekkel és mindegyik lépésben hasonlítsuk össze a kapott jelölo lépésre haladjunk a fa belseje felé, amíg az összes csúcsot meg nem jelöltük. lépésrol 3-3. Determináns számítása Írjuk meg egy olyan algoritmus pszeudokódját, amelyik egy mátrix determinánsát haté konyan kiszámítja. Ültessük át az algoritmust egy tetszoleges programnyelvre. Ki lehet-e hatékonyan számítani egy mátrix inverzét? 3-4. Alacsony kitevoj u támadás

a.

A 3.8. ábrán látható RSA-rendszerben az e

=

hatékonysági okok miatt nép3 kitevo

szeruségnek örvend. Ez azonban veszélyes lehet. Tegyük fel, hogy Aliz, Bob és Kristóf ugyanazt az m üzenetet ugyanazzal a nyilvános e

=

3 kitevovel, de esetleg különbözo

rejtett szöveget: nA , n B és nC modulusokkal rejtjelezik. Erik elcsípi a három keletkezo ci

=

3

m

mod ni , ahol i

fejteni. Hogyan?

∈ {A, B, C }.

Ezután Erik az m üzenetet könnyen vissza tudja

3. fejezet megjegyzései

123

= +1, amelynek bináris eloállításában csak két egyes van, s így a M - ´ ´ ´

számára e Útmutatás. Erik ismeri a kínai maradéktételt. Egy javasolt érték a kitevo 16

2

algoritmus nagyon gyorsan feldolgozza. b.

A fent leírt támadásokat ki lehet terjeszteni k darab olyan rejtett szövegre, amelyek egymással kapcsolatban vannak. Legyenek ismertek valamilyen ai és bi 1 értékek, és tegyük fel, hogy k darab ci mindegyiket el is fogták, ahol k

>

e(e

= (ai m + + 1)/2 és

≤

i

≤

k

e

bi ) mod ni üzenetet küldtek el és min(ni )

>

e

2

2 . Hogyan tudja egy

támadó kideríteni, hogy mi az eredeti m üzenet? Útmutatás. Az úgynevezett rácsredukciós technikával (lásd például Miccianció és Goldwasser cikkét). c.

Hogyan lehet ezt a támadást elhárítani?

Megjegyzések a fejezethez Diffie és Hellman nyilvános kulcsú kriptográáról szóló munkája [14]. Az angol, francia, német és nn nyelvu szövegek betuinek gyakoriságáról [57]-ban olvashatunk. Charles Babbageról Singh ír a könyvében [66]. Claude Shannon korszakalkotó munkája a tökéle [65]. Ron Rivest, Adi Shamir és Leonard Adleman [52] tes titkosságú kriptorendszerekrol ismert nyilvános kulcsú kriptorendszert. Agrawal, Kayal és munkájukban írták le az elso Saxena[1] munkájukban publikálták azt az eredményt, hogy a

PRIMES = {bin(n) | n prím}

prímszámprobléma a P bonyolultsági osztályba tartozik. John Pollard ( p

[48]-ben olvashatunk. Rabin és Miller véletlen prím− 1)-módszerérol

tesztje a [44, 50] cikkekben, Solovay és Strassen prímtesztje pedig a [67] cikkben található meg. Választott szövegu támadásról olvashatunk a [54] dolgozatban. Az RSA-rendszer elleni lehetséges támadásokról a további utalásokat tartalmazó [6]-ben lehet olvasni. A négyzetes szita leírását megtalálhatjuk például [68]-ben, az pedig az [39] cikkben.

általános számtest-szita leírását

Stinsonnál [68] olvashatunk arról, hogy ha p és q prímszámok, p e d

hogyan következik az (m ) maradéktételbol

≡m

, q és n =

pq, a kínai

mod n állítás. A 3.4-3. gyakorlat megol-

deníciót találunk a [27, 28] munkákban. A zéró-ismeretu dásához kielégíto protokollokat Goldwasser, Micali és Rackoff [22] vezették be. Az ArtúrMerlin-játékok tervét Babai és Moran [3, 4] fejlesztették ki. Goldwasser és Sipser [23] munkájában olvashatunk arról, hogy az interaktív bizonyítási rendszerek esetén lényegtelen az, hogy a véletlen bit titkos, vagy nyilvános. A [64]cikkben található meg Shamir híres eredménye arról, hogy IP PSPACE-szel megegyezik. A

GI prob-

lémára adott zéró-ismeretu protokoll Goldreich, Micali és Wigderson munkájáig [20] nyúlik vissza. A faizomorzmusra vonatkozó 3-2. feladathoz lásd [34]-t is. A 3-4. feladatban említett rácsredukciós technikát lásd például [43]-ben. Az itt említett támadás Johan Håstad [25] munkájára nyúlik vissza, és Don Coppersmith [11] javította. történetébe, az Singh [66] könyve szép bepillantást nyújt a kriptológia fejlodésének kezdve a modern rejtjelezo eljárásokig. Például ott olvashatjuk, hogy a ókori gyökerektol brit Állami Kommunikációs Központ (Government Communications Headquarters; GCHQ) egyik különleges egysége, a Kommunikációs-elektronikai Biztonsági Csoport (Communi-

124


cations Electronics Security Group; CESG) azt állítja, hogy Ellis, Cocks és Williamson nevu munkatársai mind a 3.8. ábrán látható RSA-rendszert, mind a 3.7. ábrabeli DiffieHellmanprotokollt hamarabb feltalálták, mint Rivest, Shamir és Adleman, illetve hamarabb, mint Diffie és Hellman, érdekes módon fordított sorrendben. Az RSA-rendszer jószerével minden, a kriptográáról szóló könyvben le van írva. Az RSA elleni támadásokról, mint amilyen cikkekben. a 3.3. alfejezetben szerepel, átfogó listát találunk például a [6, 54] áttekinto Prímszámtesztek, mint amilyen a MR-algoritmus, valamint faktorizáló algoritmusok szintén sok könyvben megtalálhatók, például [19, 57, 68] -ben. Az erosen neminvertálható, asszociatív egyirányú függvények fogalma, amelyen az és Sherman3.11. ábrán látható titkos kulcscserére vonatkozó protokoll alapszik, Rivest-tol tól származik. Ennek a protokollnak a módosítása, amely digitális aláírásra alkalmas, Rabi akik [49] munkájukban azt is bebizonyították, hogy komnak és Sherman-nak köszönheto, mutatív, asszociatív egyirányú függvény pontosan akkor létezik, ha P

,

NP. Kétségtelen,

hogy az általuk konstruált egyirányú függvények sem nem totálisak, sem erosen nem invertálhatók, még P

,

NP fennállása esetén sem. Hemaspaandra és Rothe [28] megmutatták,

hogy totális, erosen nem invertálható, kommutatív, asszociatív egyirányú függvény pontosan akkor adódik, ha P

, NP teljesül (lásd a [5, 27] cikkeket is).

Az interaktív bizonyítási rendszerek és zéró-ismeretu protokollok területére vonatkozólag a legjobb és legátfogóbb forrást Goldwasser, Micali és Rackoff mutatták be [22] munkájukban, ez Goldreich könyvében [19] a 4. fejezet. Hasonlóképpen szép kimutatást találhatunk például Köbler és társai [35] és Papadimitriou [46] könyvében, valamint a [18, 21, 54] cikkekben. Az ArtúrMerlin-játékokat foként áttekinto Babai és Moran [3, 4], valamint Zachos és Heller [74] vizsgálták. [19] részletesen foglalkozik a zéró-ismeretu protokollok olyan változataival, amelyek található róluk például a technikai részletekben térnek el a 3.17. deníciótól. Némi ízelíto [18, 21, 54] dolgozatokban. A kriptográával foglalkozik magyar nyelvu könyvében Ködmön József [36], Buttyán Levente és Vajda István [8], valamint Simon Singh [66].

4. Bonyolultságelmélet

A 3. fejezetben kriptográa módszerek és protokollok szempontjából fontos algoritmusokkal ismerkedtünk meg, mint amilyen a square-and-multiply algoritmus. Az algoritmusok akkor boldogok, ha sikerül egy probléma hatékony megoldását eloállítaniuk. fejlesztoi Ennek során viszont sok fontos probléma sajnos megmakacsolja magát, és konok módon ellenáll minden kísérletnek, melynek célja hatékony megoldó algoritmus kifejlesztése lenne. Ilyen problémák például a Boole-kifejezések kielégíthetoség problémája, a párosítás és a grázomorzmus problémái, melyeket a fejezetben részletesen tárgyalunk. A bonyolultságelmélet egyik legfontosabb feladata ilyen és hasonló problémák kiszá akkor elémíthatósági bonyolultság szerinti osztályozása. Miközben az algoritmusfejleszto gedett, ha egy, a problémáját megoldó konkrét algoritmus fejlesztése során konkrét futási mellett meg tud orizni ido egy, a lehetoségekhez mérten legjobb felso bonyolultsági kor legjobb alsó korlát meghatározásán fálátot, a bonyolultságelméleti szakember egy leheto radozik. Az algoritmusok elmélete és a bonyolultságelmélet ilyen szempontból kiegészítik és alsó korlát egybeesik, akkor a problémát osztályoztuk. egymást. Ha a felso Annak bizonyítéka, hogy egy probléma nem oldható meg hatékonyan, gyakran negatív hatású és egyáltalán nem kívánatos. Van azonban a bizonyításnak egy pozitív aspektusa is: a kriptográa tárgykörében (lásd a 3. fejezetet) épp a rossz hatékonyság hiányában vagyunk érdekeltek. Annak bizonyítása, hogy egyes problémák csak rossz hatékonysággal oldhatók meg, mint például a faktorizálás probléma vagy a diszkrét logaritmus, titkosított üzenetek átvitelekor a biztonság növekedését jelentik. A 4.1. alfejezetben lefektetjük a bonyolultságelmélet alapjait, különös tekintettel a P és NP bonyolultsági osztályok denícióira. Nagyon fontos kérdés, hogy ez a két osztály különbözo-e vagy sem. Ez évtizedek óta a bonyolultságelmélet és az egész elméleti informatika központi kérdése. A mai napig sem a P

, NP sejtést, sem pedig P és NP egyenlosé-

ad az NP-teljesség elméletébe, gét nem sikerült bizonyítani. A 4.2. alfejezet rövid bevezetot amely ezzel a kérdéskörrel különösen intenzíven foglalkozik. A leghíresebb NP-teljes problémák egyike a SAT, az ítéletlogika kielégíthetoség problémája: kielégítheto-e egy adott Boole-formula igazságértékeket behelyettesítve változóiba, vagyis igazzá teheti-e valamely behelyettesítés? A SAT probléma NP-teljessége miatt nagyon valószínutlen, hogy SAT hatékony (és determinisztikus) megoldó algoritmussal ren delkezzen. A 4.3. alfejezetben bemutatunk SAT-hoz egy determinisztikus és egy valószínu ségi algoritmust, melyek mindketten exponenciális idoben muködnek. Futási idejük a gya szinten tartható még úgy is, hogy ezek korlatban fontos bemenetméretek mellett elviselheto az

126


4.1. Alapok

127

algoritmusok aszimptotikusan rossz hatékonyságúak, tehát nagyon nagy bemenetekre csillagászati méretu ráfordítást igényelnek. A 4.4. alfejezetben újra elovesszük a

GI

grázomorzmus problémát, amit a

3.1.3.

alfejezet 3.8. deníciójában ismertettünk, és a zéró ismeretu protokolloknál játszott szerepet. Ez a probléma azon NP-beli természetes problémák egyike, melyek valószínuleg (az P elfogadhatónak tun o

,

NP feltevés mellett) nem oldhatók meg hatékonyan, és nem is

NP-teljesek. Ilyen szempontból

GI

különleges helyzetet élvez az NP-beli problémák hal-

(angolul mazában. Az erre utaló jelek az úgynevezett alsóság-elméletbol

lowness theory) erednek, amit a 4.4. alfejezetben ismertetünk. Többek között megmutatjuk, hogy GI az NP-n belüli alsó-hierarchiában helyezkedik el, ami nagyban valószínusíti, hogy Ezen kívül megmutatjuk, hogy

GI

GI nem NP-teljes.

az SPP bonyolultsági osztályban fekszik, és ezáltal al-

sóbb ( low) az ismert valószínuségi bonyolultságosztályoknál. A formális megfogalmazást kerülve egy halmaz alsóbb egy C bonyolultsági osztálynál, ha mint orákulum, mint jós semmiféle hasznos információt nem szolgáltat a C-számítások számára. A fent nevezett következmény bizonyításához, annak belátásához, hogy

GI

alsóbb bizonyos bonyolultsági

osztályoknál, nagyon hasznosnak mutatkoznak egyes csoportelméleti algoritmusok.

4.1. Alapok A bevezetésben említettük, hogy a bonyolultságelmélet többek között alsó korlátok meghatározásával foglalkozik. Ennek nehézsége abban rejlik, hogy nem elég a vizsgált problémát megoldó egyetlen konkrét algoritmus futási idejét elemezni, hanem meg kell mutatnunk, algoritmus futási ideje legalább akkora, mint hogy a problémát megoldó összes elképzelheto a felmutatott alsó korlát. Ezek közé az algoritmusok közé olyanok is tartozhatnak, melyeket következoen lépésként az algoritmus fogalmát formátalán még ki sem találtak, ebbol elso lis és matematikailag pontos módon kell megragadnunk, máskülönben nem beszélhetünk az algoritmusok összességérol. elképzelheto formális algoritmus-modellre tettek javaslatot. Az 1930-as évek óta már sok különbözo Ezek a modellek ekvivalensek egymással olyan értelemben, miszerint bármelyik modell át alakítható egy tetszolegesen választott másik ilyen modellé. Kissé pongyolán fogalmazva ez a transzformáció felfogható mint egyfajta programnyelvek közti fordítás. Az eddigi ismert modellek ekvivalenciája alapján az úgynevezett Church-tézis felteszi, hogy minden egyes algoritmusmodell pontosan a - természeténél fogva elég bizonytalanul körülhatárolható -

intuitív kiszámítások fogalmát írja le. A bonyolultságelméletben használt szoká sos algoritmusmodell az 1936-ban Alan Turing (19121954) által bevezetett Turing-gép. A Turing-gép a számítógépek egy nagyon egyszeru absztrakt modellje, melyet a követke zokben szintaxisán és szemantikáján keresztül deniálunk. Eközben egyúttal bevezetünk kiszámíthatóságelméleti vezérgondolatot: a determinisztikusságot és a nemkét különbözo determinisztikusságot. Célszeruen eloször az általánosabb nem-determinisztikus Turing aztán speciális esetként közvetlenül adódnak a determinisztikus gépeket írjuk le, amibol Turing-gépek. a Turing-gép néhány technikai részletét és muködését Mindenek elott ismertetjük. Egy Turing-gép rendelkezik k darab mindkét irányban végtelen munkaszalaggal, melyek me zokre vannak felosztva. A mezokben betuk (jelek) állhatnak. Azt a tényt, hogy egy mezo üres, egy speciális jellel, a

-szimbólummal

jelöljük. A tényleges számítás a munkasza-

128


4.1. ábra. Turing-gép.

lagokon történik. Egy számítás kezdetekor a bemeneti szó egy meghatározott szalagon, a bemeneti szalagon található, aminek minden bemeneti szóhoz nem használt további mezoje a

jelet tartalmazza. A számítás befejeztével az eredmény egy másik meghatározott szala-

gon, a kimeneti szalagon jelenik meg. Minden szalaghoz egy-egy író-olvasó fej férhet hozzá, amely a gép minden lépésében felülírhatja az aktuálisan olvasott betut, ezután elmozdulhat jobbra vagy balra, illetve állva maradhat az aktuális mezon. egy mezot Eközben a gép ak memóriájában (véges állapotú vezérloegység) tuális állapota megváltozhat, melyet a belso 1

feljegyez. A 4.1. ábrán egy két szalagos Turing-gép látható. 4.1. deníció (a Turing-gép szintaxisa). Egy k szalagos nemdeterminisztikus Turing-gép

= (Σ, Γ, Z, δ, z0 , , F) hetes, ahol Σ a bemeneti ábécé, Γ a munka ábécé (szalagjelek) melyre Σ ⊆ Γ, Z véges állapothalmaz, ahol Z ∩ Γ = ∅, δ : Z × Γk → P(Z × Γk × {L, R, N }k ) az átmenetfüggvény, z0 ∈ Z a kezdoállapot, ∈Γ−Σ az üres jel és F ⊆ Z a végállapotok halmaza. P(S ) egy S halmaz hatványhalmazát jelöli, (röviden k-szalagos NTM) egy M

tehát S összes részhalmazának halmazát. Minden z, z (z, a)

0

∈

Z, x

∈ {L, R, N } és a, b ∈ Γ mellett (z0 , b, x) ∈ δ(z, a) helyett a rövidített

0

7→ (z , b, x) jelölést is használhatjuk. Ha az aktuális állapot z, a fej pedig egy

a feliratú

mezon áll, akkor a fenti Turing-gép parancs a következo lépések végrehajtását jelenti:

• • •

a felülírását b-vel,

0

egy új z állapot felvételét és az x

∈ {L, R, N }-nak

megfelelo fejmozgást, azaz egy mezonyi lépést balra (L, az angol

left után), vagy egy lépést jobbra (R, azaz right), vagy a fej helyben marad az (N mint neutral, semleges). aktuális mezon A k szalagos determinisztikus Turing-gép (röviden a k-szalagos DTM) speciális esetéhez akkor jutunk, ha a A k

=

δ átmenetfüggvény Z × Γk -ról Z × Γk × {L, R, N }k -ra képez.

1 esetben az 1-szalagos Turing-gépekhez jutunk, melyeket NTM-ként, illetve

DTM-ként rövidítünk. Minden k-szalagos NTM illetve k-szalagos DTM szimulálható meg egy szalagos Turing-géppel, amelynél a számítási ido legfeljebb négyzete az eredetifelelo nek. Ésszeru lehet több szalag használata, amennyiben a hatékonyság szerepét nem hanya-

1

Lehetséges további megkötések bevezetése is, például lehet a bemeneti szalag csak olvasható, illetve a kimeneti

szalag csak írható. Hasonlóképp a technikai részletek kidolgozásakor számos további megoldás lehetséges, megkövetelhetjük, hogy meghatározott fejek csak meghatározott irányba mozdulhassanak el, vagy a szalagok csak egyik irányban legyenek végtelenek és így tovább.

4.1. Alapok

129

golhatjuk el. A Turing-gépek felfoghatók mint olyan elfogadó automaták, melyek nyelveket (szóhalmazokat) fogadnak el. Emellett a Turing-gépek használhatók függvények kiszámításához is.

= (Σ, Γ, Z, δ, z0 , , F) egy NTM. M ∈ Γ∗ Z Γ∗ szó. Ha k = αzβ, akkor αβ jelentése az aktuális szalagfelirat (az aktuális szó a fej által már meglátogatott szalagrészrol), a fej β elso szimbólumán 4.2. deníció (a Turing-gép szemantikája). Legyen M

egy kongurációja egy k

áll, z pedig az M aktuális állapota.

K M = Γ∗ Z Γ∗ halmazára deniálunk egy ` M bináris relációt, amely 0 ∈ K M kongurációba vezeto átmenetet írja le a δ átme∗ netfüggvény segítségével. Legyen minden α és β Γ -beli szóra, ahol α = a1 a2 · · · am és β = b1 b2 · · · bn , m ≥ 0, n ≥ 1 és minden z ∈ Z-re:  0 0  a a · · · am z cb2 · · · bn , ha (z, b1 ) 7→ (z , c, N), m ≥ 0 és n ≥ 1 ,    1 2 0 0 a1 a2 · · · am cz b2 · · · bn , ha (z, b1 ) 7→ (z , c, R), m ≥ 0 és n ≥ 2, αzβ ` M     a a · · · a z0 a cb · · · b , ha (z, b ) 7→ (z0 , c, L), m ≥ 1 és n ≥ 1. M kongurációinak

∈ KM

a k

kongurációból k

1

m−1

2

m

2

n

1

Megvizsgálandó még két speciális eset: 1.

7→ (z0 , c, R) (tehát M 0 akkor a1 a2 · · · am zb1 ` M a1 a2 · · · am cz .

2.

Ha m

Ha n

=

1 és (z, b1 )

=

7→ (z0 , c, L) (tehát ` M z0 cb2 · · · bn .

0 és (z, b1 )

akkor zb1 b2

· · · bn

jobbra mozdul és egy

-szimbólumot

talál),

M balra mozdul és egy

-szimbólumot

talál),

Az M kezdokongurációja x bemenet mellett mindig z0 x, az M termináló kongurá-

αzβ alakúak, ahol z ∈ F és α, β ∈ Γ∗ . ∗ 0 ∗ 0 Legyen ` M reexív, tranzitív lezártja ` M . Eszerint k, k ∈ K M -re k ` M k akkor és csak akkor, ha létezik egy véges k0 , k1 , . . . , kt K M -beli konguráció-sorozat, melyre ciói x bemenet mellett pedig

k ahol lehetséges, hogy k k0

=

=

k0

= k0 ` M

=

kt

=

k1

`M · · · `M

kt

= k0 ,

0

k . Ha az M kezdokongurációja x bemenet mellett

0

z0 x, akkor ezt a sorozatot M(x) véges kiszámításának nevezzük, ha a k -beli állapot

végállapot, és azt mondjuk, hogy M megáll az x bemenetre. Az M által elfogadott nyelvet a következoképp deniáljuk: L(M)

= { x ∈ Σ∗ | z0 x `∗M αzβ, z ∈

F és

α, β ∈ Γ∗ }.

Az M termináló állapotainak F halmazát feloszthatjuk az F a elfogadó végállapotok és a F r

= Fa ∪ Fr és Fa ∩ Fr = ∅. Ebben az esetben = { x ∈ Σ∗ | z0 x `∗M αzβ, z ∈ Fa és α, β ∈ Γ∗ } az M által elfogadott nyelv. ∗ ∗ ∗ Az M kiszámít egy f : Σ → ∆ szófüggvényt, amennyiben minden x ∈ Σ -ra és minden ∗ y ∈ ∆ -ra

elutasító végállapotok halmazaira, ahol F L(M)

∈ D f ⇐⇒ M az x bemenet mellett véges sok lépésben megáll,

1.

x

2.

minden x

∈ D f -re:

f (x)

= y ⇐⇒ z0 x `∗M

zy egy megfelelo z

∈

F-re,

ahol D f az f értelmezési tartományát jelöli. Azokat a szófüggvényeket, melyeket egy Turinggép kiszámít, kiszámítható szófüggvényeknek nevezzük. Egy f : mítható, ha egy g : {0, 1, #}

∗

Nk → N függvény kiszá-

→ {0, 1}∗ ,

g(bin(x1 )#bin(x2 )# · · · #bin(xk ))

= bin( f (x1 , x2 , . . . , xk ))

130

4. Bonyolultságelmélet (z0 , a) (z1 , a) (z1 , b) (z1 $) (z2 , b) (z2 , c)

7→ 7 → 7 → 7→

(z1 , $, R)

(z2 , $)

(z5 , c)

(z3 , c, R)

(z5 , $)

(z4 , , L)

(z5 , b)

(z1 , $, R)

7→ 7 → (z3 , ) → 7 (z4 , $) → 7

(z2 , $, R)

(z3 , c)

(z4 , $, L)

(z5 , a)

7→ 7 →

(z2 , b, R)

(z4 , )

(z6 , , R)

(z5 , )

(z3 , $, R)

(z4 , c)

(z5 , c, L)

(z0 , $)

(z1 , a, R) (z2 , $, R)

4.2. ábra. Az M Turing-gép L

Z

7→ 7 →

7→ 7→ 7→ 7→

(z5 , c, L)

7→ 7→

(z0 , , R)

(z5 , $, L) (z5 , b, L) (z5 , a, L)

(z0 , $, R)

= {an bn cn | n ≥ 1} nyelvhez tartozó δ parancsai.

Teendo

Jelentés

z0

kezdoállapot

új ciklust kezdeni

z1

felismertük a-t

b-t megkeresni a következo

z2

együttesen felismertük a, b-t

c-t megkeresni a következo

z3

a, b, c ki van írva

megkeresni a jobb oldali szélt

z4

jobb oldali szélre értünk

visszalépni és ellenorizni, hogy minden a, b, c ki van-e írva

z5

a teszt sikertelen

visszalépni a bal szélre és új ciklust kezdeni

z6

a teszt sikerült

elfogadás

4.3. ábra. Az M állapotainak értelmezése.

által deniált g szófüggvények segítségével kiszámítható. A bin(n) jelölés az n

∈ N kettes = 10001.

számrendszerbeli ábrázolását jelenti felvezeto nullák nélkül, mint például bin(17)

kongurációval rendelkezhet, Mivel egy NTM minden kongurációja több rákövetkezo ezért természetesen adódik egy kiszámítási fa, melynek gyökere a kezdokonguráció, levelei pedig a termináló kongurációk. A fák speciális gráfok (lásd a 3.8. deníciót a 3.1.3. állnak. Az M kiszámítási pontban, valamint a 3-2. feladatot), tehát csúcsokból és élekbol

0

fájának csúcsai megfelelnek az M x bemenet melletti kongurációi. Két k és k kongu-

0

ráció között pontosan akkor vezet egy irányított él k-ból k -be, ha k kiszámítási fájában egy k0

`M

k1

`M · · · `M

kt

`M · · ·

`M

0

k . Egy út az M

konguráció-sorozat, tehát M(x)

egy számításának felel meg. Egy NTM kiszámítási fája tartalmazhat végtelen utakat. Egy DTM esetében a kezdokonguráció kivételével minden kongurációt egyértelmuen (deter o kongurációja, ezért a kiszámítási fa elfajul egy minisztikusan) meghatározza a megeloz lineáris lánccá. A lánc a kezdokongurációval indul, és amennyiben a gép megáll az adott esetben pedig a lánc végtelen. bemenetre a termináló kongurációval végzodik, ellenkezo 4.1. példa.

L Turing-gép. Legyen egy L nyelv a következo:

= {an bn cn n ≥ 1}.

Egy, az L nyelvet

elfogadó Turing-gép deníciója az M ahol a

= ({a, b, c}, {a, b, c, $, }, {z0 , z1 , . . . , z6 }, δ, z0 , , {z6 }),

δ átmenetfüggvénynek megfelelo Turing-gép parancsok listáját a 4.2. ábra tartalmazza. A 4.3.

ábra egyenként jellemzi az M állapotait azok jelentésével, valamint a hozzájuk tartozó elvégzendo lépésekkel.

A bonyolultságelmélet szakemberei alapos emberek, szívesen teszik rendbe, foglalják

4.1. Alapok

131

rendszerbe a fontos problémák óriási, változatos halmazát. Ezen cél érdekében osztályoz zák és katalogizálják a problémákat, majd bonyolultsági osztályokba sorolják oket. Minden egyes ilyen osztályba olyan problémák kerülnek, melyek a megoldásukhoz egy meghatározott bonyolultsági mérték szerint nagyjából azonos ráfordításokat igényelnek. A legelterjedtebb bonyolultsági mértékek az idomérték (egy algoritmus által a megoldáshoz szükséges lépések száma) és a tármérték (a számítógépen szükséges tárhely). Mi most az idomérték tárgyalására szorítkozunk. fogalmán az elvégzett lépések száAz algoritmus által a megoldáshoz szükséges ido mát értjük, mint a bemenet méretének függvényét. Formális modellünk, a Turing-gép esetében egy lépés a Turing-gép

δ

átmenetfüggvényének egyszeri alkalmazását jelenti, tehát

a számítás egy kongurációjának átmenetét a következobe. Esetünkben a hagyományos legrosszabb eset bonyolultsági modell vizsgálatára szorítkozunk. Ennek megfeleloen egy Turing-gép idofüggvényéhez a lehetséges tetszoleges n hosszú bemenetek közül azokat a hatású bemeneteket vizsgáljuk, melyek mellett a gép a legtöbb lépést igényli tehát a dönto legrosszabb esetet feltételezzük. Ezzel ellentétben átlagos eset bonyolultság esetén egy al goritmus várható futási idejét mint egy (tetszolegesen választott méretu bemenethez adott) átlagot kezeljük. valószínuségi eloszlásnak megfelelo A következokben deniáljuk a determinisztikus és nemdeterminisztikus idobonyolultsági osztályokat. 4.3. deníció (determinisztikus és nemdeterminisztikus idobonyolultság).

•

⊆ Σ∗ , valamint legyen x ∈ Σ∗ egy bemenet. DeniálΣ∗ -ból N-be képez a következoképp:

Legyen M egy DTM, melyre L(M) juk az M(x) idofüggvényét, amely

( Time M (x)

=

m,

ha M(x) pontosan m

nem deniált

egyébként .

+ 1 kongurációval rendelkezik

N → N függvényt:   max x:| x|=n Time M (x), ha Time M (x) deniált minden    | x| = n méretu x-re , =     nem deniált egyébként .

Deniáljuk a time M :

time M (n)

•

Legyen M egy NTM, melyre L(M) amely juk az M(x) idofüggvényét,

( =

TIMEM x

min{Time M (x, α) | M az

TIMEMn

•

Legyen t egy

α úton elfogadja x-et},

nem deniált,

Deniáljuk az NTime M :

     =    

⊆ Σ∗ , valamint legyen x ∈ Σ∗ egy bemenet. DeniálΣ∗ -ból N-be képez a következoképp: ha x

∈

L(M),

egyébként.

N → N függvényt:

max x:| x|=n NTime M (x)

ha NTime M (x) értelmezve van minden olyan

nem deniált,

egyébként.

x−re, melyre, | x|

=n,

N-bol N-be képezo kiszámítható függvény. Deniáljuk a determinisztikus

,

132

4. Bonyolultságelmélet t(n) n

n

= 10

= 20

n

n

= 30

n

= 40

n

= 50

n

= 60

.00001 mp

.00002 mp

.00003 mp

.00004 mp

.00005 mp

.00006 mp

2

.0001 mp

.0004 mp

.0009 mp

.0016 mp

.0025 mp

.0036 mp

3

.001 mp

.008 mp

.027 mp

.064 mp

.125 mp

.256 mp

5

.1 mp

3.2 mp

24.3 mp

1.7 perc

5.2 perc

13.0 perc

n

.001 mp

1.0 mp

17.9 perc

12.7 nap

n

.059 mp

58 perc

6.5 év

3855 évszd

n n n 2 3

35.7 év 2

· 108

366 évszd 1.3

évszd

· 1013

évszd

4.4. ábra. Néhány polinomiális és exponenciális idofüggvény összevetése.

és a nemdeterminisztikus idobonyolultsági osztályokat t idofüggvény mellett a következoképp:

( DTIMEt

=

A

( NTIMEt

•

=

A

A

=

minden n A

)

L(M) egy M DTM-el és

=

, )

∈ N-re time M (n) ≤ t(n)

L(M) egy M NTM-el és

minden n

∈ N-re ntime M (n) ≤ t(n)

.

Legyen IPol az összes polinom halmaza. Deniáljuk a P és NP bonyolultsági osztályokat a következoképp: P

=

[ DTIMEt

és

t∈IPol

NP

=

[ NTIMEt

.

t∈IPol

DPTM-mel illetve NPTM-mel jelöljük a polinomiális ideju DTM-eket illetve NTM-eket.

Miért is olyan fontosak a P és az NP polinom ideju osztályok? Nyilvánvaló, hogy az ex hatékonynak. A 4.4. ábponenciális futási ideju algoritmusok általában bajosan nevezhetok rán összehasonlítjuk néhány polinomiális és exponenciális idofüggvény növekedési ütemét, indugyakorlati szempontból fontos bemeneti méretekre. Ehhez egy olyan számítógépbol lunk ki, amely másodpercenként egymillió muvelet elvégzésére képes. Látható, hogy míg a = 60 méretéig elfogadható ido alatt eloállítják

polinomiális ideju algoritmusok a bemenet n az eredményt, addig például egy t(n) szerényebb, n

=

=

n

3

futási ideju algoritmus a bemenet viszonylag

30 méreténél 6 évnél is tovább dolgozna, az n

már majdnem 400 évezredre, és körülbelül n

=

=

40 méretu problémákhoz

pedig valóban csillagászati mértéku 50-tol

idore lenne szüksége. o Az utóbbi évtizedekben a számítógéptudományok és a hardver-technológia meggyoz fejlodését gyelhettük meg. Ha azonban fel is tesszük, hogy a gyorsabb és gyorsabb processzorok fejlesztési üteme megmarad az eddigi szinten, a 4.5. ábra szerint ez sem segít lényegesen az exponenciális futási ideju algoritmusok teljes végrehajtási idejének csökkentésében. Mi történne, ha egy olyan számítógépet használnánk, amely 100-szor vagy akár 1000-szer gyorsabb napjaink leggyorsabb számítógépeinél? Egy ti (n), 1

≤i≤

6 függvény-

hez jelölje Ni azt a maximális feladatméretet, amelyet egy ti (n) idofüggvény u algoritmus egy órán belül meg tud oldani. A 4.5. ábra alapján látható, hogy még ezerszeres sebességnövekedés is csak körülbelül tízzel növeli N5 értékét t5 (n)

=

n

2

esetén. Ezzel szemben

4.1. Alapok

133 ti (n)

Mai számítógép 100-szor gyorsabb 1000-szer gyorsabb

t1 (n)

=n

N1

100

t2 (n)

= n2

N2

10

· N1

t3 (n)

= n3

N3

4.64

t4 (n)

= n5

N4

2.5

t5 (n)

= 2n

N5

N5

+ 6.64

N5

+ 9.97

t6 (n)

= 3n

N6

N6

+ 4.19

N6

+ 6.29

· N2 · N3

· N4

1000

· N1

31.6

· N2

10

· N3

3.98

· N4

4.5. ábra. Mi lenne, ha a számítógépek gyorsabbak lennének?

5

egy n

idofüggvény u algoritmus ugyanekkora sebességnövekedést feltételezve hozzáveto-

leg négyszer nagyobb problémákat tud megoldani egy óra alatt. dogma azt a széles körben elterjedt nézetet fogalmazza meg, miszerint A következo a polinomiális ideju algoritmusok hatékonynak tekinthetok, míg a csak exponenciális alsó algoritmusok kimondottan rosszak, hatékonynak nem nevezhetok. korláttal rendelkezo 4.4. dogma. A polinomiális ido a hatékonyság intuitív fogalmának felel meg. Az exponenciális ido a rossz hatékonyság intuitív fogalmának felel meg. Természetesen egy dogma mindig is csak egy dogma marad, ennélfogva 4.4.-et is kri77

10

tikusan kell szemlélnünk. Egy n nézve egy

N

lépésben dolgozó algoritmus például ugyan formálisan

feletti, polinom lépésszámú algoritmus, de a polinom fokszáma éppen olyan

összes atom mostanság becsült darabszáma. nagy, mint az egész látható univerzumban lévo Emiatt egy ilyen algoritmus egyáltalán nem hatékony, használata még a legkisebb problémaméret mellett is gyakorlatilag értelmetlen. Másrészt viszont egy 2

0.00001·n

exponenciális

idokorlát éppenséggel elfogadható lehet a gyakorlatban fontos problémaméretek mellett. Természetesen, ha valamikor is jelentkezik az exponenciális növekedés, a 0.00001

·n

ki-

esetében ez eloször tevo csak nagyon nagy n mellett esedékes. Ez a két szélsoséges eset a A természetes P-beli problémák lenyuvalóságban mindenesetre szinte soha nem fordul elo. többsége megoldható olyan algoritmussal, aminek futási ideje alacsony fokú polinom, gözo 2

3

mint O(n ) vagy O(n ). Negyed-, ötöd- vagy ennél magasabb fokú polinomok csak nagyon ritkán lépnek fel. A P osztály a 4.4. dogma szerint pontosan a hatékonyan megoldható problémákat tartalmazza. Az NP osztály sok olyan, gyakorlatban fontos problémát tartalmaz, melyekre a mai napig nem találtak hatékony megoldó algoritmust, mint például a kielégíthetoség és a grázomorzmus problémái. Ezeket a 4. fejezetben részletesen vizsgáljuk. A kérdés, hogy a P és NP osztályok azonosak-e, szintén máig megoldatlan. Ez a híres PNP probléma, amit tekinthetünk az elméleti informatika legfontosabb máig nyitott kérdésének. A kérdés különösen nagy szerepet játszik a kriptográa területén, mivel a legtöbb ma használatos titkosítási rendszer azon a feltevésen alapszik, hogy bizonyos problémák nehezen megoldhatók. Ide tartoznak a faktorizálási probléma és a diszkrét logaritmus problémája, melyeket a 3. fejezetben vizsgálunk részletesebben. Amennyiben sikerülne a P

= NP egyenloséget bi-

zonyítani, minden ilyen titkosítási rendszer elvesztené biztonságos tulajdonságát, és ezáltal haszontalanná válna. A PNP kérdés különösen nagy szerepet játszott az NP-teljesség elméletének létrejötté-

134


ben. Ez az elmélet módszereket biztosít a legnehezebb NP-beli problémák alsó korlátainak bizonyításához. Egy ilyen bizonyításnál egyetlen egy nehéz NP-beli problémából kell kiindulni. Számos további NP-probléma NP-nehézsége ezután egy visszavezetés segítségével következik, ami során egy problémát egy másikká alakítunk át. Érdekes módon mivel ezek visszavezetések léteznek olyan hatékony algoritmusok, melyekkel lehetové válik a nehéz problémák NP-nehézségének bizonyítása. Azokat a problémákat, melyek NP-beliek és NP-nehezek, NP-teljes problémáknak nevezzük. Ezek nem tartozhatnak P-be, ezért nem is lehetnek hatékonyan megoldhatók, kivéve, ha esetleg P

=

NP fennáll. Az NP-teljesség

elméletét a 4.2. alfejezetben mutatjuk be.

Gyakorlatok 4.1-1. Be lehet-e bizonyítani a Church-tézist? A választ indokoljuk. M Turing-gépet. 4.1-2. Tekintsük a 4.1. példában szereplo a. Adjuk meg M kongurációinak sorozatát x

=

3

3

a b c

2

,

illetve y

=

3

3

3

a b c

bemenet

mellett. b. Bizonyítsuk be M helyességét, azaz igazoljuk az L(M)

= {an bn cn | n ≥ 1} egyenlosé-

get. c. Adjunk becslést az M futási idejére. 4.1-3. Mutassuk meg, hogy a 3.8. denícióban szereplo

GI és GA problémák NP-beliek.

4.2. NP-teljesség Az NP-teljesség elmélete módszereket biztosít NP-beli problémák alsó korlátainak igazolásához. Egy NP-probléma NP-ben teljes, ha az osztály legnehezebb problémái közé tartozik. Ennél fogva egy X probléma NP-nehézségének belátásához NP összes problémáját össze kell hasonlítani X-el, és meg kell mutatni, hogy X legalább olyan nehéz, mint az aktuálisan vizsgált másik probléma. Két probléma bonyolultsága polinomiális ideju visszavezeté össze egymással. A sok különbözoképp sek segítségével mérheto deniálható visszavezet hetoségi típus közül számunkra most az úgynevezett sok-egy-visszavezethetoség lényeges, amit

p

≤m -vel

fogunk jelölni. Mivel ebben az alfejezetben nem foglalkozunk más vissza-

vezethetoségi osztállyal, ezért egyszeruen

beszélünk. A 4.4. alfevisszavezethetoség-r ol jezetben általánosabb visszavezethetoségeket is megismerhetünk, az úgynevezett Turingvisszavezethetoséget és az (eros) nemdeterminisztikus Turing-visszavezethetoséget. 4.5. deníció (visszavezethetoség, NP-teljesség). mazra (formálisan A

p

≤m

∈ Σ∗

Egy A halmaz visszavezetheto egy B hal-

B, ha létezik egy polinomiális idoben kiszámítható r függvény, p

∈ A ⇐⇒ r(x) ∈ B. Egy B halmaz ≤m -nehéz NP-ben, p p ha minden A ∈ NP halmazra A ≤m B. Egy B halmaz ≤m -teljes NP-ben (vagy röviden p NP-teljes), ha B ≤m -nehéz NP-ben és B ∈ NP. melyre minden x

esetén x

Egy adott X probléma NP-nehézségének bizonyításhoz látszólag végtelen sok hatékony algoritmus szükséges, majd minden egyes ilyen NP-beli problémát hatékonyan vissza kell kutatási eredmény szerint azonban nem szükséges végtelen sok vezetni X-re. Egy alapveto ilyen visszavezetés elvégzése, elég egyetlen NP-teljes V probléma visszavezetése X-re. Miaz

p

≤m -visszavezethetoség tranzitív (lásd a 4.2-2. gyakorlatot) valamint V NP-nehéz, ezért p p A ≤m V ≤m X visszavezetéssel következik X NP-nehézsége. Itt A befutja az NP-beli

vel a

4.2. NP-teljesség

135

nyelveket. 1971-ben Stephen Cook megtalálta az ilyen NP-teljes problémák egyikét, az ítéletlo gikai kifejezések kielégíthetoségének problémáját, amit röviden SAT-tal jelölünk. Sok NP teljességi bizonyításhoz elég, ha a kielégíthetoség probléma egy úgynevezett

3-SAT

meg-

szorításából indulunk ki, ahol az adott Boole-formulák konjunktív normálformában állnak

3-SAT

rendelkezésre, és minden klóz pontosan három literált tartalmaz. A

is NP-teljes.

A diszjunktív normálformájú Boole-kifejezések kielégíthetoségének eldöntése hatékonyan megoldható.

 és az  Boole-konstansokat rendre 0∈ {0, 1} minden i-re. A változókat és azok negáltját literáloknak nevezzük. Egy ϕ Boole-formula kielégítheto, ha létezik ϕ változóinak olyan behelyettesítése, ami a formulát igazzá teszi. Egy ϕ Boole Vn Wk formula konjunktív normálformájú (röviden KNF,) ha ϕ(x1 , x2 , . . . , xm ) = ` i= 1 j=1 i, j Wk formájú, ahol az `i, j literálok { x1 , x2 , . . . , xm }-bol valók. A literálok ` diszjunkcióit ϕ j=1 i, j klózainak hívjuk. Egy ϕ Boole-formula k-KNF, ha ϕ KNF és ϕ minden klóza pontosan k 4.6. deníció (kielégíthetoség probléma). A

val és 1-gyel jelöljük. Legyenek x1 , x2 , . . . , xm Boole-változók, tehát xi

i

i

literált tartalmaz. Deniáljuk a következo két problémahalmazt: SAT

3-SAT

= {ϕ | ϕ kielégítheto KNF Boole-formula} , = {ϕ | ϕ kielégítheto 3-KNF Boole-formula} .

két formula kielégítheto Boole-kifejezés (lásd még a 4.2-1. 4.2. példa. Boole-kifejezések. A következo gyakorlatot):

Itt

ϕ(w, x, y, z)

=

(x

∨ y ∨ ¬z) ∧ (x ∨ ¬y ∨ ¬z) ∧ (w ∨ ¬y ∨ z) ∧ (¬w ∨ ¬ x ∨ z) ;

ψ(w, x, y, z)

=

(¬w

∨ x ∨ ¬y ∨ z) ∧ (x ∨ y ∨ ¬z) ∧ (¬w ∨ y ∨ z) ∧ (w ∨ ¬ x ∨ ¬z) .

ϕ egy 3-KNF formula, ezért ϕ 3-SAT-beli. Ezzel szemben ψ nem 3-KNF, mivel az elso klóz négy ψ ugyan SAT-beli, de nem 3-SAT-beli.

literált tartalmaz, ezért

között adott meg A 4.7. tétel Cook korábban említett eredménye, amelyben az elsok SAT-tal egy NP-teljes problémát. A bizonyítás alapötlete szerint kódoljuk egy tetszoleges M NPTM muködését egy

ϕ M, x

Boole-formulával úgy, hogy

ϕ M, x

pontosan azon x-ekre le-

az x bemenettel, melyeket az M elfogad. A kielégíthetoség gyen kielégítheto problémából kiinduló visszavezetésekhez sokszor célszeru, ha az adott kifejezések szigorú 3-KNF formá ban állnak rendelkezésre. Ez megoldható, mivel SAT visszavezetheto

3-SAT-ra, ezért 3-SAT

fejezetét). szintén NP-teljes (lásd az Új algoritmusok megfelelo 4.7. tétel (Cook). A SAT és

3-SAT problémák NP-teljesek.

Napjainkra több ezer NP-teljes problémát találtak már. Mi most a nagy választékból szemléltetési célokra a háromdimenziós párosítás problémát választjuk ki, és egy

3-SAT-

ból való visszavezetéssel megmutatjuk NP-teljességét. A párosítási feladatoknál egymás párokat vagy hármasokat alakítunk ki. Egy kétdimenziós (vagy bipartite) párosítás hoz illo párok halmaza, egy háromdimenziós (vagy tripartite) párosítás, más néven egymáshoz illo hármasok halmaza. Kétdimenziós párosítások jól szemléltethehármasítás egymáshoz illo (irányítatlan) gráfokkal, lásd bovebben tok a 3.8. deníciót.

136

4. Bonyolultságelmélet ¯ b 1 f2

m1

f3

m2

b1 f1

b2

m2 f2

m1 ¯ b 4

f1

m3

f4

m4

¯ b 2 m3

f4 f3

m4 b4

b3 ¯ b 3

4.6. ábra. Balra: A házasítás probléma megoldása. Jobbra: Az R reláció igazságérték-komponensei.

4.8. deníció (kétdimenziós párosítás probléma).

Egy 2n csúccsal rendelkezo G gráf pá-

ros, ha a csúcshalmaza két n méretu, diszjunkt V1 és V2 halmazra osztható, ahol mindketto független halmaz, azaz sem V1 , sem pedig V2 csúcsai nincsenek élekkel összekötve. Csak V1 és V2 -beli csúcsok között fordulhat elo él. G tökéletes kétdimenziós párosítása egy olyan n csúcsú M (v, x

∈ V1 ,

⊆

w, y

{v, w} és { x, y} M-beli élre , y. A kétdimenziós párosítás probléma kérdése az, hogy

E(G) halmaz, melynél minden két különbözo

∈ W2 ) v ,

x és w

egy adott páros gráfhoz létezik-e kétdimenziós párosítás.

4.3. példa. (Kétdimenziós párosítás probléma.)

Képzeljünk el n darab házasodni szándékozó höl-

gyet és n darab házasodni szándékozó fért, akik egy páros gráf csúcsait alkotják. A V (G) csúcshalmaz tehát két részre bomlik, Vvolegény V (G)

=

Vmenyasszony

∪ Vvolegény

= { f1 , f2 , . . . , fn } és Vmenyasszony = {m1 , m2 , . . . , mn }, valamint ∩ Vvolegény = ∅. A Vvolegény -beli és a Vmenyasszony

és Vmenyasszony

beli csúcsokat élek köthetik össze, de nincs él Vvolegény -beli csúcsok vagy Vmenyasszony -beli csúcsok ha rendezheto n darab esküvo az n menyasszony és között. Egy kétdimenziós párosítás akkor áll elo, idézve) n volegény között úgy, hogy (Garey és Johnson muvéb ol

valamint a poligámia elkerülendo, mindenki elfogadható feleséget illetve férjet kapjon. Emiatt az értelmezés miatt a kétdimenziós párosítás problémát házasítás problémának is nevezzük. A 4.6. ábrán (bal oldalon) látható a házasítás

probléma egy megoldása, ahol a vastagon nyomtatott élek a négy új házaspárt jelölik. Ismert, hogy a házasítás probléma hatékonyan megoldható. A valós élet gyakran igazolja az állítást: Házasodni könnyu!

A következokben általánosítjuk a páros gráfokat és a kétdimenziós párosításokat három dimenzióra. 4.9. deníció (háromdimenziós párosítás probléma). Legyen U , V és W három, páronként

⊆ U × V × W egy hármas reláció, tehát (u, v, w) hárma∈ W . R egy háromdimenziós párosítása egy n méretu különbözo (u, v, w) és (u , v , w) hármasra u , u, v , v és

diszjunkt, n méretu halmaz. Legyen R sok halmaza, ahol u M w

∈ U, v ∈ V

és w

⊆ R halmaz, ahol minden két , w. Ez azt jelenti, hogy egy háromdimenziós párosítás semelyik két eleme nem illeszked-

4.2. NP-teljesség

137

het egymáshoz valamely koordinátájában. Deniáljuk tehát a háromdimenziós párosítás problémát a következoképp:

3-DM

=

     (R, U, V, W )    

U , V és W páronként diszjunkt, nem üres, azonos méretu halmaz és R

⊆U ×V ×W

egy hármas reláció, amely

egy |U | méretu háromdimenziós párosítást tartalmaz

     .    

4.4. példa. Háromdimenziós párosítás probléma. Kilenc hónap telt el. Egy reggel az n darab boldog születik, akik hangos sírás házastárspárunk útra kel a kórházba. Néhány órával késobb n csecsemo mellett rögtön jelentosen megnövelik szüleik életének bonyolultságát például azáltal, hogy elcseré lik a névtáblájukat, amin rajta áll, hogy melyik szülopárhoz tartoznak. Ez nagy zurzavarhoz vezet a szüloszobában. Még tovább rontva a helyzeten az újdonsült apák mindegyike talán az izgalmas szépségétol elcsábítva kijelenti, hogy sosem látta azt a hölpillanatoktól összezavarva és a többi no gyermekét hozta épp világra. Ehelyett hutlen gyet, aki makacsul kitart amellett, hogy az o módon mellett közvetlenül balra fekszik. A káosz kijelenti, hogy egy másik hölgy a házastársa, aki az elso ovére teljes! A szüloszoba fon nehéz problémával szembesül: melyik szülopároshoz melyik csecsemo tartozik? Másképp fogalmazva n darab boldog, harmonikus és páronként diszjunkt családot kell újra összeállítania, tehát egy háromdimenziós párosítás feladatot kell megoldania n édesapa, n édesanya és között. Nem csoda, hogy szemben a kétdimenziós párosítás feladat hatékony megoldn csecsemo ovérnek hatóságával a 3-DM probléma NP-teljes. Végül a fon 3n darab vérvételt és kinomult DNS teszteket kell elvégeznie, ám ennek tárgyalása már meghaladná könyvünk terjedelmét. Ismét átfogalmazva a 3-DM NP-teljességét a valós élet tapasztalataira: Ha jönnek a gyermekek, nagyon nehéz feladat boldog és harmonikus, diszjunkt családokban élni!

4.10. tétel. A 3-DM probléma NP-teljes. Bizonyítás. A 4.2-4. gyakorlat szerint könnyen belátható, hogy 3-DM NP-beli. A 3-DM NP nehézségének bizonyítása mögötti intuíciót legkönnyebb akkor megérteni, ha eloször meg ovér nézzük, hogyan jár el a szüloszobai fon a háromdimenziós párosítás probléma megoldá sakor. Eloször is mindenkit ellát a teremben egy névtáblával, olyannal, ami megbízhatóan nem fog ismét eltunni. Feltesszük, hogy az édesanyák az m1 , m2 , . . . , mn , az édesapák az pedig a b1 , b2 , . . . , bn elnevezéseket kapják. Ezután a fon ovér f1 , f2 , . . . , fn , a csecsemok ¯ ,b ¯ ,...,b ¯ } csecsemot ¯ a b -vel megegyezo állít elo, ahol minden egyes b egy újabb adag {b 1 2 n i i 2

klón , azaz ugyanúgy néz ki, és a DNS-e bi -vel azonos öröklodési információkat tartalmaz. A 2n darab szülo egy belso kört formáz, Ezt elvégezve két kört alakít ki a 4n emberbol. körben az n csecsemo és n klónja helyezkedik amiben apák és anyák váltakoznak. A külso el, ugyancsak váltakozva. A két kör szomszédos személyei kapcsolatban állnak egymással úgy, ahogy a 4.6. ábra (jobb oldalon) n

= 4 esetében mutatja: minden apa két anyával és két

csecsemovel van összekötve. gondolatmenetben az i indexek modulo n értendok, A következo a példában n 3

Vizsgáljunk minden i-t, melyre i modulo n

= 4. Az

= 4.

fi -edik apa az mi−1 -edik anyával tartja

magát házasnak, és vele közös gyermekének pedig az (i

−

Ezzel szemben 1) csecsemot.

az mi anya ahhoz ragaszkodik, hogy o az fi apa felesége, és a közös gyermekük pedig az Mindkét ellentmondó állítást egy-egy háromszög szemlélteti a 4.6. ábrán i-edik csecsemo.

2

etikai kérdések szintén túlmutatnak A csecsemoklónozás technikai kérdései és az ezzel kapcsolatban felmerülo ezen könyv határain, ennélfogva szép csendben mellozzük oket. 3

A modulo n aritmetikáját a 3. fejezet végén, a 3-1. példával kapcsolatban ismertettük.

138


¯ (jobb oldalon), melyek csúcsai fi , mi−1 és b i−1 , illetve mi , fi és bi . A 2n darab háromszög ovérnek mindegyike egy-egy potenciális családot képez. A fon azt kell megállapítania, hogy mely háromszögek reprezentálják az eredeti n darab családot, és melyek nem. Az egyet len lehetoség n darab diszjunkt család létrehozására az, ha vagy minden háromszögbe egy ¯ klóncsecsemot vagy pedig minden háromszögbe egy b választunk. Azáltal, b csecsemot, i

i

ovér hogy a 3n vérvételt és a fentebb említett DNS-teszteket elvégezte, a fon meghozhatja ovér a helyes döntést és minden apához kijelölheti igazi feleségét és igazi gyermekét. A fon az n darab eredeti családot. A fennmaradó n darab csecsemot (és ez a tehát így állítja elo ovér fon módszerének szomorú oldala és a csecsemoklónozásé úgy általában) adoptálják, vagy árvaházakban helyezik el. A bonyolultságelmélettel foglalkozók nem nagyon értenek a DNS-tesztekhez vagy a klónozáshoz, szerencsére azonban a kielégíthetoség-problémát jól ismerik. A 3-DM prob-

3-SAT egy visszavezetését 3-DM-re. Legyen ϕ(x1 , x2 , . . . , x` ) = C1 ∧ C2 ∧ · · · ∧ Cn , ahol

léma NP-nehézségének belátásához deniáljuk

ϕ

adott

Boole-formula 3-KNF-ben, vagyis

ϕ minden C j klóza pontosan három literált tartalmaz. Eloállítandó polinomiális idoben egy ahol R ⊆ U × V × W egy hármas reláció a páronként diszjunkt, (R, U, V, W ) négyes 3-DM-bol, nem üres, azonos méretu U , V és W halmazokkal úgy, hogy

ϕ kielégítheto ⇐⇒ R egy |U | méretu, M háromdimenziós párosítást tartalmaz .

(4.1)

jellegu R különbözo hármasokból áll, melyek mögött mindig más és más szándék rejto zik. Azonos jellegu hármasokat elem-csoportokká, komponensekké fogunk össze. Az elso

ϕ formula változóinak olyan ϕ összes klózára nézve. Ennek

ilyen komponens azokból az R-beli hármasokból áll, melyek meghatározott hozzárendelését biztosítják, ami konzisztens

klózokban, akkor minden egyes megfeleloen ha ugyanaz a változó elofordul különbözo ilyen eloforduláshoz ugyanazt az igazságértéket kell hozzárendelni, ennélfogva ezeket az igazságérték-komponensnek nevezzük. alkotóelemeket R-bol Minden ϕ-beli xi változóhoz készítünk pontosan 2n darab U -beli b , b , . . . , bn és 1 2 ¯ i pedig ¬ x ¯i , b ¯i , . . . , b ¯ i elemet, ahol n a ϕ klózainak száma. A bi reprezentálja x , a b b i i n j j i

1

i

i

2

ϕ j-edik C j klózában. Mivel az összes literál nem fordul elo minden klózban, i ¯ i nem feleltetheto meg valamely ϕ-beli literál elofordulásának. Ezeezért néhány b j vagy b j

elofordulását

ken kívül minden

ϕ-beli xi változóhoz létrehozunk további i , f2i , . . . , fni elemet, melyek a 4.6. ábrán 1

és n darab W -beli f

=

alkotják, ha n i

i

i

i 1

n darab V -beli m

, mi2 , . . . , min

belso kört (jobb oldalon) lévo

4 és az ábrán nem szerepelnek a fenti indexek. Kapcsoljuk most össze i i ¯i és b elemeket egymással, ahogy a 4.6. jobb oldali

az m j , f j és b j , továbbá az f j , m

j−1

j− 1

ábráján vázoltuk. Az így létrehozott komponensek háromszögei megfelelnek az R hármai

i

körbol m és f csak azokban a komponensekben fordulnak elo, melyek sainak. A belso j j i ¯ i más komponensekben is körbol b és b az xi változónak felelnek meg, miközben a külso j j

elofordulhatnak. Formálisan az X igazságérték-komponensek X Xi

=

Fi

∪ Ti

minden

ϕ-beli

S`

i= 1

Xi alakúak, ahol

két halmaz által deniálva: xi -re, a következo

Fi

= {(bij , mij ,

fj) | 1

Ti

= {(b¯ ij , mij ,

f j+1 ) | 1

i

=

i

i

≤ j ≤ n}

;

≤ j < n} ∪ {(b¯ in , min ,

i

f1 )}

.

i

kör m és f elemei csak Xi komponenseiként szerepelhetnek, ezért R minMivel a belso j j den M párosítása pontosan n darab hármast tartalmaz, vagy minden ilyen hármast F i -bol,

4.2. NP-teljesség

139

Az F i és T i közötti választás biztosítja az xi változók megfevagy minden hármast T i -bol. leltetését az igaz vagy a hamis értékeknek. Mivel Xi tartalmazza

ϕ összes

xi elofordulását,

ezért ez a választás az egész formulára nézve konzisztens, következésképp R minden egyes M párosítása a

ϕ

formula egy hozzárendelését határozza meg úgy, hogy a hozzárendelés

minden xi változója akkor és csak akkor lehet igaz, ha M

ϕ

=

Sn

∩ Xi = T i .

Y j hármasok halmazát úgy, hogy minden Y j a j=1 C j klózát ellenorizze. megfelelo Ennek megfeleloen az Y komponenst R kielégíthetoségi Most hozzáillesztjük R-hez az Y

komponensének nevezzük. Minden C j klózhoz készítünk két v j

∈V

és w j

∈W

elemet, me-

Ezen kívül Y j három további elemet tartalmaz az lyek csak Y j -ben fordulnak elo.

S` i=1

{bij } ∪ {b¯ ij }

halmazból, melyek megfelelnek C j három literáljának, és R más kompo-

nenseiben is elofordulhatnak. Formálisan Y j -t

ϕ minden C j

halmazzal klózára a következo

deniáljuk: ¯ i , v , w ) | ¬x = {(bij , v j , w j ) | xi elofordul C j -ben} ∪ {(b j j i j

Yj

Mivel a v j és w j (1

≤

j

≤

elofordul C j -ben}

.

különn) elemek egyike sem szerepelhet az R halmaz Y j -tol

bármelyik másik hármasában, ezért R minden M háromdimenziós párosítása pontosan bözo i ¯ i , v , w )-t. Továbbá M ponegy Y -beli hármast tartalmaz, vagy (b , v , w )-t, vagy pedig (b j

j

j

j

j

tosan akkor tartalmaz egy Y j -beli hármast vagy ¯ i -t (ha b j

i b j -t

j

j

(ha xi elofordul C j -ben), vagy pedig

¬ xi fordul elo C j -ben) ha ez az elem nem fordul elo az M ∩ Xi hármasai között. Ez

pedig pontosan akkor következik be, ha az M igazságérték-komponensével meghatározott hozzárendelés kielégíti a C j klózt. Mostanra U pontosan 2n` elemet tartalmaz, azonban V és W mindössze n`

+ n elemu. − 1) elemmel V -t és W -t, amivel a három halmaz azonos méretu lesz. hozzáadjuk a vn+1 , vn+2 , . . . , vn` elemeket V -hez, valamint a wn+1 , wn+2 , . . . , wn`

Bovítsük további n(` Eloször is

halmazával: elemeket W -hez. Ezeken kívül kiegészítjük R-et hármasok következo Z

=

{(bij , vk , wk ) | 1 ≤ i ≤ ` és 1 ≤ j ≤ n és n + 1 ≤ k ≤ n`} ∪ {(b¯ ij , vk , wk ) | 1 ≤ i ≤ ` és 1 ≤ j ≤ n és n + 1 ≤ k ≤ n`} .

A vicc pedig az, hogy ha létezik R

−Z

egy háromdimenziós párosítása, és az összes,

R igazságérték- és kielégíthetoségi-komponenseivel biztosított feltétel teljesül, akkor ez a háromdimenziós párosítás U -ból pontosan n(`

− 1)

elemet szabadon hagy, amit aztán egy

egyértelmuen meghatározott Z-beli (vk , wk ) párral

párosíthatunk. Az R − Z háromdimen ziós párosításainak ilyen bovítése R egy háromdimenziós párosítását adja. Formálisan az U , V és W halmazokat a következoképp deniáljuk: U

=

{bij | 1 ≤ i ≤ ` és 1 ≤ j ≤ n} ∪ {b¯ ij | 1 ≤ i ≤ ` és 1 ≤ j ≤ n}

V

=

{mij | 1 ≤ i ≤ ` és 1 ≤ j ≤ n} ∪ {vk | 1 ≤ k ≤ n`}

W

=

;

;

i fj

{ | 1 ≤ i ≤ ` és 1 ≤ j ≤ n} ∪ {wk | 1 ≤ k ≤ n`} .

⊆ U ×V ×W relációt a R = X ∪Y ∪Z egyenloség határozza meg. Mivel R pontosan 2n`+ 2 `(` − 1) hármast tartalmaz, tehát polinomiális számút a ϕ formula méretére nézve, és ezért a visszavezetés polinomiális szerkezete könnyen meghatározható ϕ szerkezetébol,

Az R

3n + 2n R

idoben kiszámítható. A (4.1) állítás következik az R konstrukciója közbeni észrevételekbol.

140


(4.1) formális bizonyítását a 4.2-5. gyakorlat keretében az Olvasóra bízzuk.

Gyakorlatok behelyettesítést a 4.2. példában szereplo 4.2-1. Adjunk meg egy-egy kielégíto

ϕ és ψ Boole-

formulákhoz. 4.2-2. Mutassuk meg az A

p m

≤

p

p

≤m -visszavezethetoség tranzitivitását: (A ≤m

B

p

∧ B ≤m

C)

=⇒

C.

4.2-3. Adjunk meg egy SAT

p

≤m 3-SAT visszavezetést. Alakítsuk át hozzá egy adott Boole-

vagy háromnál több formula minden olyan klózát KNF klózzá, amely csak egy, csak ketto literált tartalmaz. Eközben a formula kielégíthetosége ne változzon. 4.2-4. Mutassuk meg, hogy a SAT és 3-DM problémák NP-beliek. (4.1) egyenloséget. 4.2-5. Lássuk be a 4.10. bizonyításban szereplo

4.3. Az ítéletlogika kielégíthet®ség-problémája 4.3.1. 3-SAT determinisztikus id®bonyolultsága 3-SAT megszorítása a 4.7. tétel alapján NP-teljes. = NP rögtön következne, ezért nagyon valószínutlennek tunik, hogy léteznének SAT-hoz vagy 3-SAT A SAT kielégíthetoség probléma és annak

Ha SAT esetleg P-beli lenne, akkor az általánosan elfogadott sejtéssel szemben P

hoz hatékony determinisztikus algoritmusok. Akkor viszont mekkora a legjobb algoritmu-

3-SAT-ra? Mivel a formula pontos szerkezete nyilvánvalóan befolyásolhatja 3-SAT problémára koncentrálunk, ahol minden klóz k-SAT-ra, pontosan három literálból áll. Az itt bemutatott eredmények közvetlenül átvihetok SAT megszorítására pontosan k literállal klózonként. 3-SAT naiv determinisztikus algorit musa a következoképp muködik: egy adott n-változós ϕ Boole-formulánál egymás után az sok futási ideje

ezért mi ebben a pontban a futási idot,

összes lehetséges behelyettesítést kipróbáljuk, kiértékelve a formulát a mindenkori értékekkel. Ha n

a 2

ϕ

esetben mind valamely behelyettesítésre igaz, az algoritmus elfogad, ellenkezo

behelyettesítést eredmény nélkül kipróbálja, és az algoritmus elutasít. Ez a módszer n

nyilvánvalóan O(2 ) idovel dolgozik. Megoldható-e a probléma gyorsabban? megmutatnánk hogyan, a következo kérIgen, megoldható gyorsabban is. De mielott dést szeretnénk feltenni: miért? Mi haszna annak, ha n

szorítjuk, valahová O(c )-re, ahol a c konstansra 1

3-SAT

n

idokorlátját felso O(2 ) alá

< c < 2 teljesül, ami még mindig egy ex-

annak az n0 küszöbértéknek ponenciális idokorlát? A haszon ott jelentkezik, hogy elérheto jellemzo lesz, azaz ahol az algorita hátrébb tolása, ahonnan kezdve az exponenciális ido mus abszolút futási ideje n

≥

A n0 méretu bemenetek mellett elviselhetetlenül nagyra no.

3-SAT

n

naiv algoritmusának O(2 ) korlátját hozzávetoleg annyira le lehet szorítani, hogy n egy O(c ) algoritmussal kétszeres méretu bemenetek feldolgozása válik lehetové azonos ido alatt, ami nagy gyakorlati jelentoséggel bír. Pontosan ez az eset áll fenn c

√

mellett, ahol az algoritmus O(

2

2n

)

=

=

√

2

≈ 1.4142

n

O(2 ) idoben dolgozik (lásd még a 159. oldalon a

4.9. táblázatot). A következokben bemutatunk egy algoritmust

3-SAT-hoz, amely a visszalépésen alapul.

Ez az algoritmusfejlesztési technika azon problémák megoldására alkalmas, ahol a meg tevodik oldás n darab alkotóelembol össze, melyeknél több választási lehetoség adódik.

4.3. Az ítéletlogika kielégíthet®ség-problémája Például

3-SAT

141

behelyettesítés, ami n darab igazságértékébol egy megoldása egy kielégíto

áll, továbbá minden ilyen igazságértékhez két választási lehetoség adódik:

 vagy ,

illetve 1 vagy 0. Az ötlet ezután abból áll, hogy az üres megoldásból (részleges behelyet lépésre, a V tesítés, ahol a változók nincsenek kitöltve) kiindulva lépésrol ´  ´  eljárás rekurzív hívásával a probléma mind nagyobb részleges megoldását hozzuk létre, amíg meg rekurziós fában nem találjuk a teljes megoldást, már amennyiben az létezik. A keletkezo

4

a gyökeret megjelöljük az üres megoldással, a probléma teljes megoldásai pedig a levelek szintjére kerülnek. Ha az algoritmus végrehajtása során megállapítjuk, hogy a rekurziós fa aktuális ága

halott, vagyis az addig konstruált részmegoldás semmi esetben sem egészít ki a probléma teljes megoldásává, akkor az eddig elért csúcs alatti részfát nyugodtan leheto oleg vághatjuk. A meghívandó eljárást visszaléptethetjük, próbálkozhatunk az eloz konstruált részmegoldás újabb folytatásával. Ennek a visszalépésnek köszönheti nevét a visszalépés algoritmikai elve. A rekurziós fa V ´  ´ -SAT(ϕ, β) 1 2 3

if

β-ban ϕ minden változója ki van töltve then return ϕ(β) elseif β hamissá teszi ϕ egy klózát

4 5

elseif V ´  ´ -SAT(ϕ, β0) then return 1 else return V ´  ´ -SAT(ϕ, β1)

A V ´  ´ -SAT algoritmus egy

β

inak

B Halott ág.

then return 0

6 7

tudunk megtakarítani. halott részeinek levágásával idot

ϕ

Boole-formula bemenet és

ϕ

valamely változó-

részleges hozzárendelése mellett egy Boole-értéket ad vissza: 1-et, ha a

megoldás egy minden változót tartalmazó

ϕ-t

β

parciális

hozzárendeléssé bovíthet és 0-át kielégíto o,

egyébként. A parciális hozzárendeléseket ebben az esetben a {0, 1} ábécé fölötti, n-nél nem hívása a V hosszabb szavaknak tekintjük. Az algoritmus kezdo ´  ´ -SAT(ϕ, λ), ahol

λ β parciális hozzárendelés ϕ valamely klózát hamissá teszi, akkor az már soha nem lesz kiegészítve egy ϕ-t kielégíto az üres hozzárendelés. Látható, hogy ha az elozetesen konstruált

hozzárendeléssé, a rekurziós fa aktuális csúcs alatti részfáját levágjuk (lásd még a 4.3-1. gyakorlatot). becsléséhez az adott A V ´  ´ -SAT futási idejének felso

ϕ

szolegesen választott C j klózt vizsgálunk. A

minden

β

ϕ

formulából egy tet-

hozzárendelésének kitöltendo

most elsosorban és ebbol a három C j -ben eloforduló változónak értékül igazságértéke3

ket kell kapnia. A 0 vagy 1 sorozatok 2

=

az algoritmus biztosan kivá8 lehetoségéb ol

lasztja azt az egyet, amely C j -t hamissá teszi. A szóban forgó csúcs V ´  ´ -SAT(ϕ, β) halott részfához vezet, amit nyugodtan levághatunk. A ϕ adódóan további halott részfák állnak elo, melyeket nem kell formula szerkezetébol adódik a V korlátjára legrosszabb esetben gyelembe venni, ebbol ´  ´ -SAT egy felso rekurziós fájában tehát egy

3

O((2

− 1)n/3 ) = O(

√ 3

n

7 )

≈ O(1.9129n ), ami a

mindig javítja valamelyest.

4

naiv

3-SAT algoritmus O(2n ) korlátját még

A félreértések elkerülése végett hangsúlyozni kell, hogy a rekurziós fa más, mint egy NTM kiszámítási fája. A

V egy rekurziós fa mélységi bejárásának megfele´  ´ -SAT algoritmus teljesen determinisztikusan muködik, csúcsai az algoritmus rekurzív hívásait reprezentálják, a gyökere az elso hívást, a leveleknél loen. Egy ilyen fa belso csúcsa pontosan akkor gyereke egy k pedig további hívások nélkül terminál az algoritmus. A rekurziós fa egy k hívás az algoritmus k után kiváltott számításán belül következik be, továbbá nincs olyan k? hívás, csúcsnak, ha a k ? ami k-n belül van és k -on belül van.

142

4. Bonyolultságelmélet A

3-SAT determinisztikus idobonyolultsága még lejjebb szorítható, például Monien és

korláttal rendelkezik. A Speckenmeyer oszd-meg-és-uralkodj algoritmusa O(1.618 ) felso n

korlát világrekordját determinisztikus felso

3-SAT-algoritmusra jelenleg egy O(1.481n ) kor-

látos, lokális keresésen alapuló megoldás tartja, melyet Dantsin és társai készítettek. Vannak más, nemdeterminisztikus megközelítések is. Ezek közül egyet mutatunk be, egy Schöning úgynevezett munkáiból meríto,

véletlen séta algoritmust.

4.3.2. 3-SAT valószín¶ségi id®bonyolultsága Egy véletlen séta egy (véletlen) bejárás adott struktúrán, például egy euklideszi térben, egy végtelen rácson vagy egy gráfon. Esetünkben a gráfok bejárása érdekes, azon belül is olyan gráfok bejárása, melyek egy meghatározott sztochasztikus automatát ábrázolnak. Egy sztochasztikus automata egy speciális véges automata. állapotgráfjának segítségével. A véges automata Egy véges automata szemléltetheto

Σ

állapotait csúcsok, az állapotok közti átmeneteket irányított, egy

ábécé szimbólumaival

címkézett élek jelölik. Egy csúcs a kitüntetett kezdoállapot szerepet kapja, ennél kezdodik az automata muködése, és akkor fejezodik be, ha a teljes bemenet feldolgozásra került. Az automata minden lépésben pontosan egy bemeneti szimbólumot olvas. Az állapotgráf bizonyos csúcsait végállapotként jelöljük meg, és amennyiben egy végállapotot érünk el a feldolgozás végén, akkor az automata elfogadja a bemenetet. Véges automatákkal szavakat ismerhetünk fel. Egy

Σ∗ -beli

=

w

w1 w2

· · · wn

szót az

automata pontosan akkor fogad el, ha a kezdoállapotból kiindulva w minden egyes wi szim sorrendben elolvassa, az állapotátmeneteket mindig a wi -vel jelölt él bólumát a megfelelo követésének megfeleloen hajtja végre, és végül elér egy végállapotot. Egy véges automata által elfogadott nyelv pontosan az ilyen módon elfogadott szavakból áll. Egy

S

sztochasztikus automata éleit utólagosan számokkal is felcímkézzük. Az

élhez rendelt pu,v (0 lapotgráfjában egy u-ból v-be vezeto színuségét adja meg, hogy

S

≤

≤

pu,v

S

ál-

1) érték annak való-

az u állapotból v állapotba lép. Egy sztochasztikus automata

(véletlen) állapotátmeneteinek folyamatát a sztochasztika tárgykörében Markov-láncoknak,

S sztochasztikus autoS által elfogadott nyelv

a végállapotokat pedig abszorpciós állapotoknak nevezhetjük. Egy mata esetében így természetesen egy w szó elfogadása (és ezzel az

deniálása) csak adott valószínuséggel következik be, mely valószínuséget a w feldolgozása ismerhetjük. során bejárt élek címkéibol Esetünkben azonban nem a nyelvfelismerés érdekes a sztochasztikus automata feladatai közül. Az automatát egy bejárásra szeretnénk alkalmazni, amit a V´ ´-SAT valószínuségi algoritmus valósít meg. A V´ ´-SAT algoritmus megpróbál az n-változós

ϕ

behelyettesítést találni, amennyiben létezik ilyen. Boole-formulához egy kielégíto V´ ´-SAT valamely

ϕ bemenet mellett eloször is készít egy véletlenszeru β β minden egyes bitje függetlenül választott egyenletes eloszlás mellett, tehát β minden bitje 0 vagy 1 értéket vesz fel 1/21/2 valószínuséggel. A behelyettesítéseket ismét mint {0, 1} feletti n-hosszú szavakat kezeljük. Tegyük fel, hogy ϕ kielégít ϕ tetszolegesen és legyen β behelyettesítése ϕ-be. Legyen X az a heto, választott kielégíto Hamming-távolságát fejezi ki, vagyis azon bitek számát, valószínuségi változó, ami a β és β nem egyeznek meg. X nyilvánvalóan a j ∈ {0, 1, . . . , n} értékeket veheti fel, valaahol β és β mint binomiális eloszlású n és 1/2 paraméterekkel. Ennek megfeleloen X = j valószínusége n

kezdeti hozzárendelést, ahol

−n

j

2

.

4.3. Az ítéletlogika kielégíthet®ség-problémája

143

s 1

6

15

20

15

6

1

64

64

64

64

64

64

64

2 3

1

0

3

1

1

2

3

2

3

2

3

2

2

3

4

3

5

6

1

1

1

1

1

3

3

3

3

3

2 3

4.7. ábra. Egy V´ ´-SAT bejárás sztochasztikus automatájának állapotgráfja.

V´ ´-SAT(ϕ) 1

for i

← 1 to d(4/3)n e

2

do válasszunk egy

3

for j

4

B n a ϕ változóinak száma. β ∈ {0, 1}n behelyettesítést, egyenletes eloszlás szerint

← 1 to n ϕ(β) = 1

do if

β

7

B β kielégíti ϕ-t. = (x ∨ y ∨ z) klózt, ahol C(β) = 0 válasszunk véletlenszeruen egy ` ∈ { x, y, z} literált,

8

állapítsuk meg

9

változtassuk meg

5

then return

6

else válasszunk egy C

egyenletes eloszlás szerint

10

return

β `-edik lefoglalt β` ∈ {0, 1} bitjét β-ban β` -t (1 − β` )-re

ϕ kielégíthetetlen

A V´ ´-SAT algoritmus ezután ellenorzi, hogy a kezdetben választott

β hozzáϕ formulát, és amennyiben igen, akkor elfogadja a bemenetet. Egyébként pedig ha β nem teszi igazzá ϕ-t, akkor léteznie kell egy ϕ-beli klóznak, amit β nem elégít ki. A V´ ´-SAT tetszolegesen kiválaszt egy ilyen klózt, a kiválasztott klózrendelés kielégíti-e a

ban egyenletes eloszlás mellett véletlenszeruen kijelöl egy literált, és megcseréli az ehhez a literálhoz rendelt bitet az aktuális

β

behelyettesítésben. Ezt n-szer megismétli, majd

amennyiben az aktuális behelyettesítés még mindig nem elégíti ki a

ϕ

formulát, akkor a

V´ ´-SAT újraindul egy új kezdeti hozzárendeléssel és megismétli a teljes fent leírt

= d(4/3)n e. A 4.7. ábrán egy S sztochasztikus automata szerepel, melynek éleit nem szimbólumokkal, hanem mindössze átmenet-valószínuségekkel címkéztük. A V´ ´-SAT algorit mus ϕ bemenet melletti muködését a következokben mint S egy bejárását mutatjuk be. Az s kezdoállapotból kiindulva amit késobb már sosem érintünk V´ ´-SAT(ϕ) az n és 1/2 paraméteru binomiális eloszlásnak megfeleloen lép tovább egy j ∈ {0, 1, . . . , n} része egy n = 6 változós ϕ Boole-formula esetében. állapotba. Ezt mutatja a kép felso Egy ilyen j állapot azt jelenti, hogy a véletlenszeruen választott β kezdeti behelyettesítés kielégíto behelyettesítés állandó közötti Hamming-távolság j. Amíg j , 0, addig és a β V´ ´-SAT(ϕ) a belso for ciklusban a kielégíto megoldást keresve mindig megváltoztatja az aktuális β behelyettesítés egy β` bitjét (1 − β` )-re. Az S bejárásban ez megfelel egy lépésnek a j − 1 állapotba balra vagy a j + 1 állapotba jobbra, ahol csak n-nél kisebb próbát t-szer, ahol t

állapot érheto el. vagy n-nel egyenlo behelyettesítés kielégíti Az állandóra választott β

ϕ-t,

tehát

ϕ

minden klózából lega-

144


lább egy literált igazzá tesz. Ha minden klózban pontosan egyet kijelölünk ezek közül a

β

` − 1-be) j + 1-be) valószínusége nyilvánvalóan mindig 1/3, a jobbra lépés ( j-bol pedig mindig 2/3. Hamming-távolsága 0 lesz. Ennek megBármikor is érjük el a j = 0 állapotot, ott β és β feleloen β kielégíti a ϕ formulát, és V´´-SAT(ϕ) visszaadja β aktuális értékét, majd -tól kümegáll elfogadó állapotban. Egy j , 0 állapotban természetesen belefuthatunk egy β által kielégített literálok közül, úgy pontosan akkor lépünk egy lépést balra, ha ezt az

literált V´ ´-SAT kiválasztja. Egy balra lépés valószínusége (j

>

0-ból j

kielégíto behelyettesítésbe is, de mivel ez a lehetoség lönbözo az elfogadás valószínuségét csak növelheti, ezért az elfogadás valószínuségének becslésénél most gyelmen kívül hagyjuk. Ha a j

= 0 állapotot nem érjük el β behelyettesítés n-szeri bitcseréjével, akkor a kezdo

behelyettesítést olyan rosszul választottuk, hogy V´ ´-SAT(ϕ) egyszeruen eldobja, és egy új kezdeti értékkel próbál ismét szerencsét. 0 végállapottól jobbra távoMivel annak valószínusége, hogy a (számunkra kedvezo) lodjunk, nagyobb, mint annak valószínusége, hogy 0 irányába balra haladjunk, azt gondolhatjuk, hogy V´ ´-SAT nem túl nagy valószínuséggel jár sikerrel. Annak esélyét rögtön a nulladik lépés után a 0 közelébe kesem szabad azonban alábecsülni, hogy s-bol pozíciónk, annál nagyobb annak valószínusége, rülünk. Minél közelebbi a 0-hoz a kezdo véletlen jobbra- vagy balra-lépések lefutásával 0-ba ütközünk. hogy a rákövetkezo V´ ´-SAT eredményességének valószínuségére és az algoritmus futási idejére vonatkozó elemzést itt most nem mutatjuk be teljes részletességében, csak vázlatszeruen. Az egyszeruség kedvéért tegyük fel, hogy n a 3 egész értéku többszöröse. Legyen pi annak valószínusége, hogy V´ ´-SAT n lépésen belül eléri a 0 állapotot, azzal a feltétellel, hogy V´ ´-SAT a bejárás nulladik lépésében (β kezdeti véletlen hozzárendelés megválasztásakor) az i

≤ n/3 állapotba kerül. Amennyiben például kezdetben az n/3 állapotba

kerülünk, akkor legfeljebb n/3 lépés megengedett a

rossz irányba jobbra, ami kiegyen el helyes irányba, balra tett lépésekkel. Egyéb esetekben a 0 állapot nem érheto n lépésben. Általában az i állapotból kiindulva legfeljebb (n − i)/2 lépést tehetünk jobbra,

a lítheto

a következo becslés adódik pi -re: amibol

pi

=

n n−i 2

!

2

!(n−i)/2

3

1

!n−(n−i)/2

3

.

(4.2)

Legyen továbbá qi annak valószínusége, hogy V´ ´-SAT a bejárás nulladik lépésében az i

≤ n/3 állapotba jut. Ekkor természetesen fennáll ! n qi = · 2−n .

(4.3)

i

Végül pedig legyen p az eredményesség valószínusége, amikor V´ ´-SAT a for ciklus egy körében eléri a 0 állapotot. Ez lehetséges j külso

>

n/3 állapotokból is.

Ennélfogva fennáll

p

≥

n/3 X

pi

· qi .

i=0

az entrópiafüggvény segítségével, továbbá az összeg tagjaiban Ez az összeg közelítheto a Stirling-formulával, így végül (4.2) és (4.3) binomiális együtthatói közelíthetok adódik p alsó korlátjának.

Ω((3/4)n )

4.4. Gráfizomorfizmus és alsóság

145

A hibás futás elkerülése érdekében a V´ ´-SAT algoritmus összesen t független kísérletet hajt végre, melyek mindegyike új kezdoértékkel indul, és legalább a fent megan

(3/4) dott hozzávetoleges

valószínuséggel sikerrel jár. Mivel a kísérletek függetlensége

miatt ezek a valószínuségi értékek szorzódnak, ezért V´ ´-SAT eredményes futásának valószínusége tehát annak valószínusége, hogy V´ ´-SAT megadja behelyettesítését, amennyiben az létezik nagyon közel van 1-hez. Ha pedig kielégíto

ϕ egy ϕ kie-

légíthetetlen, V´ ´-SAT sosem követ el hibát, tehát ezekben az esetekben a kimenet

ϕ kielégíthetetlen lesz. Az algoritmus futási ideje megegyezik az eredményes futás p

mindig

≈

(3/4)

n

valószínuségé

nek reciprokával, mivel egy hiba valószínusége (amikor a t próba során egyszer sem találunk t −t· p (1 − p) ≤ e Amennyiben ϕ kielégítheto) -vel becsülheto. t értékét tehát nem szeretnénk egy elore adott ε hibavalószínuségi értéket átlépni, elegendo −t · p ol úgy megválasztani, hogy e ≤ ε, illetve t ≥ ln(1/ε)/ p fennálljon. A konstans tényezokt n n az algoritmus futási ideje tehát O ((4/3) ). eltekintve ez t = d(4/3) e választásával elérheto,

behelyettesítést, pedig kielégíto

Gyakorlatok

4.3-1. Indítsuk el a V ´  ´ -SAT algoritmust a

ϕ = (¬ x ∨ y ∨ ¬z) ∧ (x ∨ ¬y ∨ z) ∧ (¬u ∨ ϕ egy kielégíto

lépésre y ∨ z) ∧ (u ∨ ¬y ∨ z) Boole-formulával, és konstruáljuk meg lépésrol

behelyettesítését. Rajzoljuk fel az így kialakuló rekurziós fát, és határozzuk meg a fa azon részeit, melyeket levágunk, mert nem vezethetnek megoldáshoz.

4.4. Gráfizomorfizmus és alsóság alfejezetben szükségünk lesz a 3.1.3. alfejezetben leírt csoport- és gráfelméA következo leti alapokra. Különösen fontos felidézni a 3.6. deníció permutációcsoport fogalmát, a grázomorzmus problémát, valamint a 3.8. deníció

GA

GI

gráfautomorzmus problémáját

(lásd még a 3.4. példát is).

4.4.1. Visszavezethet®ségek és bonyolultsági hierarchiák A 4.2. pontban megismerkedtünk a hatékonyan megoldható házasítás problémával, valamint az NP-teljes SAT,

3-SAT

és 3-DM problémákkal. Könnyen meggondolhatjuk, hogy P

=

NP

pontosan akkor teljesül, ha minden NP-beli probléma beleértve az NP-teljes problémákat is P-ben helyezkedik el. Amennyiben P

, NP, akkor P-ben nem lehetnek NP-teljes prob , NP

lémák. Megoldható-e vajon hatékonyan minden NP-beli probléma a hihetonek tun o

feltevés mellett, tehát P-beliek-e, vagy pedig NP-teljesek? Tudunk-e vajon olyan NP-beli problémákat adni P

,

NP feltevés mellett, melyek nem oldhatók meg hatékonyan, de nem

tétel adja meg. is NP-teljesek? A választ a következo 4.11. tétel (Ladner). Ha P

,

NP, akkor léteznek olyan problémák NP-ben, melyek se nem

P-beliek, se nem NP-teljesek. A Ladner által megadott problémák valamelyest mesterségesek olyan szempontból, hogy közvetlenül a 4.11. tétel bizonyításához készültek. Vannak azonban olyan természe jelöltek arra, hogy se P-beliek, se pedig NPtes problémák is NP-ben, melyek megfelelo teljesek ne legyenek. Ezek közül egy

GI,

a grázomorzmus probléma, és ezt szeretnénk

146


most bizonyítani. Ehhez deniálunk NP-n belül két, Schöning által bevezetett bonyolultsági osztályhierarchiát, az úgynevezett alsó-, valamint a felso-hierarchiát. Ahhoz, hogy polinomiális idoezt a két hierarchiát deniálni tudjuk, be kell vezetnünk az NP-re épülo hierarchia fogalmát, ennek deníciójához pedig szükségünk van egy, a 4.5. denícióban bevezetett sok-egy visszavezethetoségnél általánosabb visszavezethetoségre, nevezetesen a p

≤T fogalmára. Deniáljuk továbbá a nemdeterminisztikus és az NP NP fogalmakat, melyek a és ≤ erosen nemdeterminisztikus Turing-visszavezethetoség ≤ sT T Turing-visszavezethetoség, a

polinomiális ido-hierarchia esetében fontosak. Ezek a visszavezethetoségek az orákulumos Turing-gép fogalmára építkeznek. Most tehát deniáljuk a nevezett fogalmakat. 4.12. deníció (orákulumos Turing-gép). Az orákulum-halmaz (röviden orákulum) szavak egy halmaza. Egy B orákulummal rendelkezo orákulumos M Turing-gép egy olyan Turing-gép, ami rendelkezik egy speciális

kérdés-szalaggal, állapotainak halmaza pedig

tartalmaz egy speciális z? kérdés-állapotot, valamint zyes és zno válasz-állapotokat. Amíg M nincs a z? állapotban, addig pontosan úgy viselkedik, mint egy szokványos Turing-gép. Ha azonban muködése során z? kérdés-állapotba kerül, akkor megszakítja futását, és kérdést intéz az orákulumhoz az éppen a kérdés-szalagon álló q szóról. Az orákulumot egyfajta fekete dobozként képzelhetjük el: B orákulum egy lépésben eldönti, hogy q szó B-beli-e, függetlenül attól, hogy ennek eldöntése milyen nehézségu feladat. Ha q ∈ B, akkor M a következo lépésben zyes válasz-állapotba kerül és folytatja muködését. Ellenkezo esetben (ha q

<

B) M zno állapotban folytatja muködését. Ekkor azt mondjuk, hogy az M Turing-géppel B

x bemenet kiszámítása relatív B orákulumra nézve, a kiszámítást pedig M (x)-el jelölünk. B

Legyen L(M ) az M

B

által elfogadott nyelv. Egy

C bonyolultsági osztályt relativizálhatónak

nevezünk, ha reprezentálható orákulumos Turing-gépekkel (üres orákulum-halmaz mellett) az eloz oeknek megfeleloen. Deniáljuk egy orákulum mellett a B-re relatív

C

C relativizálható bonyolultság-osztály és egy

B

osztályt a következoképp:

CB = {L(M B ) | M egy C-t reprezentáló orákulumos Turing-gép} . S B B Ha B halmazok egy osztálya, akkor legyen C = B∈B C . NPOTM (illetve DPOTM) jelöli a nemdeterminisztikus (illetve a determinisztikus) po osztályok: linomiális ideju orákulumos Turing-gépeket. Deniálhatók például a következo NP

NP

=

[

NP

B

= {L(M B ) | M egy NPOTM, B pedig NP-beli}

;

B∈NP

P

NP

=

[

P

B

= {L(M B ) | M egy DPOTM, B pedig NP-beli} .

B∈NP

Amennyiben az orákulum üres halmaz (∅), akkor a nem relativizálható NP P

=

P

∅

=

NP

∅

,

illetve

beszélhetünk, DPOTM heosztályokhoz jutunk. NPOTM helyett ekkor NPTM-rol

Különösen jól alkalmazhatók az orákulumos Turing-gépek keresési lyett pedig DPTM-rol. példa mutatja. Az itt alfeladatokhoz, mint amilyen a prexkeresés is, ahogy a következo kalmazott Pre-Iso NP-orákulum szolgáltatja azt az információt, hogyan lehet az üres szó bitre haladva az NP-beli ból kiindulva bitrol

GI probléma legkisebb megoldását eloállítani,

amennyiben létezik ilyen megoldás. 4.5. példa. Prexkeresés a legkisebb izomorzmus után orákulumos Turing-géppel. A

GI grázomor-

zmus problémát az 3.1.3. alfejezet 3.8. deníciójában fogalmaztuk meg. Legyen G és H két adott

4.4. Gráfizomorfizmus és alsóság gráf n

≥

147

1 darab csúccsal. A G és H közti izomorzmusokat

zük. Az Iso(G , H) izomorzmus-csoport tartalmazza a Iso(G , H)

, ∅ ⇐⇒

(G , H)

∈ GI.

Ha (G , H)

∈ GI,

(G , H)

(G , H)

∈ GI

∈ GI

megoldásának nevez-

összes megoldását, valamint

akkor egy lexikograkusan legkisebb megoldás

λ szó kimenet segítségével tudatnunk kell, hogy < GI. Tehát, ki szeretnénk számítani a következoképp deniált f függvényt: ( min{π π ∈ Iso(G , H)}, ha (G , H) ∈ GI , f (G , H) = λ, ha (G , H) < GI ,

esetben pedig az üres eloállítása a célunk, ellenkezo

(G , H)

képezzük. A Sn deníciója a követSn -bol ∈ Sn egy permutációját mint n hosszú, [n] = {1, 2, . . . , n} ábécé fölötti π(1)π(2) · · · π(n) szót. Pontosan akkor írható π < σ (π, σ ∈ Sn ), ha létezik egy olyan j ∈ [n], melyre minden i < j esetén π(i) = σ(i), valamint π( j) < σ( j). Amennyiben egy σ ∈ Sn permutációból kitörlünk néhány (i, σ(i)) párt, akkor parciális permutációt kapunk, amit szintén kezelhetünk [n] fölötti szóként. A σ ∈ Sn egy k ≤ n hosszú prexe σ egy olyan parciális permutációja, amely minden (i, σ(i)) párt tartalmaz i ≤ k mellett, viszont egyetlen (i, σ(i)) párt sem i > k esetén. A k = 0 esetben σ prexe a λ üres szó, valamint k = n esetben a teljes permutáció. Ha π a σ ∈ Sn egy k < n hosszú prexe és w = i1 i2 · · · i|w| egy [n] fölötti |w| ≤ n − k hosszú szó, akkor jelölje πw azt a parciális permutációt, ami π-t a (k + 1, i1 ), (k + 2, i2 ), . . . , (k + |w|, i|w| ) párokra bovíti. Ha 1 ≤ j ≤ |w| esetén σ(k + j) = i j , akkor πw is σ egy prexe. Deniáljuk G és H gráfok mellett az Iso(G, H)-beli izomorzmusok prexeinek

ahol a lexikograkus rendezésre vonatkozó minimumot kezeljük a π kezo:

halmazát: Pre-Iso

=

{(G, H, π) (∃w ∈ {1, 2, . . . , n}∗ ) [w = i1 i2 · · · in−|π|

és

πw ∈ Iso(G, H)]} .

≥ 1-re a λ üres szót egy permutáció sem képzi le Sn -be, valamint hogy = ∅ pontosan akkor áll fenn, ha (G, H, λ) < Pre-Iso, ami viszont akkor és csak akkor igaz, ha (G , H) < GI. N-P-I(G , H) Figyeljük meg, hogy n Iso(G , H)

1

if (G , H, λ)

< Pre-Iso

2

then return 0

3

else

4

π←λ j ← 0

5

while j

6

B G és H mindig n csúcsú.

do i

7

while (G , H, πi)

8

do i

< Pre-Iso ←i+1 π ← πi j ← j+1

9 10 11

return

π

Az N DPOTM prexkereséssel, a Pre-Iso orákulum segítségével számítja ki az f függvényt (lásd még a 4.4-2. gyakorlatot). Jelölje FP a polinomiális idoben kiszámítható függvények osztályát. Ekkor f

∈

FP

Pre-Iso

. Mivel Pre-Iso egy NP-beli halmaz (lásd a 4.4-2. gyakorlatot), ezért f

∈

FP

NP

követke-

zik.

A 4.5. példa alapján elláthatók orákulummal a függvényeket kiszámító Turing-gépek is, valamint relativizálhatók függvény osztályokra, mint például az FP. Másrészt alkalmazhatók orákulumként halmazok helyett függvények is. A 4.12. denícióval összevetve az f :

Σ∗ → Σ∗

függvényorákulum egy q kérdésre egy lépésben nem az igen vagy nem válaszokat adja, hanem | f (q)| lépésben visszaadja az f (q) függvényértékeket. A következo

148


tétel kimondja, hogy konstruálható teljes izomorzmus két izomorf gráf közötti parciális izomorzmusból egy f függvényorákulum segítségével. 4.13. tétel. f (G , H)

=

Legyenek G és H izomorf gráfok. Legyen f egy függvényorákulum, melyre (x, y), ahol x

∈

V (G), valamint fennáll y

∈

V (H), és

σ(x) =

y egy

σ∈

Iso(G , H)

izomorzmussal. Ekkor létezik egy M DPOTM, amely az f orákulummal kiszámol egy

ϕ∈

Iso(G , H) izomorzmust. A 4.13. tétel szerint tehát az NP-beli a rukciója visszavezetheto

GI

GI

probléma egy teljes megoldásának konst-

egy parciális megoldására (érdemes lehet ezt összevetni a

bitre bovíti V a ´  ´ -SAT algoritmussal, ami bitrol

3-SAT kifejezések parciális megol-

dását, amíg azok teljesek nem lesznek).

GI probléma zéró σ ∈ Iso(G, H) izomorzmust küld Artúrnak, ahogy az kívánta,

Képzeljük el, hogy Merlin, a 3.5. alfejezet 3.12. ábráján szereplo ismeretu protokolljában egy

sajnos azonban az átvitelnél némely bitek elvesznek vagy használhatatlanná válnak. Artúr

σ-ból. Rekonstruálhat azonban Merlin ϕ ∈ Iso(G, H) teljes izomorzmust még akkor is, ha π csak egyetlen csúcspárból áll. Figyeljük meg, hogy ϕ-nek nem kell a Merlin által eredetileg elküldött σ izomorzmusnak lennie.

tehát csak egy parciális

π

izomorzmust kap meg

segítségével a 4.13. tételnek köszönhetoen egy

A 4.6. példa a bizonyítás alapötletét szemlélteti konkrét gráfokkal. A formális bizonyítástól most eltekintünk. Egy lényeges tulajdonság, amit itt kihasználunk

GI úgynevezett

ön-visszavezethetosége. Anélkül, hogy belemennénk a technikai részletekbe, ezt a fontos fo galmat a következoképp írhatjuk le: egy A halmaz pontosan akkor ön-visszavezetheto, ha létezik egy M DPOTM, ami egy A orákulum segítségével elfogadja magát az A halmazt. M az x bemeneti szóról egyszeruen megkérdezhetné az A orákulumot, amikor is x A-beliségének eldöntése természetesen triviális lenne, ezért az ön-visszavezethetoségnél megtiltjuk a bemenetre magára vonatkozó kérdéseket. Ehelyett az M csak olyan kérdéseket tehet fel az A a hagyományos lexikoorákulumnak, melyek kisebbek a bemenetnél, ahol a kisebb jelzot általánosított értelemben használjuk. Ezt a deníciót a 4.13. tételnek grakus rendezésbol megfeleloen szintén átültethetjük halmazok helyett függvényekre. 4.6. példa. (Teljes izomorzmus eloállítása parciális izomorzmusból.) A ??. ábra két izomorf G és H gráfjára Iso(G , H)

= {σ, ϕ}, ahol σ = (

1 2 3 4 5 1 5 4 3 2

) és

ϕ=(

1 2 3 4 5

). A következokben leírunk és körüljárunk

5 1 4 3 2

naiv megközelítést. Tegyük fel, hogy a 4.13. tétel algoritmusa az f orákulumhoz egy kudarchoz vezeto intézett kérdésekkel meghatároz egy (x, y) csúcspárt, ahol

σ(x) =

y vagy

ϕ(x) =

y. Így felismerve

illetve y-t H-ból, és hasonló módon fokozatosan addig halad, (x, y)-t az algoritmus törli x-et G-bol, amíg a gráfok üresek nem lesznek. Ezzel biztosítottuk, hogy az algoritmus legfeljebb n

=

5 lépésben

termináljon, és remélhetoleg a tárolt csúcspárok sorrendje a keresett Iso(G , H)-beli izomorzmust adja, tehát vagy

σ-t,

vagy pedig

ϕ-t.

Ez azonban nem feltétlenül következik be. Tegyük fel például,

(G , H) párra vonatkozó kérdésre az f orákulum az (5, 2) csúcspárt válaszolja. A 4.13. hogy az elso az 5, valamint H-ból a 2 csúcsokat (valamint az 5-bol, tétel algoritmusa ekkor egyszeruen törli G-bol

b és H b gráfjaihoz jutunk. Az Iso(G b, H) b azonban hat kiinduló éleket). Ekkor a ??. ábra G illetve a 2-bol

csak ketto összeegyeztetheto izomorzmust tartalmaz, amibol a (5, 2) párral (lásd a 4.4-3. gyakorlatot).

b, H) b hat izomorzmusából csak ketto parciális izomorzmusa Ez tehát azt jelenti, hogy Iso(G

σ-nak és ϕ-nek. Ezután az algoritmus következo lépésében tárolhatja például az új (4, 5) párt, ami sem σ-hoz, sem pedig ϕ-hez nem tartozik. Annak érdekében, hogy kizárhassuk ezeket az eseteket, a 4.13. tétel f orákulumos M DPOT M-ja másképp jár el. Nem csak egyszeruen törli azokat a csúcspárokat, melyeket az orákulum segítségével


149

meghatározott, hanem elegendoen nagy méretu klikkek segítségével kijelöli a törölt csúcsok szomszédos csúcsait. Egy k méretu klikk olyan gráf, aminek k darab csúcsa páronként egy-egy éllel mindenhol (5, 2) csúcspár törlése után a G-beli 4 és H-beli 3 csúcsokat össze van kötve. Példánkban tehát az elso adódik a (G 1 , H1 ) új pár, lásd a ??. ábrán. Figyeljük meg, egy 5 méretu klikkel jelöljük meg. Ebbol

π ∈ Iso(G1 , H1 ) σ-ból és ϕ-bol.

hogy most minden Iso(G , H)-beli

a (5, 2) csúcspárral az eredeti izomorzmus összeegyeztetheto

Ha M fokozatosan e szerint az eljárás szerint halad, akkor az orákulum válaszok egy megha (G 2 , H2 ), (G 3 , H3 ) és (G 4 , H4 ) gráfpárok állhatnak tározott sorozatára például az ??. ábrán szereplo Ekkor a (G 4 , H4 )-nél egyértelmuen elo. meghatároztuk az utolsó (4, 3) csúcspárt, M pedig ebben az esetben eloállította a

ϕ=(

1 2 3 4 5 5 1 4 3 2

) teljes izomorzmust Iso(G , H)-ból.

visszavezethetoségeket Most pedig különbözo deniálunk az orákulumos Turing-gép fogalmából kiindulva. Minden itt vizsgált visszavezethetoség hatékonyan tehát polinomi ális idoben kiszámítható.

Σ = {0, 1} egy bináris ábécé, legyenek Σ feletti szavak halmazai, és legyen C egy bonyolultsági osztály. A C-beli halmazok komplementereinek osztályát deniáljuk mint coC = { L | L ∈ C}. Deniáljuk a következo

4.14. deníció (Turing-visszavezethetoség). Legyen A és B ezen

visszavezethetoségeket:

• •

p

Turing-visszavezethetoség: A≤

T

⇐⇒

B

A

=

B

L(M ) egy M DPOTM-ra.

Nemdeterminisztikus Turing-visszavezethetoség: A≤

NP T

B

⇐⇒

A

=

B

L(M ) egy M NPOTM-

ra.

• •

Eros nemdeterminisztikus Turing-visszavezethetoség: A≤ Ha

≤r

NP

B

sT

←→

A

∈ B ∩ coNPB .

egy fent deniált visszavezethetoség, akkor egy B halmazt pontosan akkor neve-

≤r -nehéznek C-ben, ha A ≤r B teljesül minden A ∈ C halmazra. Egy B halmaz pontosan akkor ≤r -teljes C-ben, ha B ≤r -nehéz C-re és B ∈ C. p p C P = { A | (∃ B ∈ C) [A ≤ B]} halmaz a C lezárása ≤ -visszavezethetoség mellett. T T C NP NP NP = { A | (∃ B ∈ C) [A ≤ B]} halmaz a C lezárása ≤ -visszavezethetoség mellett. T T zünk

• •

A 4.14. deníció

p

≤T - és ≤NP -visszavezethetoségeinek segítségével bevezetjük a polinoT

miális ido-hierarchiát, valamint az NP-ben deniált alsó- és felso-hierarchiákat. 4.15. deníció (polinomiális ido-hierarchia). A PH a következoképp deniáljuk: minden i

≥ 0-ra.

coΣ

1

p

p

p

S k ≥0

∆0 = Σ0 = Π0 = P, ∆i+1 = P

speciális esetként Ebbol p

p

=

∆1p =

P

p

Σ0

=

P

P

=

P és

p

Σi

Σkp polinomiális ido-hierarchiát p p Σ , Σ = NP és Π = coΣip+1 i+ 1 i+1

Σ1p =

p

i

p

Σ0

NP

=

NP

P

=

NP és

Π1p =

= coNP adódik. A következo bizonyítás nélküli tétel megadja ezen hierarchiák néhány

tulajdonságát (lásd még a 4-2. feladatnál). 4.16. tétel (Meyer és Stockmeyer). Minden egyes i p

p

p

p

≥ 1-re:

p

1.

Σi−1 ∪ Πi−1 ⊆ ∆i ⊆ Σi ∩ Πi .

2.

Σip , Πip , ∆ip és PH mind ≤m -lezártak, ∆ip továbbá a ≤T -visszavezetésekre nézve is lezárt.

3.

Σip pontosan azt az A halmazt tartalmazza, amelyre léteznek B ∈ P halmaz és egy p poli∗ p p p nom úgy, hogy minden x ∈ Σ -ra: x ∈ A ⇐⇒ (∃ w1 ) (∀ w2 ) · · · (Q wi ) [(x, w1 , w2 , . . . , wi ) ∈ p p p p B], ahol a ∃ és ∀ kvantorok polinomiális hosszkorlátúak és Q = ∃ ha i páratlan, p p vagy Q = ∀ ha i páros.

p

p

150


.. . ..

Π

.

. . . . . .

Π

∆

Σ

···

Σ

. . . . . .

valamint az alsó- és felso-hierarchiák. 4.8. ábra. A polinomiális ido-,

4.

Ha

Σip−1 = Σip , akkor PH összeomlik Σip−1 = Πip−1 = ∆ip = Σip = Πip = · · · = PH-ba.

5.

Ha

Σip = Πip , akkor PH összeomlik Σip = Πip = ∆ip+1 = Σip+1 = Πip+1 = · · · = PH-ba.

6.

Σip -ben, Πip -ben és ∆ip -ben léteznek ≤m -teljes problémák. Amennyiben PH-ban létezik p ≤m -teljes probléma, akkor PH egy véges szintjébe omlik össze, vagyis egy adott k-val p p PH = Σ = Π . k k

p

4.17. deníció (az NP-beli alsó- és felso-hierarchia).

•

az NP-beli LH

=

S

k ≥0

p

Σk }, •

az NP-beli HH p, H

=

S k ≥0

Legyen k

≥ 0 mellett az

Lowk alsó-hierarchia k-adik szintje Lowk

Highk felso-hierarchia k-adik szintje Highk

Σk }.

= {L ∈

NP |

Σkp,L ⊆

= {H ∈ NP | Σkp+1 ⊆

Σkp kiszámításhoz orákulump ként használhatatlan, vagyis minden információt, amit L kínálhat, egy Σ -gép is kiszámíthat, k Egy L halmaz tehát akkor és csak akkor Lowk -beli, ha egy

egy H halmaz Highk -ból olyan gazdag hasznos önmagában, orákulum nélkül. Másrészrol növeli. Egy Highk -beli H

Σkp -gép kiszámítási erejét egy NP-halmazban maximális értékre p p orákulum segítségével tehát egy Σ -gép minden Σ kiszámítást k k +1

szimulálhat. Egy

számára tehát H pontosan olyan sokat nyújt, mint egy NP-teljes

információkban, hogy egy

Σkp -gép

halmaz. A fent deniált hierarchiák egymásba ágyazott szerkezetét a 4.8. ábra szemlélteti, ahol a világosabb tónusú bonyolultsági osztályok tartalmazzák a sötétebb árnyalatú osztályokat. Egyik ilyen

C ⊆ D tartalmazásról sem ismert, hogy valódi-e, tehát vajon C , D Σkp , Σkp+1 igaz-e, k = 0 esetében pontosan a P-versus-NP kérdés.

fennáll-e. A kérdés, hogy

Most (ismét bizonyítás nélkül) felsoroljuk a hierarchiák néhány fontosabb tulajdonságát (lásd még a 4-2. feladatot). Ladner tétele (4.11.) közvetlenül következik a 4.18. tétel utolsó állításának n

= 0 speciális esetébol.


151

4.18. tétel (Schöning). 1.

Low0

= P, Low1 = NP ∩ coNP és NP ∩ coAM ⊆ Low2 .

2.

High0

-teljes NP-ben}. = {H | H ≤T -teljes NP-ben} és High1 = {H | H ≤NP sT

3.

Low0

⊆ Low1 ⊆ · · · ⊆ Lowk ⊆ · · · ⊆ LH ⊆ NP.

4.

High0

⊆ High1 ⊆ · · · ⊆ Highk ⊆ · · · ⊆ HH ⊆ NP.

5.

Minden n

≥ 0-ra Lown ∩ Highn

6.

Minden n

≥ 0-ra NP-ben akkor és csak akkor léteznek sem Lown -beli, sem pedig Highn Σnp , Σnp+1 . NP-ben pontosan akkor léteznek sem LH-beli, sem pedig

p

pontosan akkor nem üres, ha

Σnp = Σnp+1 = · · · = PH.

beli halmazok, ha

HH-beli halmazok, ha PH valódi végtelen halmaz, tehát nem omlik össze egy véges szintjére.

4.4.2. A gráfizomorfizmus alsó-hierarchiabeli GI Low2 -beli, ami egy GI NP-teljessége ellen. Ha GI NP-teljes lenne, akkor High0 ⊆ High2 -beli p is lenne, mivel a 4.18. tétel alapján High0 pontosan NP ≤ -teljes részét tartalmazza, így tehát T p következik viszont, hogy Low2 ∩ High2 akaz NP ≤m -teljes részét is. Szintén a 4.18. tételbol p kor és csak akkor nem üres, ha PH összeomlik Σ -be, ami viszont nagyon valószínutlennek 2 Hozzákezdve az említett eredmény bizonyításához belátjuk, hogy fegyvertény eros

tunik. A tétel bizonyításához szükségünk van még az úgynevezett hasítás lemmára, lásd 4.20. eljárás. Minden adategységhez egy kulcs tarlemma. A hasítás egy dinamikus adatrendezo tozik, ami azt egyértelmuen azonosítja. A kulcsok U halmaza meglehetosen nagy, a kö vetkezokben mint univerzum tekintjük, mivel a ténylegesen felhasznált kulcsok V

⊆

U

halmaza jóval kisebb lehet. A célunk az, hogy U elemeit egy hasító függvény segítségével bejegyezzük egy T

= {0, 1, . . . , k − 1} hasító táblázatba, ahol több U -beli kulcshoz is tartoz-

V -beli kulcsoknak különbözo T -beli hat ugyanaz a T -beli cím. Lehetoség szerint különbözo a ténylegesen használt kulcsok ütközései. Másképp címet kell kapniuk, tehát elkerülendok fogalmazva a hasító függvény lehetoség szerint legyen injektív V -re. ismert hasító eljárás változat közül számunkra leginkább az univerA sok különbözo zális hasítás az érdekes. Ennél az alapötlet abból áll, hogy egy alkalmasan választott hasító függvény családból véletlenszeruen választunk egy hasító függvényt. Ez a hasítás módszer univerzális olyan értelemben, hogy már nem függ egy meghatározott V halmaztól, hanem minden megfeleloen kicsi V halmazon nagy valószínuséggel elkerüli az ütközéseket. A va lószínuség itt a hasító függvény véletlenszeru választására vonatkozik. A következokben a kulcsokat mint

Σ = {0, 1} ábécé fölött kódolt szavakat kezeljük, és Σn -el jelöljük a Σ∗ -beli,

n hosszú szavak halmazát. Legyen Σ = {0, 1}, valamint legyenek m és t természetes számok, > m. Egy h : Σt → Σm hasító függvény lineáris leképezés, ami egy (t × m) Boole-mátrixszal t adott, mégpedig Bh = (bi, j )i, j -vel, ahol bi, j ∈ {0, 1}. Minden x ∈ Σ és 1 ≤ j ≤ m mellett az m y = h(x) ∈ Σ j-edik bitje mint y j = (b1, j ∧ x1 ) ⊕ (b2, j ∧ x2 ) ⊕ · · · ⊕ (bt, j ∧ xt ) adódik, ahol ⊕ a logikai paritásmuveletet jelenti, tehát a1 ⊕ a2 ⊕ · · · ⊕ an = 1 ⇐⇒ |{i | ai = 1}| ≡ 1 mod 2. t m Legyen Ht,m = {h : Σ → Σ | Bh egy (t × m) Boole-mátrix} hasító függvények egy családja, t és m paraméterekkel. A Ht,m -re egyenletes eloszlást tételezünk fel: Ht,m -bol egy 4.19. deníció (hasítás). t

152


h hasító függvényt emelünk ki, amelynél a Bh -beli bi, j -ket függetlenül és egyenletes eloszlás mellett választjuk. Legyen V

b részcsaládjára akkor lép fel ütközés V -n, ha ⊆ Σt . A Ht,m egy H (∃v

Egyéb esetekben

b) (∃ x ∈ V ) [v , x ∧ h(v) = h(x)] . ∈ V ) (∀h ∈ H

b a V -n ütközésmentes. H

Egy V fölötti ütközés azt jelenti tehát, hogy megsérül egy tetszolegesen választott

b H

lemma kimondja, hogy minden családbeli hasító függvény injektivitása V -n. A következo kelloen kis V halmazon

Ht,m

egy véletlenszeruen választott részcsaládja ütközésmentes, ha

pedig V túl nagy, az ütközés elkerülhetetlen. A 4.20. lemma bizonyításától eltekintünk.

b = (h1 , h2 , . . . , hm+1 ) ∈ N paraméterek, V ⊆ Σt és H egy egyenletes eloszlás mellett véletlenül választott hasító függvény család Ht,m -bol. Legyen

4.20. lemma (hasítás lemma). Legyenek t, m

K(V )

b | (∃v ∈ V ) (∀h ∈ H b) (∃ x ∈ V ) [v , x ∧ h(v) = h(x)]} = {H

b-ban egy ütközés fellépésének eseménye V -n. Ekkor H 1.

ha |V |

≤ 2m−1 , akkor K(V ) legfeljebb 1/4 valószínuséggel következik be,

2.

ha |V |

> (m + 1)2m , akkor K(V ) 1 valószínuséggel következik be.

A 3.5. alfejezetben deniáltuk az Artúr-Merlin hierarchiát és említettük, hogy ez a hierarchia a második szintjére omlik össze. Számunkra most a coAM osztály érdekes, lásd a 3.16. deníciót. 4.21. tétel (Schöning). A

GI probléma Low2 -beli.

Bizonyítás. A 4.18. tétel alapján minden coAM-beli NP-halmaz Low2 -beli. GI Low2 -beliségének belátásához elégséges tehát azt megmutatni, hogy GI coAM-beli. Legyenek G és H n csúccsal gráfok. A hasítás lemmát szeretnénk alkalmazni. Ígéretesnek tunik, rendelkezo hogy a 3.11. lemmában deniált A(G , H)

= {(F, ϕ) | F G és ϕ ∈ Aut(F)} ∪ {(F, ϕ) | F

H és

ϕ ∈ Aut(F)}

halmaz a 4.20. lemma V -jének szerepét vegye fel. A 3.11 lemma szerint | A(G , H)| amennyiben G

H és | A(G , H)|

= 2n!, ha G

H. Ahhoz, hogy a

= n! GI-t megoldó coAM-gép

polinomiális idoben dolgozzon, a hasítás lemma t és m paraméterei n-ed fokú polinomok kell legyenek. A lemma alkalmazásához az m hogy n! fennálljon, mivel ekkor lesz a V

= m(n) polinomot úgy kellene választanunk,

≤ 2m−1 < (m + 1)2m < 2n!

=

(4.4)

A(G , H) halmaz elég nagy ahhoz, hogy elegendoen nagy

valószínuséggel meg tudjunk különböztetni két izomorf G és H gráfot két nem izomorf gráf tól. Sajnos nem létezik olyan m polinom, hogy a (4.4) egyenlotlenség fennálljon, ehelyett és alsó korlátok közötti rést elég naggyá választunk egy másik V halmazt, amivel a felso tudjuk tenni.

4.4. Gráfizomorfizmus és alsóság Legyen V

=

A(G , H)

n

=

153

A(G , H)

|

× A(G, H) × · · · × A(G, H). Ezzel (4.4) a következo{z } n-szer

képp alakul: n

(n!)

≤ 2m−1 < (m + 1)2m < (2n!)n ,

(4.5)

= m(n) = 1 + dn log n!e választással. GI-hez a következoképp. Az n csúcsú G és H gráfok n kiszámítja az m paramétert. A V = A(G , H) halmaz bemenete mellett M mindenekelott n darab (F, ϕ) formájú párost tartalmaz, ahol F egy n csúcsú gráf és ϕ ∈ Aut(F). Tekintsük a V elemeit mint t(n) hosszú, Σ = {0, 1} ábécé fölötti szavakat, ahol t egy alkalma az m ahol az új egyenlotlenség kielégítheto Készítsünk egy M coAM-gépet

san választott polinom. Ekkor M egyenletes eloszlás mellett véletlenszeruen választ egy

b = H

(h1 , h2 , . . . , hm+1 ) hasító függvény családot

ami megfelel Artúr lépésének. Ht,m -bol, b Minden hi ∈ H hasító függvényt egy (t × m) Boole-mátrixszal reprezentálunk, ezért az b-beli hi hasító függvény ábrázolható mint p(n) hosszú z b ∈ Σ∗ szó, ahol p m + 1 darab, H

H

egy alkalmas polinom. Módosítva a hasítás lemma K(V ) ütközés predikátumát B

= {(G, H, zHb ) | (∃v ∈ V ) (∀i : 1 ≤ i ≤ m + 1) (∃ x ∈ V ) [v , x ∧ hi (v) = hi (x)]} .

∀ kvantor csak polinomiálisan sok i-t határoz meg, ezért determinisztikus ∃ kvantora összefogható egy p darab polinomiális hosszra korlátozott ∃ kvantorrá. A 4.16. tétel alapján tehát B egy Σ = 1 szóhoz amit m + 1 függetNP-beli halmaz. Legyen N egy NPTM B-hez. A z b készülo H A B-ben elforduló

valamint B mindkét módon polinomiális idoben kiértékelheto,

lenül és egyenletes eloszlás mellett választott hasító függvény reprezentál M szimulálja az N(G , H, z b ) kiszámítását, ami megfelel Merlin lépésének. Az M pontosan akkor fogadja

H

el a (G , H) bemenetét, ha N(G , H, z b ) elfogad.

H

Becsüljük meg (a z b -ban kódolt hasító függvény véletlenszeru választása mellett) an-

H nak valószínuségét, hogy M elfogadja (G , H) bemenetét. Ha G és H izomorfak, akkor a 3.11 n m−1 |V | = (n!) ≤ 2 lemma alapján | A(G , H)| = n!. A (4.5) egyenlotlenségb ol következik. A

4.20. lemma alapján annak valószínusége, hogy (G , H, z b ) B-beli, következésképp M(G , H)

H

elfogad, legfeljebb 1/4. Ha ezzel szemben G és H nem izomorfak, akkor a 3.11. lemma szerint | A(G , H)|

=

2n!, a

pedig |V | (4.5) egyenlotlenségb ol

A 4.20. lemma alapján ekkor annak valószínusége, hogy következik tehát, hogy elfogad, közel 1. Ebbol

= (2n!)n > (m + 1)2m adódik. (G , H, z b ) B-beli, tehát M(G , H) H

GI coAM-beli.

4.4.3. A gráfizomorfizmus SPP-beli A 3.3.1. alfejezet 3.14. deníciójában bevezettük az RP valószínuségi osztályt. A követ alfejezetben két további, itt deniált valószínuségi kezo osztály játszik szerepet: PP és SPP, melyek a Probabilistic Polynomialtime és a Stoic Probabilistic Polynomialtime angol kifejezések rövidítései. 4.22. deníció (PP és SPP). A PP osztály azokat az A problémákat foglalja magában, melyekhez létezik egy M NPTM úgy, hogy minden x bemenetre: ha x nem kisebb valószínuség mellett elfogad, és ha x valószínuséggel fogad el.

<

∈

A, akkor M(x) 1/2-nél

A, akkor M(x) valamely 1/2-nél kisebb

154

4. Bonyolultságelmélet Jelölje acc M (x) az M(x) elfogadó útjainak számát egy M NPTM-nél x bemenet mel-

lett, valamint rej M (x) az M(x) visszautasító útjainak számát. Legyen továbbá gap M (x) acc M (x)

=

− rej M (x).

Az SPP osztály azokból az A problémákból áll, melyekre létezik olyan M NPTM, hogy minden x-re (x

∈

A

=⇒ gap M (x) = 1) és (x <

A

=⇒ gap M (x) = 0) teljesül.

Egy SPP-gép sztoikus tehát abban az értelemben, hogy a rése tehát az elfogadó és a visszautasító utak különbsége mindig csak két értéket vesz fel az exponenciális számú lehetséges érték közül. A PP-vel ellentétben az SPP így egy úgynevezett ígéret osztály ( promise class), mivel egy M SPP-gép azt ígéri, hogy minden x-re gap M (x) teljesül (lásd még a 4.4-4. gyakorlatot).

∈ {0, 1}

C bonyolultsági osztályra deniálhatC-alsó, ha CA = C teljesül. Speciálisan minden k-ra

Az alsóság fogalmát tetszoleges relativizálható juk: egy A halmaz akkor és csak akkor

a 4.17. deníció alsóság-hierarchiájának Lowk szintje pontosan azokból az NP-halmazokból áll, melyek

Σkp -alsó tulajdonságúak. Minden, a fent deniált SPP osztályba tartozó halmaz

tételben ezek mellett bizonyítás nélkül összefoglalunk néhány hasonló PP-alsó. A következo tulajdonságot. 4.23. tétel. SPP

1.

Az SPP osztály PP-alsó, tehát PP

2.

Az SPP önmagával alsó (angolul

3.

Legyen A

∈ NP egy N

= PP. SPP

self-low), tehát SPP

NPTM-el egyeztetve és L

∈ SPP

A

= SPP.

egy M NPOTM-mal egyeztetve

úgy, hogy az M-A(x) minden x bemenetre csak olyan q kérdést tesz fel, melyre accN (q)

≤

1 fennáll. Ekkor L SPP-beli. 4.

Legyen A

∈

NP egy N NPTM-mel egyeztetve és f

∈

FP

A

egy M DPOTM-ma egyez-

tetve úgy, hogy M-A(x) minden x bemenet mellett csak olyan q kérdést tesz fel, melyre accN (q)

≤ 1. Ekkor

SPP

f FP

-beli.

tétel kimondja, hogy egy jobb oldali co-halmaz lexikograkusan legkisebb A következo permutációja hatékonyan kiszámítható. A

Sn

lexikograkus rendezését a 4.5. példában de-

niáljuk. 4.24. tétel. Legyen

G ≤ Sn

egy permutációcsoport

G = hGi mellett és π ∈ Sn

egy permu-

táció. Ekkor létezik olyan algoritmus, amely a (G , π) bemenetre polinomiális idoben meghatározza a

Sn -beli G jobb oldali co-halmazát, Gπ-t.

Bizonyítás. A LERC algoritmus a lexikograkusan legkisebb permutáció kiszámítását végzi a

Sn -beli G jobb oldali co-halmazában Gπ-ben, ahol a G permutációcsoport egy G generá-

torfüggvényen keresztül adott, lásd a 3.1.3. pont 3.6. denícióját. számítható az id A 3.7. tétel segítségével polinomiális idoben

G

= G(n) ≤ G(n−1) ≤ · · · ≤

≤ G = G, G stabilizátor lánc. Pontosabban fogalmazva minden egyes i-re meghatá képezzük G egy G(i) jobb oldali T i reprezentáns rendszerét, ahol 1 ≤ i ≤ n, és ebbol Sn−1 (n−1) (n) erosebb S = T generátorát. Mivel ϕ = π és G = G = id, ezért a bizonyítási 0 i=1 hoz elég a LERC algoritmus helyességét megmutatni, tehát azt, hogy 0 ≤ i ≤ n − 1 esetén (i+1) minden i-re a G ϕi+1 -beli G(i) ϕi legkisebb permutációját kapjuk. (1)

rozzuk

(0)


155

LERC(G , π) 1

számítsuk ki a

G-beli stabilizátorok G(n) ≤ G(n−1) ≤ · · · ≤ G(1) ≤ G(0)

láncát

ϕ0 ← π for i ← 0 to n − 1 do x ← i + 1

2 3 4

G(i) (x) pályán az y elemet, melyre ϕi (y) minimális (i) határozzunk meg egy τi permutációt G -ben τi (x) = y mellett ϕi+1 ← τi ϕi return ϕn

5

számítsuk ki a

6 7 8 Z

indukcióval következik, hogy Ebbol

G(n) ϕn = {ϕn }

a

Gπ = G(0) ϕ0

lexikograkusan legki-

sebb permutációja. Következésképp tehát a LERC algoritmus valóban legkisebb

ϕn

Gπ lexikograkusan

permutációját adja vissza.

H ≤ Sn permutációcsoportbeli x ∈ [n] eleG(i) -beli permutáció, amely a i + 1-et a G(i) (i + 1) (i) y-ra képzi le, és amelyre ϕi (y) = x a {ϕi (z) | z ∈ G (i + 1)} halmaz minimális pályában lévo (i) eleme. A 3.7. tétel alapján a G (i + 1) pálya polinomiális idoben kiszámítható, és mivel G(i) (i + 1) legfeljebb n − i elemet tartalmaz, ezért y hatékonyan meghatározható. Az algorit(i) mus deníciója alapján fennáll ϕi+1 = τi ϕi . Mivel G minden permutációja minden [i]-beli (i) elemet önmagára képez le és mivel τi ∈ G , ezért minden j-re, amelyre 1 ≤ j ≤ i, minden τ ∈ G(i) -re és minden σ ∈ G(i+1) -re: A fenti állítás bizonyításához jelöljük egy

mek pályáját

H(x)-el.

Legyen

(σϕi+1 )( j)

τi

az a

= ϕi+1 ( j) = (τi ϕi )( j) = ϕi ( j) = (τϕi )( j).

speciálisan következik, hogy minden Ebbol mutációra fennáll, hogy minden

(i+1)

G

G(i) ϕi -beli µ

lexikograkusan legkisebb per-

ϕi+1 -beli permutációnak egyeznie kell µ-vel az elso i

elemre. Ezen kívül minden

σ ∈ G(i+1) -re és a fent deniált

(σϕi+1 )(i

x

= ϕi (y) elemre fennáll

+ 1) = ϕi+1 (i + 1) = (τi ϕi )(i + 1) = x.

G(i+1) ϕi+1 = {ϕ ∈ G(i) ϕi | ϕ(i + 1) = x}. Az állítás ezután abból a ténybol (i) következik, hogy a G ϕi -beli lexikograkusan legkisebb µ permutációra fennáll µ(i + 1) = Természetesen x. Ezzel megmutattuk, hogy a LERC algoritmus hatékonyan és helyesen muködik.

a 4.25. következménnyé (lásd a 4-3.. feladatot). Ehhez A 4.24. tétel könnyen kibovíthet o tételét, a 4.26. tételt. kapcsolódóan bebizonyítjuk az alfejezet fo

G ≤ Sn egy permutációcsoport, ahol G = hGi, valamint leπ és ψ két permutáció Sn -ben. Ekkor létezik olyan algoritmus, amely (G, π, ψ) bemenet mellett polinomiális idoben meghatározza ψGπ lexikograkusan legkisebb permutációját.

4.25. következmény. Legyen gyen

4.26. tétel (Arvind és Kurur). A

GI probléma SPP-beli.

156


Bizonyítás. Az

AUTO

probléma a következoképp deniált: számítsuk ki egy adott G gráf-

hoz az Aut(G) automorzmus-csoportot (a fogalmak értelmezéséhez lásd a 3.6 deníciót és bekezdést, valamint a 3.8 deníciót). Mathon eredményei alapján alapján az az azt követo

AUTO és a GI problémák Turing-ekvivalensek, tehát AUTO ∈ FPGI és GI ∈ PAUTO , ezért elég AUTO FPSPP -beliségét megmutatni. Ezután SPP 4.23. tételbeli önmagával alsó ( self-low) AUTO tulajdonságából következik, hogy GI P ⊆ SPPSPP ⊆ SPP-beli, amivel a tételt be is láttuk. SPP Célunk tehát, hogy találjunk AUTO-hoz egy FP -algoritmust. Ennek az algoritmusnak Sn−1 egy adott G gráf esetén egy S = T er os generátort kell kiszámítania Aut(G)-hez, ahol i i=1 id

= Aut(G)(n) ≤ Aut(G)(n−1) ≤ · · · ≤ Aut(G)(1) ≤ Aut(G)(0) = Aut(G)

az Aut(G) stabilizátorainak lánca, T i (1 reprezentáns rendszere Aut(G)

(i−1)

≤

i

generátort Aut(G) egy eros

Sn−1

=

generátort Aut(G) T j eros j=i SPP

FP

-algoritmus Aut(G)

(i)

n) pedig Aut(G) (n)

-ben. A triviális Aut(G)

generátort Aut(G) lépésre építünk fel egy eros (0)

≤

(i)

=

(i)

egy teljes jobb oldali

id esettel kezdve lépésrol

i mellett, végül tehát kapunk -hez, csökkeno

Aut(G)-hez. Tegyük fel tehát, hogy már találtunk egy S i (0)

=

=

Aut(G)-hez. Most leírjuk, hogyan határozza meg az (i−1)

egy teljes jobb oldali reprezentáns rendszerét Aut(G)

-ben,

T i−1 -et. Ehhez deniáljuk az

        A = (G , S , i, j, π)      

⊆ Aut(G) és hS i egy pontonkénti stabilizátora [i]-nek Aut(G)-ben, π egy pontonként [i − 1] által stabilizált parciális permutáció és π(i) = j, valamint létezik egy τ ∈ Aut(G)(i−1) , ahol τ(i) = j és LERC(S , τ) a π bovítése S

              

halmazt. A 4.24. tétel alapján a hS iτ jobb oldali co-halmazhoz tartozó LERC(S , τ) lexiko grakusan legkisebb permutáció polinomiális idoben kiszámítható a LERC algoritmus se-

π parciális permutáció a (G, S , i, j, π) bemenet része, mivel az A halmazt mint τ ∈ Aut(G)(i−1) , τ(i) = j melletti permutáció prexkereséses meghatározásakor (vessük ezt össze a 4.5. példa N-P-I

gítségével. A

orákulumot szeretnénk használni a lexikograkusan legkisebb algoritmusával).

hogy ha Az N algoritmus egy NPTM A orákulumhoz, tehát A NP-beli. Eldöntendo,

τ(i) =

j, akkor fennáll-e hS iτ jobb oldali co-halmaz minden

σ permutációjára σ(i) = j.

N(G , S , i, j, π)

⊆ Aut(G)(i)

1

ellenorizzük, hogy S

2

találjunk ki nemdeterminisztikusan egy

3

if

τ ∈ Aut(G)(i−1)

és

τ(i) =

j és

4

then elfogadás és megállás

5

else elutasítás és megállás

τ ∈ Sn permutációt B G n csúcsú. τ a π bovítése és τ = LERC(S , τ)

Most megmutatjuk, hogy N elfogadó útjainak száma (G , S , i, j, π) bemenet mellett vagy 0 vagy 1, amennyiben hS i

= Aut(G)(i) , valamint általában fennáll n o (i) accN (G , S , i, j, π) ∈ 0, |Aut(G) |/|hS i| .

Eloször egy pszeudokódot adunk meg.


157

M-A(G) 1 2 3 4 5 6 7 8 9 10 11 12

T i ← {} minden i-re, ahol 0 ≤ i ≤ n − 2 B G n csúcsú. B T i az Aut(G)(i+1) egy teljes jobb oldali reprezentáns rendszere lesz Aut(G)(i) -ben. S i ← ∅ minden i-re, ahol 0 ≤ i ≤ n − 2 (i) generátor lesz Aut(G) -hez. S n−1 ← {id} B S i egy eros for i ← n − 1 downto 1 do B Az i-edik iteráció kezdetén S i -t már megtaláltuk, most S i−1 -et számítjuk ki. legyen π : [i − 1] → [n] parciális permutáció π(a) = a-val minden a ∈ [i − 1]-re B i = 1 esetén π a deniálatlan parciális permutáció. for j ← i + 1 to n do π ← πj B Tehát π bovíti π-t az (i, j) párral π (i) = j mellett. if (G , S i , i, j, π ) ∈ A (i−1) then B A prexkeresés eloállítja a legkisebb Aut(G) -beli, j-re képezo permutációt. i-rol

13

for k

14

← i + 1 to n

do keressük meg az (G , S i , i, j, π` )

` elemet, π leképezésein kívül, A mellett

π ← π` B π most egy teljes Sn -beli permutáció. T i−1 ← T i−1 ∪ π

15 16 17

B T i−1 most az Aut(G)(i)

18

(i−1)

rendszere Aut(G) 19 20

∈

S i−1

egy teljes jobb oldali reprezentáns -ben.

← S i ∪ T i−1 (0) generátor Aut(G) = Aut(G) -hoz. B S 0 egy eros

return S 0

Tegyük fel, hogy (G , S , i, j, π) A-beli. Ha

τ(i) =

j egy

τ∈

Aut(G)

akkor az hS iτ jobb oldali co-halmaz pontosan azokból az Aut(G)

(i−1)

(i−1)

mellett és j

>

i,

-beli permutációkból

áll, melyek i-t j-re képezik le. Következésképp N(G , S , i, j, π) egyetlen elfogadó útja megfelel az egyértelmuen meghatározott lexikograkusan legkisebb nak. Ha viszont hS i az Aut(G)

(i)

τ = LERC(S , τ) permutáció(i) τ ábrázolható az hS i

egy valódi alcsoportja, akkor Aut(G)

= |Aut(G)(i) |/|hS i| darab diszjunkt jobb oldali co-halmazának egyesítéseként. Általában tehát N(G , S , i, j, π) akkor rendelkezik k elfogadó úttal, ha (G , S , i, j, π) A-beli, egyébként k

pedig nincs elfogadó útja. A

Az M-A egy FP -algoritmus

AUTO

képp minden valóban feltett q kérdésre fennáll accN (q) ebbol

AUTO ∈ FPSPP

= = Aut(G)(i) , következés-

megoldásához. Itt az M DPOTM csak olyan q

(G , S i , i, j, π) kérdéseket tesz fel az A orákulumnak, melyekre hS i i

≤

1. A 4.23. tétel 4. része alapján

következik.

= Aut(G)(0) -hoz n szerinti teljes indukcióval mutatjuk meg. Az indukció kezdete az n − 1, S n−1 = {id} pedig (n−1) Az indukciós lépéshez feltesszük, hogy az i-edik természetesen Aut(G) = id-t állítja elo. generátor Aut(G) Az állítást miszerint M-A(G) S 0 kimenete egy eros

(i)

generátor Aut(G) iteráció kezdetekor már rendelkezésre áll egy S i eros hogy az i-edik iteráció végére az S i−1 (i−1)

Si

-hez. Megmutatjuk,

(i−1) generátor Aut(G) ∪ T i−1 halmaz egy eros (G , S i , i, j, π ) ∈ A? kérdéssel megvizsgáljuk,

+1 ≤ j ≤ na -ben létezik-e olyan permutáció, amely i-t j-re képezi le. A rákövetkezo

hez. Minden j-hez, ahol i hogy Aut(G)

=

kérdésekkel eloállítja perxkeresés az A orákulumhoz intézett megfelelo a lexikograkusan

158

4. Bonyolultságelmélet (i−1)

legkisebb π permutációt Aut(G)

-ben π (i) = j mellett. Mint fent megállapítottuk, ekkor generátor ≤ 1-nek megfelelo q kérdéseket intézünk, mivel S i egy eros (i) (i) Aut(G) -hez, tehát hS i i = Aut(G) . A permutáció eloállítása után az i-edik iteráció végén (i) (i−1) T i−1 Aut(G) egy teljes jobb oldali átlója Aut(G) -ben, következésképp S i−1 = S i ∪ T i−1 A-hoz csak accN (q)

generátor Aut(G) egy eros Aut(G)

= Aut(G)

(0)

(i−1)

generátort -hez. Végül n iteráció után megtalálunk egy S 0 eros

-hoz.

két állításából közvetlenül adódik a 4.27. következmény. A 4.23. tétel elso

4.27. következmény.

GI alsó SPP-re és PP-re, tehát SPPGI = SPP és PPGI = PP.

Gyakorlatok

4.4-1. A 4.14. deníció alapján fennáll A ≤ P

A

⊆P

B

p T

B

⇐⇒

A

p

∈ PB . Mutassuk meg, hogy A ≤T B ⇐⇒

.

4.4-2. Mutassuk meg, hogy a 4.5. példában deniált Pre-Iso halmaz NP-beli, valamint hogy az N-P-I algoritmus N gépe egy DPOTM, tehát polinomiális idoben dolgozik.

b és H b gráfokhoz az Iso(G b, H) b izomorz4.4-3. Határozzuk meg a 4.6. példában deniált G muscsoportot. osztályok közül melyek ígéret-osztályok: NP és coNP, RP és coRP, 4.4-4. A következo AM és coAM, MA és coMA? Tartozhatnak-e az ígéret-osztályokhoz teljes problémák? A válaszokat indokoljuk.

Feladatok 4-1. Eros NPOTM NPOTM, vagyis a végállapotok Egy eros NPOTM egy három végállapot típussal rendelkezo F halmaza F a , F r és F ? halmazokra bontható. Ekkor teljesül, hogy amennyiben x

∈

A, akkor

B

M (x) rendelkezik egy olyan úttal, ami egy F a -beli állapotban végzodik, és nem rendelkezik olyan úttal, amely F r -beli állapotban végzodik. Ha azonban x

<

B

A, akkor M (x) rendelkezik

egy olyan úttal, ami egy F r -beli állapottal végzodik, és nem rendelkezik olyan úttal, ami B

F a -beli állapottal végzodik. Az M (x) mindkét esetben végzodhet bizonyos utakon F ? -beli NPOTM tehát olyan gép, ami nem tudom válasznak. Az eros két állítást: sosem hazudik. Bizonyítsuk a következo

állapotban, ami megfelel a

•

A≤

NP

•

A≤

NP

sT

sT

B

NPOTM, mellyel A = ⇐⇒ létezik M eros

B

⇐⇒ NPA ⊆ NPB .

B

L(M ).

Útmutatás. Általánosítsuk a 4.4-1. gyakorlatot. 4-2. Bizonyítás Bizonyítsuk a 4.16. és 4.18. tételek állításait. 4-3. Bizonyítás módosítása Módosítsuk a 4.24. tétel bizonyítását úgy, hogy abból adódjon a 4.25. következmény.

4. fejezet megjegyzései

159

Algoritmus

Típus

3-SAT

vISSZALÉPÉS

det.

O(1.913 )

4-SAT O(1.968 )

O(1.987 )

O(1.995 )

Monien és

det.

O(1.618 )

O(1.839 )

O(1.928 )

O(1.966 )

det.

O(1.481 )

O(1.6 )

O(1.667 )

O(1.75 )

Paturi et al. [47]

val.

O(1.362 )

O(1.476 )

O(1.569 )

O(1.637 )

Schöning [60]

val.

O(1.334 )

O(1.5 )

O(1.6 )

O(1.667 )

Iwama és Tamaki [31]

val.

O(1.324 )

O(1.474 )

n n

5-SAT n n

6-SAT n n

n n

Speckenmeyer [45] Dantsin et al. [13]

n

n n

n

n

n

n

n

n

n

n

n

n

n

4.9. ábra. Néhány a kielégíthetoség problémát megoldó algoritmus futási ideje.

Megjegyzések a fejezethez A 3. és 4. fejezetek egyes részei a [56] könyvön alapulnak. Amit itt csak erosen tömörített formában tudtunk bemutatni, ott megtalálható átfogó és minden technikai részletre kiterjedo változatban, terjedelmes példákkal, nagyobb számokkal, szebb és több ábrával, pontosabb magyarázatokkal és kidolgozottabb bizonyításokkal. Ilyen módon megtalálhatók [56]-ben itt most lemondtunk, mint a 4.16., 4.18. és 4.23. tételek, olyan bizonyítások, melyekrol valamint a 4.20. lemma bizonyításai. Ehhez képest a 3. és ezen 4. fejezet elonye, hogy és pontos. rövid, feszes és tömör, mindazonáltal értheto Bonyolultságelmélethez nagyobb háttéranyag található például a [29, 46, 72, 73] köny munkájában [70]. A 4.4. és a 4.5. vekben. A Turing-gépet Alan Turing vezette be úttöro táblázatot Garey és Johnson [16] készítették. A klasszikus [16] az NP-teljesség elméletéhez még ma is értékes forrásnak számít. A 4.7. tételnél említett több ezer NP-teljes probléma egy több száz darabos gyujteménye szintén megtalálható Garey és Johnson [16] könyvében. A 4.10. tétel bizonyítása megtalálható más könyvekben is, például [16] és [46]. A

3-SAT prob-

léma determinisztikus idobonyolultságánál említett oszd-meg-és-uralkodj algoritmust Monien [45], a lokális keresésen alapuló megoldást pedig Dantsin és társai [13] publikálták. A véletlen séta algoritmus Schöning [60, 62] munkáin alapszik. A Cook [10], a

≤

p m -visszavezethetoséget

p

≤T -visszavezethetoséget

Karp [32] vezették be. Ladner, Lynch és Selman [38]

cikke átfogó és mélyreható mu a bonyolultság-korlátozott visszavezethetoségek tanulmányozásához. A 4.4-1. gyakorlat, valamint a 4-1. feladat alapjait Selman [63] cikke jelenti. korlátot Dantsin és társai [13] érték el Az eddigi legjobb O(1.481 ) felso

k-SAT deter≥ 3 esetén. Schöning itt bemutatott valószínuségi algoritkorlátozott lokális keresés ismétléssel [60] ötleten alapszik. A k-SAT problémához n

minisztikus idobonyolultságára k musa a k

≥

4 mellett Paturi és társai [47] algoritmusa kissé még jobb. A jelenlegi legjobb valószí-

nuségi algoritmus

3-SAT-hoz

és

4-SAT-hoz

Iwama és Tamaki [31] munkáján alapul. Az o

algoritmusuk ügyesen ötvözi Paturi et al. [47] és Schöning [60] algoritmusait, és megköze lítoleg O(1.324 ) futási idovel rendelkezik. A n

k-SAT

ezen algoritmusa k

≥

5 mellett nem

jobb mint Paturi et al. [47] algoritmusa. A 4.9. ábra áttekintést nyújt a fejezetben tárgyalt és néhány további kielégíthetoség problémát megoldó algoritmusról. A jelenlegi legjobb algoritmusok félkövér szedéssel szerepelnek. A grázomorzmus problémával Köbler, Schöning és Torán [35] könyve foglalko-

160


zik átfogó jelleggel, elsosorban bonyolultságelméleti szempontok szerint. Hoffman [30] csoportelméleti algoritmusokat vizsgált

GI-hoz.

A 4.11. tételt Ladner [37] publikálta, az

alacsony- és magas bonyolultsági osztályhierarchiákat Schöning [58] vezette be. A 4.13. tételnél használt lexikograkus rendezés megtalálható Rothe [56] cikkében. Gál et al. [17] mutatták meg, hogy teljes izomorzmus konstruálható O(lg n) méretu parciális izomorzmusból két, egyenként n csúcsú izomorf gráfhoz. Ezt az eredményt a 4.13. tétel optimálisra javítja fel, kimondja, hogy ehhez már egy 1 méretu parciális izomorzmus is elegendo. Ezen tétel, valamint a 4.6. példa Größe, Rothe és Wechsung [24] munkájára alapszik. A polinomiális ido-hierarchiát Meyer és Stockmeyer [42, 69] vezették be, akik bizonyítot ták többek között a 4.16. tétel állításait. Az alsó- és felso-hierarchiát Schöning vezette

GI Low2 GI alsóságára vonatkozóan

be [58], valamint bizonyította a 4.18. tétel állításait [58] és megmutatta, hogy beli [59]. Köbler et al. [33, 34] közöltek eloször eredményeket

valószínuségi osztályok, mint amilyen PP ellenében. Eredményeiket Arvind és Kurur [2] javították, akik bebizonyították, hogy

GI

még SPP-beli is. Az univerzális hasítás módsze-

rét Carter és Wegman [9] írták le 1979-ben. A 4.20. lemma Carter és Wegman [9] munkáján alapszik. Az SPP a Valiant [71] által bevezetett UP osztály általánosítása. Az SPP és más ígéret osztályok alapos tanulmányozásával számos munka foglalkozik, például [2, 7, 15, 26, 33, 34, 51, 55], a 4.23 tételben felsorolt tulajdonságok is megtalálhatók ezen muvekben [15, 34, 35]. A 4.26 tétel bizonyításához szükséges Turing-ekvivalenciát

AUTO és

GI problémák közt Mathlon [41] mutatta meg (lásd még [35]). Magyar nyelvu, bonyolultságelmélettel foglalkozó szakkönyvek Cormen, Leiserson, Rivest és Stein [12], Lovász [40], Papadimitriou [46], valamint Rónyai Lajos, Ivanyos Gábor és Szabó Réka [53] muve. köszönetet mond Uwe Schöning-nek hasznos észrevételeiért ezen fejezet egy A szerzo korábbi változatához. Leginkább Uwe Schöning eloadásfóliáin alapul a 4.3. alfejezet V´ ´SAT algoritmusának valószínuségi elemzése, amely az eredeti érvelés egy egyszerusítése. Ennek részletesebb elemzése olvasható könyvében [61]. Ezen kívül hálás köszönet illeti Dietrich Stoyant, Sigurd Assingt és Holger Spakowskit a 3. és 4. fejezetek korábbi válto a Német Kutatási Társaság (Deutsche zatainak korrektúra-olvasásáért. Támogatta a szerzot Forschungsgemeinschaft DFG) a RO 1202/9-1 azonosítószám alatt.

Irodalomjegyzék

[1] M. Agrawal, N. Kayal, N. M. Saxena. PRIMES is in P. Available at http://www.cse.iitk.ac.in/users/ manindra/primality.ps, 2002. 123 [2] V. Arvind, P. Kurur. Graph isomorphism is in SPP. In Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science, 743750. o. IEEE Computer Society Press, 2002. 160 [3] L. Babai. Trading group theory for randomness. In Proceedings of the 17th ACM Symposium on Theory of Computing, 421429. o. ACM Press, 1985. 123, 124 [4] L. Babai, S. Moran. Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes. Journal of Computer and Systems Sciences, 36(2):254276, 1988. 123, 124 [5] A. Beygelzimer, L. Hemaspaandra, C. Homan, J. Rothe. One-way functions in worst-case cryptography: Algebraic and security properties are on the house. SIGACT News, 30(4):2540, 1999. 124 [6] D. Boneh. Twenty years of attacks on the RSA cryptosystem. Notices of the AMS, 46(2):203213, 1999. 123, 124 [7] B. Borchert, L. Hemaspaandra, J. Rothe. Restrictive acceptance suffices for equivalence problems. London Mathematical Society Journal of Computation and Mathematics, 86:8695, 2000. 160 [8] L. Buttyán, I. Vajda. Kriptográa és alkalmazásai (Cryptography and its Applications). Typotex, 2004. 124 [9] J. L. Carter, M. N. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences, 18(2):143154, 1979. 160 [10] S. Cook. The complexity of theorem proving procedures. In Proceedings of the Third Annual ACM Symposium on Theory of Computing, 151158. o. ACM Press, 1971. 159 [11] D. Coppersmith. Small solutions to polynomial equations, and low exponent RSA vulnerabilities. Journal of Cryptology, 10(4):233260, 1997. 123 [12] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to Algorithms. The MIT Press/McGrawHill, 2004 (Második kiadás ötödik, javított utánnyomása. Magyarul: Új algoritmusok. Scolar Kiadó, 2003). 160 [13] E. Dantsin, A. Goerdt, R. Kannan, J. Kleinberg, C. Papadimitriou, P. Raghavan, U. Schöning. A deterministic (2 − 2/(k + 1)) algorithm for k-sat based on local search. Theoretical Computer Science, 289(1):6983, 2002. n

159 [14] W. Diffie, M. E. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, IT22(6):644654, 1976. 123 [15] S. Fenner, L. Fortnow, S. Kurtz. Gap-denable counting classes. Journal of Computer and System Sciences, 48(1):116148, 1994. 160 [16] M. R. Garey, D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. 159 [17] A. Gál, S. Halevi, R. Lipton, E. Petrank. Computing from partial solutions. In Proceeding of the 14th Annual IEEE Conference on Computational Complexity, 3445. o. IEEE Computer Society Press, 1999. 160 [18] O. Goldreich. Randomness, interactive proofs, and zero-knowledge a survey. In R. Herken (szerkeszto), The Universal Turing Machine: A Half-Century Survey, 377405. o. Oxford University Press, 1988. 124 [19] O. Goldreich. Foundations of Cryptography. Cambridge University Press, 2001. 124 [20] O. Goldreich, S. Micali, A. Wigderson. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. Journal of the ACM, 38(3):691729, 1991. 123

162

Irodalomjegyzék

Computational Complexity Theory, [21] S. Goldwasser. Interactive proof systems. In J. Hartmanis (szerkeszto), AMS Short Course Lecture Notes: Introductory Survey Lectures. Proceedings of Symposia in Applied Mathematics 38. kötete, 108128. o. American Mathematical Society, 1989. 124 [22] S. Goldwasser, S. Micali, C. Rackoff. The knowledge complexity of interactive proof systems. SIAM Journal on Computing, 18(1):186208, 1989. 123, 124 [23] S. Goldwasser, M. Sipser. Private coins versus public coins in interactive proof systems. In S. Micali (szer keszto), Randomness and Computation, Advances in Computing Research 5. kötete, 7390. o. JAI Press, 1989. A preliminary version appeared in Proc. 18th Ann. ACM Symp. on Theory of Computing, 1986, pp. 59 68. 123 [24] A. Große, J. Rothe, G. Wechsung. Computing complete graph isomorphisms and hamiltonian cycles from partial ones. Theory of Computing Systems, 35(1):8193, 2002. 160 [25] J. Håstad. Solving simultaneous modular equations of low degree. SIAM Journal on Computing, 17(2):336 341, 1988. Special issue on cryptography. 123 [26] J. Hartmanis, L. Hemachandra. Complexity classes without machines: On complete languages for UP. Theoretical Computer Science, 58(13):129142, 1988. 160 [27] L. Hemaspaandra, K. Pasanen, J. Rothe. If P

, NP then some strongly noninvertible functions are invertible.

In Proceedings of the 13th International Symposium on Fundamentals of Computation Theory, Lecture Notes in Computer Science 2138. kötete, 162171. o. Springer-Verlag, 2001. 123, 124 [28] L. Hemaspaandra, J. Rothe. Creating strong, total, commutative, associative one-way functions from any one-way function in complexity theory. Journal of Computer and Systems Sciences, 58(3):648659, 1999. 123, 124 [29] L. A. Hemaspaandra, M. Ogihara. The Complexity Theory Companion. EATCS Texts in Theoretical Computer Science. Springer-Verlag, 2002. 159 [30] C.

Hoffman

(szerkeszto).

Group-Theoretic

Algorithms

and

Graph

Isomorphism,

Lecture

Notes

in

Computer Science 136. kötete. Springer-Verlag, 1982. 160 [31] K. Iwama, S. Tamaki. Improved upper bounds for 3-SAT. Technical Report TR03-053, Electronic Colloquium on Computational Complexity, 2003. 159 [32] R. M. Karp. Reducibility among combinatorial problems. In R. E. Miller, J. W. Thatcher (szerkesztok), Complexity of Computer Computations, 85103. o. Plenum Press, 1972. 159 [33] J. Köbler, U. Schöning, S. Toda, J. Torán. Turing machines with few accepting computations and low sets for PP. Journal of Computer and System Sciences, 44(2):272286, 1992. 160 [34] J. Köbler, U. Schöning, J. Torán. Graph isomorphism is low for PP. Computational Complexity, 2:301330, 1992. 123, 160 [35] J. Köbler, U. Schöning, J. Torán. The Graph Isomorphism Problem: Its Structural Complexity. Birkhäuser, 1993. 124, 159, 160 [36] J. Ködmön. Kriptográa: Az informatikai biztonság alapjai, a Pgp kriptorendszer használata (Cryptography: Bases of the Security of Computer Systems. Use of Cryptosystem Pgp). Computerbooks, 2002. 124 [37] R. Ladner. On the structure of polynomial time reducibility. Journal of the ACM, 22(1):155171, 1975. 160 [38] R. Ladner, N. A. Lynch, A. Selman. A comparison of polynomial time reducibilities. Theoretical Computer Science, 1(2):103124, 1975. 159 [39] A. Lenstra, H. Lenstra. The Development of the Number Field Sieve, Lecture Notes in Mathematics 1554. kötete. Springer-Verlag, 1993. 123 [40] L. Lovász. Algoritmusok bonyolultsága (Complexity of Algorithms). ELTE TTK, 1990. 160 [41] R. Mathon. A note on the graph isomorphism counting problem. Information Processing Letters, 8(3):131 132, 1979. 160 [42] A. Meyer, L. Stockmeyer. The equivalence problem for regular expressions with squaring requires exponential space. In Proceedings of the 13th IEEE Symposium on Switching and Automata Theory, 125129. o., 1972. 160 [43] D. Micciancio, S. Goldwasser. Complexity of Lattice Problems: A Cryptographic Perspective, The Kluwer International Series in Engineering and Computer Science 671. kötete. Kluwer Academic Publishers, 2002. 123 [44] G. L. Miller. Riemann's hypothesis and tests for primality. Journal of Computer and Systems Sciences, 13(3):300317, 1976. 123 n

[45] B. Monien, E. Speckenmeyer. Solving satisability in less than 2 10:287295, 1985. 159

steps. Discrete Applied Mathematics,

Irodalomjegyzék

163

[46] C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994 (Magyarul: Kiszámítási bonyolultság, Novadat, 1999). 124, 159, 160 [47] R. Paturi, P. Pudlák, M. Saks, F. Zane. An improved exponential-time algorithm for k-SAT. In Proceedings of the 39th IEEE Symposium on Foundations of Computer Science, 628637. o. IEEE Computer Society Press, 1998. 159 [48] J. M. Pollard. Theorems on factorization and primality testing. Proceedings of the Cambridge Philosophical Society, 76:521528, 1974. 123 [49] M. Rabi, A. Sherman. An observation on associative one-way functions in complexity theory. Information Processing Letters, 64(5):239244, 1997. 124 [50] M. O. Rabin. Probabilistic algorithms for testing primality. Journal of Number Theory, 12(1):128138, 1980. 123 [51] R. Rao, J. Rothe, O. Watanabe. Upward separation for FewP and related classes. Information Processing Letters, 52(4):175180, 1994 (Corrigendum appears in the same journal,74(12):89, 2000). 160 [52] R. L. Rivest, A. Shamir, L. M. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2):120126, 1978. Lásd még az U.S. Patent 4 405 829 számú szabadalmat. 123 [53] L. Rónyai, G. Ivanyos, R. Szabó. Algoritmusok (Algorithms). Typotex, 1999. 160 [54] J. Rothe. Some facets of complexity theory and cryptography: A ve-lecture tutorial. ACM Computing Surveys, 34(4):504549, 2002. 123, 124 [55] J. Rothe. A promise class at least as hard as the polynomial hierarchy. Journal of Computing and Information, 1(1):92107, 1995. 160 [56] J. Rothe. Complexity Theory and Cryptology. An Introduction to Cryptocomplexity. EATCS Texts in Theoretical Computer Science. Springer-Verlag, 2005. 159, 160 [57] A. Salomaa. Public-Key Cryptography, EATCS Monographs on Theoretical Computer Science 23. kötete. Springer-Verlag, 2. kiadás, 1996. 123, 124 [58] U. Schöning. A low and a high hierarchy within NP. Journal of Computer and System Sciences, 27:1428, 1983. 160 [59] U. Schöning. Graph isomorphism is in the low hierarchy. Journal of Computer and System Sciences, 37:312 323, 1987. 160 [60] U. Schöning. A probabilistic algorithm for k-SAT based on limited local search and restart. In Proceedings of the 40th IEEE Symposium on Foundations of Computer Science, 410414. o. IEEE Computer Society Press, 1999. 159 [61] U. Schöning. Algorithmik. Spektrum Akademischer Verlag, 2001. 160 [62] U. Schöning. Ideen der Informatik. Oldenbourg Verlag, 2002. 159 [63] A. Selman. Polynomial time enumeration reducibility. SIAM Journal on Computing, 7(4):440457, 1978. 159 [64] A. Shamir. IP

= PSPACE.

Journal of the ACM, 39(4):869877, 1992. 123

[65] C. Shannon. Communication theory of secrecy systems. The Bell Systems Technical Journal, 28(4):657715, 1949. 123 [66] S. Singh. The Code Book. The Secret History of Codes and Code Breaking. Fourth Estate, 1999 (Magyarul: Kódkönyv. A rejtjelezés és rejtjelfejtés története. Park Könyvkiadó, 2002). 123, 124 [67] R. Solovay, V. Strassen. A fast Monte Carlo test for primality. SIAM Journal on Computing, 6:8485, 1977. Erratum appears in the same journal, 7(1):118, 1978. 123 [68] D. Stinson. Cryptography: Theory and Practice. CRC Press, 2002 (2. kiadás). 123, 124 [69] L. Stockmeyer. The polynomial-time hierarchy. Theoretical Computer Science, 3(1):122, 1977. 160 [70] A. Turing. On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, ser. 2, 2:230265, 1936 (Correction, ibid, vol. 43, pp. 544546, 1937). 159 [71] L. G. Valiant. The relative complexity of checking and evaluating. Information Processing Letters, 5(1):20 23, 1976. 160 [72] K. Wagner, G. Wechsung. Computational Complexity. D. Reidel Publishing Company, 1986 (and Kluwer Academic Publishers, 2001). 159 [73] G. Wechsung. Vorlesungen zur Komplexitätstheorie, 32. kötet. B. G. Teubner Verlagsgesellschaft, 2000. 159 [74] S. Zachos, H. Heller. A decisive characterization of BPP. Information and Control, 69:125135, 1986. 124

Tárgymutató

A, Á

izomorzmus, 104

alsó-hierarchia, 146, 150 asszociativitás, 101, 116gy

gráfautomorzmus probléma, 104 grázomorzmus probléma, 104, 145, 151, 153

B bonyolultságelmélet,

GY gyur u, 101 egység, 102 egységelem, 102

C

kommutatív, 101

97 Caesar-rejtjelezo, Church-tézis, 127, 134gy

nullelem, 101 nullosztó, 102

CS

H

csoport, 101 generátorrendszer, 103

Hamming-távolság, 142 hármasítás, 135

kommutatív, 101

háromdimenziós párosítás, 135, 136, 137

rend, 101

3-SAT, 135 hasítás, 151 házasítás probléma, 136 hitelesség, 110

D determinisztikus idobonyolultság, 131 determinisztikus Turing-gép, 128 DiffieHellman-protokoll, 94 diszkrét logaritmus, 108

I, Í inverz, 101 inverz elem, 101 inverz mátrix, 99 izomorzmuscsoport, 158gy

E, É egyirányú függvény, 108 egységcsoport, 122 elem invertálható, 102 inverz, 101 generátor, 103 eros Euler-féle

ϕ függvény, 102

K kétdimenziós párosítás, 135, 136 kielégíthetoség probléma, 135, 140 kiszámítható függvény, 129 klikk, 149 kompozíció, 103 konjunktív normálforma, 135

F fa, 122 levél, 122 félcsoport, 101 felso-hierarchia, 146, 150 fokszám, 104

kriptoanalízis, 95 kriptográa, 94124 kriptológia, 95 kriptorendszer, 96 aszimmetrikus, 96, 99 monoalfabetikus, 97 nyilvános kulcsú, 110 polialfabetikus, 97

G

szimmetrikus, 96, 99

gráf automorzmus, 104 diszjunkt egyesítés, 104

kulcscsere-probléma, 94 kulcs tér, 96

Tárgymutató

165

L

eltolásos, 96

LERC, 155

helyettesítéses, 99 99 Hill-rejtjelezo,

M

monoalfabetikus, 99 permutációs, 99

M-A, 157

polialfabetikus, 99

MA az ArthurMerlin hierarchiában, 118 mátrix

transzpozíciós, 99 relativizálható bonyolultsági osztály, 146

adjungált, 99 determináns, 99

reprezentánsrendszer

inverz, 99

részcsoport, 101

jobb oldali, 103

mellékosztály jobb oldali, 103 M-G, 157 M-R, 112

M - ´ , 109 ´ ´ Monte-Carlo-algoritmus, 112

S SAT, 135 semleges elem, 101 stabilizátor, 103 stabilizátor lánc, 103

N N, 156 négyzetes szita, 115

SZ személyazonosítás, 117

nemdeterminisztikus idobonyolultság, 131 nemdeterminisztikus Turing-gép, 128

sztochasztikus automata, 142

NP-teljesség, 134

T támadás

N-P-I, 147 nullosztó, 102

aktív, 110 faktorizálási, 115 NY

középen állás támadás, 110

nyílt szöveg, 96 nyilvános kulcs, 96

nyílt szövegu, 100 passzív, 110

nyilvános kulcsú kriptográa, 95 nyilvános kulcsú kriptorendszer, 95

rejtett szövegu, 97, 100 kulcs, 100 rejtjelezo választott nyílt szövegu, 114 választott szövegu, 100 test, 101, 102

O, Ó orákulum, 146

titkos kulcs, 96

orákulumos Turing-gép, 146

tökéletes titkosság, 101

Ö, O

Turing-gép szintaxisa, 128 Turing-visszavezethetoség, 146, 149

148 ön-visszavezethetoség,

Turing-gép, 127, 128áb, 146 Turing-gép szemantikája, 129

U, Ú

P pálya, 103

univerzális hasítás, 151

párosítás, 136 periódus, 97 permutáció, 103 identikus, 103

Ü, U üzenet, 96

permutációcsoport, 102 permutációcsoportok, 102 polinomiális ido-hierarchia, 146, 149, 150áb primitív gyök, 107 probléma

DiffieHellman-probléma, 109

protokoll zéró-ismeretu, 119

V választott szövegu támadás, 123 véges állapotú vezérloegység, 128 V´ ´-SAT, 143 véletlen séta, 142 Vigenère-négyzet, 97 visszalépés, 140, 141

V ´  ´ -SAT, 141, 145gy 134, 140gy visszavezethetoség,

R rejtett szöveg, 96 rejtjelezo 99 blokkrejtjelezo, affin, 99

lineáris, 99

Z zártság, 101 zéró-ismeretu protokoll, 119

Névmutató

A, Á

Hemachandra, L., 162

Adleman, Leonard, 123 Agrawal, Manindra, 123, 161

Hemaspaandra, Lane A., 124, 161, 162 Herken, R., 161

Arvind, V., 161

Hill, Lester, 99

Assing, Sigurd, 160

Hoffman, C., 160, 162 Homan, C., 161 Håstad, Johan, 123, 162

B Babai László, 123, 124, 161 Babbage, Charles, 101, 123 Beygelzimer, A., 161 Boneh, D., 161 Borchert B., 161

I, Í Ivanyos Gábor, 163 Iwama, K., 159, 162

Buttyán Levente, 161 J C

Johnson, David S., 136, 159

Carter, J. L., 160, 161 Church, A., 127 Cook, Stephen, 135, 159 Cook, Stephen Arthur, 161 Coppersmith, Don, 123 Cormen, Thomas H., 161

K Kannan, Ravindran, 161 Karp, Richard M., 159, 162 Kayal, Neeraj, 123, 161 Kleinberg, J., 161 Köbler, J., 159, 160, 162

D Dantsin, E., 142, 159, 161 de Fermat, Pierre, 102

Ködmön József, 162 Kurtz, Stefan, 161 Kurur, P., 161

Diffie, Whiteld, 94, 161

F Fenner, S., 161 Fortnow, L., 161

G Gál Anna, 160, 161 Garey, Michael R., 136, 159, 161 Goerdt, A., 161 Goldreich, Oded, 123, 124, 161

Goldwasser, Shaffi, 123, 124, 161, 162 Große, André, 160, 162

L Ladner, Richard E., 145, 150, 159, 160, 162 Leiserson, Charles E., 161 Lenstra, Arjen K., 162 Lenstra, H., Jr., 162 Leonhard, Euler, 107 Lipton R., 161 Lovász László, 162 Lynch, Nancy Ann, 159, 162

M Mathon, R., 162 Meyer, A., 160, 162 Micali, S., 123, 161, 162

H Halevi, Shai, 161 Hartmanis, Juris, 161, 162 Heller, H., 163 Hellman, Martin E., 94, 161

Micciancio, D., 162 Miller, Gary L., 123, 162 Miller, Raymond E., 162 Monien, B., 142, 159, 162 Moran, S., 123, 161

Névmutató O, Ó Ogihara, M., 162

167 Speckenmeyer, 142, 162 Stein, Clifford, 161

Stinson, Douglas, 123, 124, 163 P

Stockmeyer, L., 160, 163 Stoyan, Dietrich, 160

Papadimitriou, Christos H., 124, 161, 162

Strassen, V., 123, 163

Pasanen, Kari, 162 Paturi, R., 159, 162 Petrank, Erez, 161 Pollard, John M., 123, 163

SZ Szabó Réka, 163

Pudlák, P., 162 T R Rabi, M., 163

Tamaki, S., 159, 162 Thatcher, J. W., 162

Rabin, Michael O., 123, 163

Toda, S., 162

Rackoff, C., 123, 162

Torán, J., 159, 162

Raghavan P., 161

Turing, Alan, 127, 159

Rao, R., 163 Rivest, Ronald Lewis, 123, 161, 163

Turing, Alan (19121955), 163

Rónyai Lajos, 163 Rothe, Jörg, 124, 160163

V Vajda István, 161 Valiant, L. G., 160

S Saks, M., 162 Salomaa, Arto, 124, 163

W

Saxena, Nitin, 123, 161 Schöning, Uwe, 142, 146, 159163

Wagner, Klaus W., 163 Watanabe O., 163

Selman, Alan L., 159, 162, 163

Wechsung, Gerd, 160, 162, 163

Shamir, Adi, 123, 163

Wegman, M. N., 160, 161

Shannon, Claud Elwood (19162001), 163

Wigderson, A., 123, 161

Sherman, A., 163 Singh, Simon, 101, 123, 163 Sipser, M., 123, 162

Z

Solovay, R., 123, 163

Zachos, S., 163

Spakowski, Holger, 160

Zane, F., 162

Tartalomjegyzék

3.

4.

Kriptográa (Jörg Rothe) . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

94

3.1.

95

Alapok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1.

Kriptográa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

96

3.1.2.

Kriptoanalízis . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

100

3.1.3.

Algebra, számelmélet és gráfelmélet . . . . . . . . . . . . . . . . .

101

3.2.

Kulcscsere Diffie és Hellman szerint . . . . . . . . . . . . . . . . . . . . .

107

3.3.

RSA és faktorizálás . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

110

3.3.1.

RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

110

3.3.2.

Digitális aláírás RSA segítségével . . . . . . . . . . . . . . . . . .

114

3.3.3.

Az RSA biztonsága és lehetséges támadások az RSA ellen . . . . .

114

3.4.

Rivest, Rabi és Sherman protokolljai . . . . . . . . . . . . . . . . . . . . .

116

3.5.

Interaktív bizonyítási rendszerek és zéró ismeret . . . . . . . . . . . . . . .

117

3.5.1.

Interaktív bizonyítási rendszerek, ArtúrMerlin-játékok és zéróismeretu protokollok . . . . . . . . . . . . . . . . . . . . . . . . .

117

3.5.2.

Zéró-ismeretu protokoll grázomorzmusra . . . . . . . . . . . . .

119

Bonyolultságelmélet (Jörg Rothe) . . . . . . . . . . . . . . . . . . . . . . . . .

125

4.1.

Alapok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

127

4.2.

NP-teljesség . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

134

4.3.

Az ítéletlogika kielégíthetoség-problémája . . . . . . . . . . . . . . . . . .

140

4.3.1.

. . . . . . . . . . . . . .

140

. . . . . . . . . . . . . .

142

Grázomorzmus és alsóság . . . . . . . . . . . . . . . . . . . . . . . . .

145

4.3.2. 4.4.

3-SAT determinisztikus idobonyolultsága 3-SAT valószínuségi idobonyolultsága . .

4.4.1.

Visszavezethetoségek és bonyolultsági hierarchiák

4.4.2.

A grázomorzmus alsó-hierarchiabeli

4.4.3.

A grázomorzmus SPP-beli

. . . . . . . . .

145

. . . . . . . . . . . . . . .

151

. . . . . . . . . . . . . . . . . . . .

153

Irodalomjegyzék . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

161

Tárgymutató . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

164

Névmutató

166

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3. Kriptográfia (Jörg Rothe)

Recommend Documents