Дж. Прескилл - Квантовая информация и квантовые вычисления. Тома 1-2, страница 54

ред.2Схемы должны быть апериодическими, н том смысле, •rm полностью .замккуrые цик:IЬIв них недопустимы.Г.IIADA 6284Часто оказывается, что вопрос, который не хотелось бы формулировать С.JIО­весно как вопрос, имеющий ответ ДА/НЕТ, может быть <<переформу.;шро­ваю> f<ЗК npofi>eмa припятня решения. Например, фувкция, определяющаяFACTOR!NG-пpoб;~eмy (задача факторюации):(х1 )1 'Узнаниесеf(x,{1' если целое х имеет делитель, меньший чем у'(6.21)О в противном случае;<у) ;~_;1я всех ух зк.вивалентно знанию наименьшего нетри­виалыюго множите.nя х.

Друтим важным примером проблемы припятнярешения служит НАМILТОN!АN-проблема (задача нахождения гамильто­нова обхода): рассмотрим !-вершинный граф, предстаменныйf х €-матри­цей смежности (равенство единице ее ij-э:~емента означает. что существуетребро, связывающее верпшныiиj);функциях ~ { 1, ec.m граф х имеет гамiLТhтонов обход,f( ) -О в пропшном с:rучае.(6.22)(Обход называется гамильтоновым, если он прохол.ит через каждую верши­ну графа ТО,JЬКО ОДИН раз.)Мы хотим оценивать трудность проблемы, количественпо определяянеобходимые ;щя се решения ресурсы.

Сложность проблемы принятия ре­шения разумно измерять размеро~ч мипима.1ьной схемы, вычисляющей со­ответствующую фувКIJиюf: {0, 1}»-->{0, 1}. Под размером мы понимаемкшшчество элементарных операций или компонентов, которые нужно обь­единить в cxe~ty, чwбы вычис.1итьf.Также можно интересоваться те~.какого вре.меии требует вычисление, если многие операции могут н.ыпон­няться параллельно. Глубина схемы нре)Jставляет собой необходимое коли­чество шагов при условии, что онерации, Jtейстпующие на раз.ТJичные биты,могут выпотrяться одновременно (то есть 1:...1убиной Я:В..i1ЯСТСЯ максима.1ьнаяд.·шна нрямого пути от входа схемы до ее выхода).

Ширина схемы--это\.fаксимальнuе количество операций, выrюлняемых на любом из ее этапов.Мы хотели бы разделить проблемы принятия решения на дваIOiacca:легкие и трудные. Но где следуст провести границу? Расс'\ютрим с ·пойцелью бесконечные семейства проблем припятня решения с персменнымразмером входа~ то есть ко.1ичес'tВО биrов на входе может быть любымцелымn.Тогда можно проверить, как соиз.\fерястся сnразмер схс\1ы, ре­шающей проблему.Однако в испою~зоваtши масruтабноru поведения семейства схем в ка­честве характеристики с.;южности задачи имеетсяo.wa.тонкость.

Бwю бы2856.1. КЛАССИtLRСКИЕ (ВЫЧИС1ИТЕЛЪНЫЕ) СХЕМЫобманом скрывать сдожность нроблемы в конструкции схемы. Следова­телL.но, мы дОJlЖНЫ ограничиться семействами, обладающими приемлемы­ми свойствами «однородности»сn-должно быть «просw» построить схему+ 1-битовы:м: входом, коль скоро схема с п-битовым входом уже постро­ена.Пусть с данным семейством функций {fn} (где fn имеет п-битовыйвход) сопоставлены вычнСJIЯющие их схемы {Cn}. Мы говорим, что {Сп}является семейством схем «подиномиального размера)), есJШ размер Cnрастет сnне быстрее некоторой степениn:(6.23)size(Cn),;; poly(n),г;~еpoly обозначает по:шном.Тогда определим:?={проблема принятия решения, решаемаясемействамисхем}полиномиального размера(Р означает разрешимость за «nолиномиальное время»).

Проблемы nрн­нятия решения, принадлежащие Р, яв"'!Яются <шросrЬIМИ», остальные<<сложнымю>. Заметим, что Сn вычисляетf n (х)-для любого оозможно­rо п-битового вхот(а и, следоJJатслыю, сели проблема принятия решенияпринадлежит Р, ro даже «в худшем случае)) мы можси найти ответ, исполь­зуя схему, размер которой не nревышает poly( n).

