мЮ ЦКЮБМСЧ ЯРПЮМХЖС млс

йКЮЯЯХВЕЯЙНЕ Х ЙБЮМРНБШЕ БШВХЯКЕМХЕ (БЕЯМЮ 1998)

ю.ьЕМЭ, ю.йХРЮЕБ

гЮОХЯЙХ КЕЙЖХИ (БШОНКМЕМШ л.м.бЪКШЛ)
(Lecture notes, by M.Vyalyi)

Gzipped postscript (may be viewed directly by some versions of Ghostview)

[кЕЙЖХЪ 2 (40 K)|кЕЙЖХЪ 3 (37K)|кЕЙЖХЪ 4 (39K)|
кЕЙЖХЪ 5 (43K)|кЕЙЖХЪ 6 (47K)|кЕЙЖХЪ 7 (32K)|
кЕЙЖХЪ 8 (54K)|кЕЙЖХЪ 9 (41K)|кЕЙЖХЪ 10 (45K)|
кЕЙЖХЪ 11 (38K)|кЕЙЖХЪ 12 (44K)|кЕЙЖХЪ 13 (43K)]

гЮОЮЙНБЮММШЕ zip-НЛ postscript-ТЮИКШ (Zipped Postscript)

[кЕЙЖХЪ 2 (40 K)|кЕЙЖХЪ 3 (37 K)|кЕЙЖХЪ 4 (39 K)|
кЕЙЖХЪ 5 (43 K)|кЕЙЖХЪ 6 (48 K)|кЕЙЖХЪ 7 (32 K)|
кЕЙЖХЪ 8 (54 K)|кЕЙЖХЪ 9 (41 K)|кЕЙЖХЪ 10 (45 K)|
кЕЙЖХЪ 11 (38 K)|кЕЙЖХЪ 12 (45 K)|кЕЙЖХЪ 13 (43 K)]

гЮДЮВХ ОН ЙКЮЯЯХВЕЯЙХЛ БШВХЯКЕМХЪЛ (Exercises on classical computations)

[Postscript-ТЮИК (36 K)|гЮОЮЙНБЮММШИ zip-НЛ postscript-ТЮИК (12 K)]

гЮДЮВХ ОН ЙБЮМРНБШЛ БШВХЯКЕМХЪЛ (Exercises on quantum computations)

[Postscript-ТЮИК (42 K)|гЮОЮЙНБЮММШИ zip-НЛ postscript-ТЮИК (17 K)]

оПНЦПЮЛЛЮ ЙСПЯЮ

вЮЯРЭ 1: нЯМНБМШЕ ОНМЪРХЪ РЕНПХХ ЯКНФМНЯРХ (ю.ьЕМЭ)

1. юКЦНПХРЛХВЕЯЙЮЪ ЯКНФМНЯРЭ Х ЙКЮЯЯ P. оПХЛЕПШ ЮКЦНПХРЛНБ Х РПСДМШУ ГЮДЮВ.
2. яУЕЛМЮЪ ЯКНФМНЯРЭ; НДМНПНДМШЕ ЯЕЛЕИЯРБЮ АСКЕБШУ ЯУЕЛ.
3. йКЮЯЯ NP. яБНДХЛНЯРЭ ОН йЮПОС. NP-ОНКМШЕ ГЮДЮВХ.
4. оНКХМНЛХЮКЭМЮЪ ХЕПЮПУХЪ Х ЙКЮЯЯ PSPACE. яБНДХЛНЯРЭ ОН рЭЧПХМЦС, НРМНЯХРЕКЭМЮЪ ЯКНФМНЯРЭ.
5. бЕПНЪРМНЯРМНЕ БШВХЯКЕМХЕ Х ЙКЮЯЯ BPP. оНКХМНЛХЮКЭМШИ БЕПНЪРМНЯРМШИ ЮКЦНПХРЛ ОПНБЕПЙХ ОПНЯРНРШ ВХЯКЮ.

вЮЯРЭ 2: йБЮМРНБНЕ БШВХЯКЕМХЕ (ю.йХРЮЕБ)

1. хДЕЪ ЙБЮМРНБНЦН БШВХЯКЕМХЪ. сМХРЮПМШЕ ОПЕНАПЮГНБЮМХЪ Х ЙБЮМРНБШЕ ЯУЕЛШ. йКЮЯЯХВЕЯЙНЕ НАПЮРХЛНЕ БШВХЯКЕМХЕ.
2. нЯМНБМШЕ ОНМЪРХЪ ЙБЮМРНБНИ ЛЕУЮМХЙХ. лЮРПХЖЮ ОКНРМНЯРХ. хГЛЕПЕМХЪ Х ХГЛЕПЪЧЫХЕ НОЕПЮРНПШ.
3. нОПЕДЕКЕМХЕ Х ОПНЯРЕИЬХЕ ЯБНИЯРБЮ ЙБЮМРНБНЦН БШВХЯКЕМХЪ. йКЮЯЯ BQP. мЕЙНРНПШЕ ХДЕХ, ЙЮЯЮЧЫХЕЯЪ ТХГХВЕЯЙНИ ПЕЮКХГЮЖХХ ЙБЮМРНБНЦН ЙНЛОЭЧРЕПЮ.
4. йБЮМРНБШИ ЮКЦНПХРЛ ДКЪ ГЮДЮВХ Н ОЕПХНДЕ. гЮДЮВЮ Н ЯРЮАХКХГЮРНПЕ, ДХЯЙПЕРМШИ КНЦЮПХТЛ.
5. йНДШ, ХЯОПЮБКЪЧЫХЕ НЬХАЙХ.
6. йБЮМРНБШЕ ЙНДШ.
7. бШВХЯКЕМХЕ, СЯРНИВХБНЕ Й НЬХАЙЮЛ (ЙКЮЯЯХВЕЯЙНЕ Х ЙБЮМРНБНЕ).