Számítási bonyolultság

Tartalom

I. Algoritmusok 1
1. Problémák és algoritmusok 3
1.1. Elérhetőség gráfokban 3
1.2. Maximális folyam és párosítás 8
1.3. Az utazóügynök-probléma 13
1.4. Megjegyzések, hivatkozások és feladatok 15
2. Turing-gépek 21
2.1. A Turing-gépek alapjai 21
2.2. Turing-gépek mint algoritmusok 27
2.3. Többszavas Turing-gépek 30
2.4. Lineáris felgyorsítás 35
2.5. Tárkorlátok 38
2.6. Közvetlen hozzáférésű gépek 40
2.7. Nemdeterminisztikus gépek 50
2.8. Megjegyzések, hivatkozások és feladatok 57
3. Eldönthetetlenség 65
3.1. Univerzális Turing-gépek 65
3.2. A megállási probléma 66
3.3. További eldönthetetlen problémák 68
3.4. Megjegyzések, hivatkozások és feladatok 75
II. Logika 81
7 4. Ítéletkalkulus 83
4.1. Boole-formulák 83
4.2. Kielégíthetőség és érvényesség 87
4.3. Boole-függvények és -hálózatok 90
4.4. Megjegyzések, hivatkozások és feladatok 95
5. Elsőrendű logika 99
5.1. Az elsőrendű logika szintaxisa 99
5.2. Modellek . . 102
5.3. Tautológiák 108
5.4. Axiómák és bizonyítások 114
5.5. A teljességi tétel 111
5.6. A teljességi tétel következményei 125
5.7. Másodrendű logika 129
5.8. Megjegyzések, hivatkozások és feladatok 134
6. Eldönthetetlenség a logikában 141
6.1. A számelmélet axiómái 141
6.2. A bonyolultság mint számelméleti fogalom 145
6.3. Eldönthetetlenség és nemteljesség 150
6.4. Megjegyzések, hivatkozások és feladatok 155
III. P és NP 157
7. Bonyolultsági osztályok közötti összefüggések 159
7.1. Bonyolultsági osztályok 159
7.2. A hierarchia tétel 163
7.3. Az elérhetőségi módszer 167
7.4. Megjegyzések, hivatkozások és feladatok 176
8. Visszavezetések és teljesség 183
8.1. Visszavezetések . . . . 183
8.2. Teljesség 190
8.3. Logikai jellemzések 198
8.4. Megjegyzések, hivatkozások és feladatok 203
9. NP-teljes problémák 209
9.1. NP problémák 209
9.2. A kielégíthetőség változatai 211
9.3. Gráfelméleti problémák 217
9.4. Halmazok és számok 230
9.5. Megjegyzések, hivatkozások és feladatok 238
10. A coNP osztály és függvényproblémák 253
10.1. NP és coNP 253
10.2. Prímtesztelés 256
10.3. Függvényproblémák 262
10.4. Megjegyzések, hivatkozások és feladatok . . . 270
11. Randomizált számítás 277
11.1. Randomizált algoritmusok 277
11.2. Randomizált bonyolultsági osztályok 291
11.3. Véletlen források 298
11.4. Hálózati bonyolultság 306
11.5. Megjegyzések, hivatkozások és feladatok 312
12. Kriptográfia 321
12.1. Egyirányú függvények 321
12.2. Protokollok 331
12.3. Megjegyzések, hivatkozások és feladatok 338
13. Közelíthetőség 345
13.1. Közelítő algoritmusok 345
13.2. Közelítés és bonyolultság 355
13.3. Közelíthetetlenség 367
13.4. Megjegyzések, hivatkozások és feladatok 371
14. P vagy NP 379
14.1. Az NP térképe 379
14.2. Izomorfizmus és sűrűség 382
14.3. Orákulumok 389
14.4. Monoton hálózatok 394
14.5. Megjegyzések, hivatkozások és feladatok 402
IV. A P osztályon belül 409
15. Párhuzamos számítás 411
15.1. Párhuzamos algoritmusok 411
15.2. Párhuzamos számítási modellek 421
15.3. Az NC osztály 428
15.4. RNC-algoritmusok 434
15.5. Megjegyzések, hivatkozások és feladatok 439
16. Logaritmikus tár 451
16.1. Az L = NL kérdés 451
16.2. Alternálás 455
16.3. Irányítatlan elérhetőség 458
16.4. Megjegyzések, hivatkozások és feladatok 461
V. Az NP osztályon túl 467
17. A polinomiális hierarchia 469
17.1. Optimalizálási problémák 469
17.2. A polinomiális hierarchia . . 483
17.3. Megjegyzések, hivatkozások és feladatok 492
18. A számítás, ami számít 499
18.1. A permanens 499
18.2. A P osztály 508
18.3. Megjegyzések, hivatkozások és feladatok 512
19. Polinomiális tár 515
19.1. Alternálás és játékok 515
19.2. Játékok a természet ellen és interaktív protokollok 530
19.3. További PSPACE-teljes problémák 542
19.4. Megjegyzések, hivatkozások és feladatok 550
20. Egy pillantás a távolba 553
20.1. Exponenciális idő 553
20.2. Megjegyzések, hivatkozások és feladatok 562
Tárgymutató 575
Névmutató 585

Témakörök