(Как отмечалось выше, мынеявно предполагаем, что семейство схем «о;щородпоп, так что проблемаразработки схемы сама может быть решена с помощью алrоритма, тре­бующего полиномиального времени. В этом предположении разрешимостьза полиномиа.Тiьное время с помощью семейства схем эквивалентна раз­решимости за nолиномиальное время с помощью универсальной машиныТьюриша.)Конечно, чтобы определить размер схемы, вычисляющейf n' мы долж­ны знать, что представ.;lЯют собой ее злементарные компоненты.

К сча­стью, принадлежиость проблемы к Р не зависит от выбора набора венти­лей, до тех пор пока они универсальны, их множество конечно, а каждыйвенти.IЬ действует на ограниченное множество битов. Один универса...'IЬныйнабор вентилей может ,uоделuроваться другим.Огромное большинство семейств функцийf:{0, l}n-->{0, 1}неnринадлежит Р. Для большей части функций выход существенно случа­ен, и нет лучшего способа «вычислить>>значений.

Но поскольку имеется2nf(x ),чем обратиться к таб;,пще ееп-битовых входов, то эта таблица имеетэкr:пинепциальпый размер, такой же размер должна иметь и схема, кодиру­ющая эту таблипу. Проблемы из Р nринадлежат очень частному юхассу-286гллвл6они имеют такую структуру, что функцияfможет быть эффектно но оычис­леl!а.Особый интерес представляют проблемы принятия решения, на кото­рые можно отоетить, приведя легко проверяемый при\lер.

ПуС1ъ, напри­мер, д,lЯ данных х н у<х трудно (в худше"' случае) опрспелиТJ,, имеетли х множите.'lь. меньше чем у. Нотакоеz <ecmt:кто-нибудь любезно предоставиту, на которое делится х, то нам просто проверить, чтоz.а:сй­сrвительно яшmется множителем х. Ана.;югично трудно опрсде~шть, имеетли граф 1·амильтонов обход, но ес!IИ кто-нибудь нам его нока3З.:I, то легкоубедиться н ·rом, что он и в самом ;щле гамильтовон.Эту щtею, что проблема может бьГJъ трудно разрешимой, по ее ре­шение, ко.'IЬ скоро оно найдено, легко про11еряе:мо, можно форма.низо­вать с помощью понятия «не;(етсрминиронанной» схемы.

Ассоцииронан­ная с С" (x(n)) кедстерминированная схема <'\,m (x<n), у< т)) обладает свой­ством1:СС:IИ(где x<n) представляетСп,тпr>.\'x(n)'y<"'))=l :Ддя пекоторога у\ т) (6.24)битоu, а y(m) - т битов). Таки"' обра:юм, сс­J1и у( т) оказа.rюсr:. удачно подобранным д.1я некотор010 x(n), ·ю мы мо­жем исtюш;юватr:- дn,m дпя прове,рки того, что Cl'l(x(н)) = 1.

Опреде­лимN Р={ 11роблемы припятня решения, лопускающ. и е семейство kеде-}терминировттых схем попиномиа.пъншо размера(N Розначает ра1рсшимосrь за <<Недетерминированное по:rиномиальноевремя>>). !:'.ели проблема нрнна;щежит N 1', то нет гарантии, что она нро­стая. Это о:шачает лишь то, что ее реnrсние легко нровсрить, есди мыраснолагаем nравильной информ8дией.

Очев11дно, что 1' <::; N Р. Подоб·но Р, N Р-проблсмы образуют малый подкласс всех проблем J[ринятия ре­шения.1Согласно одному из оnределений проблема прuнадпеЖJtт хлассу слож1юсти N Р, еслиcxe'll!a nuлиномиа..r.tьноrо по n. размера, проверяющая nредлuженнос решение :~аnолиномиальное RpeМJI. Проверяющаа схема [в дашюм случае зто д(х(п), y(m))] яаляетсясушествуетдетермшшрованной.

Термин недетерминированный происходит от того, что COI~'Iacнo друrо~му определению (см. следуюшее чуть ниже определение в основном тck~:rc)1\' Р-пробJJемадопусхаеr pt:lU~JLИe за полиномиапьuое время на таk щr~ываемой недетерминирtианный !~а­шине Тьюрннта, способпой в некоторых состояниях выбирать раз..Jw!ПЪiе варианты вычнсJJе­ни.и.. См. А. Кнтаев, А. Шеuъ, М. BJJ.;""IЬIЙ, Классичесkие и ЮlаJгrовьrе вы<~ис.'Iекия, М., МЦНМО,ЧеРо( 1999). -Прим. ред.6.1. КЛАССИЧЕСКИЕ (ВЫЧИСЛИТRЛЬН:ЫF:) СХЕМЫ287Многое в теории с.:южносm опирается на фундаментаныюе предположениеПредположение:РfN Р;(6.25)существуют сложные проблемы принятия решения, ретепия которых лег­ко проверяемы. К сожалению, эта важная rипотеза все еще ждет своегодоказательства.

Однако после 30-ти ;~ет попыток nоказать обратное- боль­шинство специалистов в теории слОЖJюсти твердо унерепы в ее справедли­вости1.Важным нримером NР-проблемы является CIRCUIТ-SAT 2 В этомслучае вход нредставпяет собой состоящая изnвентилей схема С с m-би­товым входом и Однобитовым выходом. Проблема состоит в том, чтобынайти, существует ли какой-нибудь m-битовый вход, для которого выходравен единице. Функция, которую необходимо вычиСJШ'IЪ, представляет со­бойf С)~(Это{ 1, если существует x(m) такое, что C(xCml) с- 1,О в противном с;,учае.N Г-проблема,(6.26)поскольку данную схему легко смоделироватh и вьrчис­лить ее выход для тобого частного входа.Я персхожу к формулировке некоторых важных результатов теориисложности, которые будут il)IЯ нас важliЫ. Здесь не будет времени ,'\Ш! дока­зательств.

Вы можете почерnнуть больше, обратившись к одному из многихучебникон но этому предмету. 3Многие идеи, nорожденныс теорией сложности. вытекают из теоремыКука(1971 ). Она утверждает, что любаяводима кCIRCUIT-SAT.N Г-проблемаЭто означает, что для nюбойполиномиально при­PROBLEMЕNPсуществует семейство схем полиномиа.;Jьного размера, которое отобража­ет «ситуацию>> xCnl для PROBLRM на <<сюуацию>> уСт) для CIRCUIТ-SAT,то еСlъCIRCUIТ-SЛT(yCml) = !, если PROBLEM(x(n)) = !.(6.27)Оrсюда следуе1~ что если бы в нашем распоряжении имелось мrо,иче­ское устройство, которое мото бы эффективно решатьCIRCUIT-SAT1Проб.1ема оо0111ошени"!.

к.'Iассов слоJЮюстн Р н N Р uстается нс.реruенной 11. в настоящее11ремя (нач<JЛо 2007r.). Более roru она входиг R сииоок вюкнейших .'laдaq математики XXI в.­При.м. ред.2CIRCUIT-SAT (circuit-satisfyaЬility) proЬiem- ЩЮ6JJема выполнимоств схемы. (нерев.)3Одной из лучших является книга M.R. Garey, D.S. Johnson, Computers and lntractabllity:А Guide to the Theory of N P-Competeness, русский персвод М. Г~ри, Д. Джонсон, Вычислитель­ные машины и труdн.орешае.мые заdачи, М.: Мир (1982). [Краткий, но достiПОчно полный, об­зор к.:1ассо1:1 сложности и их иерархии можно найпr в первой части kНИI'И: А.

Китаев, А. Шснь,М. Вя:лый, КлассичесюJ.е и квантовые вычисления, М.: МЦНМО, ЧсРо(1999).-Прим. ред.]288ГЛАВА 6(CIRCUIТ-SAT <<Оракул>>), то с помощью полиномиальной редукции мымогли бы связаться с ним, чтобы эффективно решить PROBLEM. Из тео­ремы Кука следует, что если вдруг О!Qlжется, что CIRCUIТ-SЛTтоР=ЕР,NP.Проблема, которая, подобно CIRCUIТ -SAT, обладает тем свойством,что к ней nолиномиально приводится любая проблема изется NР-поmюй(NPC).примеров NРС-проблем. Чтобы показать, чтоетсяN Р -полной,N Р,называ­После Кука было найдено множество друтихPROBLEMЕNPявля­достаточно найти: другую, полиномиально приводимуюк ней проблему~ о которой уже известно, что онаN Р-полная.Например,можно продемонстрировать пшшномиальную приводимость CIRCUIТ -SATк НAМILTONIAN.Toma из теоремы Кукаследует, что НAМILTONJ~"' то­же NР-полна.Если мы nредположим, что Рf NP,то отсюда следует, что всуществуют проблемы промежуточной трудности (классниN Р I).NPЭто ни Р,NPC.Друrой важный класс сложности называетсяN Р -проблемамиco-N Р.Эвристическиразрешимости являются те, на ко·юрые мы можем от­ветить, приведя пример, если ответом является ДА, в то врС!V!я как наco-N Р-проблемуможно ответить кoнmpnp'U..J\iepoм, сели ответом являетсяНЕ Т.