Имеет ли

15

Что произойдет, если мы определим P P A DP P A D таким образом, чтобы вместо схемы времени Тьюринга / машины полисайта схема Тьюринга пространства журналов или схема A C 0A C0 кодировали проблему?

В последнее время оказалось важным дать более быстрые алгоритмы для обеспечения удовлетворительности схемы для малых цепей , поэтому мне интересно, что происходит с версиями P P A D с ограниченным доступом .P P A D

domotorp
источник
Бусс и Джонсон, «Предложения и доказательства между задачами поиска NP», доказывают, что PPAD закрыт при сокращениях Тьюринга, и я уверен, что небольшая модификация аргумента дает эквивалентность PPAD с его (равномерной) версией AC ^ 0 ,
Эмиль Йержабек поддерживает Монику
@ Эмиль: Спасибо за предложение, к сожалению, понятия в этой статье находятся за пределами моего понимания. Я был бы признателен, если бы кто-то мог рассказать мне о его последствиях. Кроме того, позвольте мне дать ссылку на его препринт здесь: math.ucsd.edu/~sbuss/ResearchWeb/NPSearch/NPSearch.pdf
domotorp

Ответы:

10

Да, . (Здесь и далее я предполагаю, что определен как унифицированный класс. Конечно, с неоднородным мы бы просто получили .)A C 0 P A D = P P A D A C 0 A C 0 P P A D / p o l yA C0P A D = P P A DA C0A C0P P A D / p o l y

Основная идея довольно проста: может выполнить один шаг вычисления машины Тьюринга, поэтому мы можем смоделировать одно вычислимое ребро за полиномиальное время с помощью полиномиально длинной линии -вычислимых ребер. Дальнейшим расширением идеи можно было бы смоделировать ребра, вычисляемые за многократное время, с оракулом PPAD, то есть PPAD закрыт при сводимости по Тьюрингу; этот аргумент приводится у Бусса и Джонсона .A C 0 A C 0A C0A C0

Есть много эквивалентных определений PPAD в литературе, которые отличаются по разным деталям, поэтому позвольте мне привести здесь одно для определенности. Задача поиска NP находится в PPAD, если есть полином и функции полиномиального времени , и со следующими свойствами. Для каждого входа длины , и представляют ориентированный граф без самоконтролей, где , и каждый узел имеет степень и степень не более . Представление таково, что еслиS p ( n )Sp ( n )f ( x , u ) g ( x , u ) h ( x , u ) x n f g G x = ( V x , E x ) V x = { 0 , 1 } p ( n ) 1 ( u , v ) E x f ( x , u ) = vе( х , ты )g(x,u)h(x,u)xnfgGx=(Vx,Ex)Vx={0,1}p(n)1(u,v)Exтогда и ; если имеет внешнюю степень , ; и если имеет степень , .f(x,u)=vg ( x , v ) = u u 0 f ( x , u ) = u u 0 g ( x , u ) = ug(x,v)=uu0f(x,u)=uu0g(x,u)=u

Узел является источником (т. Имеет степень и степень ). Если - это любой источник или приемник (в степени , вне степени ), отличный от , то является решением .0 p ( n )V x 0 1 u V x 1 0 0 p ( n ) h ( x , u ) S ( x )0p(n)Vx01uVx100p(n)h(x,u)S( х )

Мы можем определить аналогичным образом, за исключением того, что нам требуется чтобы находились в .A C 0 P A D f,g,h F A C 0A C0P A Dе, г, чF A C0

Я буду игнорировать в конструкции для простоты. (Нетрудно показать, что можно считать это проекцией, следовательно, -вычислимой.)h A C 0часA C0

Итак, рассмотрим задачу PPAD, определенную и , и исправим машины Тьюринга, вычисляющие и за время . Для любого мы определим ориентированный граф , вершинами которого являются последовательности следующего вида:S f g f g q ( n ) x G x = ( V x , E x )SеграммеграммQ( н )Иксграмм'Икс= ( V'Икс, E'Икс)

  • ( 0 , u , c 1 , , c k ) u V x 0 k q ( n ) c 1 , , c k k f ( x , u )( 0 , у , с1, , СК) , где , , и - первые конфигураций в вычислении .u VИкс0kq(n)c1,,ckkf(x,u)

  • ( 0 , u , c 1 , , c q ( n ) , v , d 1 , , d k ) u , v V x 0 k q ( n ) f ( x , u ) = v c 1 , , C q ( n ) f ( x)(0,u,c1,,cq(n),v,d1,,dk) , где , , , - полное вычисление , а - первые шагов в вычислении .u,vVx0kq(n)f(x,u)=vc1,,cq(n), u ) d 1 , , d k k g ( x , v )f(x,u)d1,,dkkg(x,v)

  • ( 1 , v , d 1 , , d k ) 0 p ( n )v V x 0 k q ( n ) d 1 , , d k k g ( x , v )(1,v,d1,,dk) , где , , и - первые конфигураций в вычислении .0p(n)vVx0kq(n)d1,,dkkg(x,v)

  • ( 1 , v , d 1 , ... , д д ( п ) , у , с 1 , ... , C к ) у , v V х V 0 р ( п ) 0 K д ( п ) г ( х , v ) = u d 1 , , d(1,v,d1,,dq(n),u,c1,,ck) , где , , , , - это вычисление , а - первые шагов в вычислении .u,vVxv0p(n)0kq(n)g(x,v)=uq ( n ) g(x,v) c 1 ,, c k kf(x,u)d1,,dq(n)g(x,v)c1,,ckkf(x,u)

E x V x × V xEx состоит из ребер в следующих видов:Vx×Vx

  • ( 0 , u , c 1 , , c k ) ( 0 , u , c 1 , , c k + 1 )(0,u,c1,,ck)(0,u,c1,,ck+1)

  • ( 0 , u , c 1 , , c q ( n ) ) ( 0 , u , c 1 , , c q ( n ) , v )(0,u,c1,,cq(n))(0,u,c1,,cq(n),v)

  • ( 0 , u , c 1 , , c q ( n ) , v , d 1 , , d k ) ( 0 , u , c 1 , , c q ( n ) , v , d 1 , , д к + 1 )(0,u,c1,,cq(n),v,d1,,dk)(0,u,c1,,cq(n),v,d1,,dk+1)

  • ( 0 , u , c 1 , , c q ( n ) , v , d 1 , , d q ( n ) ) ( 1 , v , d 1 , , d q ( n ) , u , c 1 , , C q ( n ) ) f ((0,u,c1,,cq(n),v,d1,,dq(n))(1,v,d1,,dq(n),u,c1,,cq(n)) , если и (то есть, либо , или является изолированная вершина)u ) = v g ( v ) = u ( u , v ) E x u = vf(u)=vg(v)=u(u,v)Exu=v

  • ( 1 , v , d 1 , , d q ( n ) , u , c 1 , , c k + 1 ) ( 1 , v , d 1 , , d q ( n ) , u , c 1 , , С к )(1,v,d1,,dq(n),u,c1,,ck+1)(1,v,d1,,dq(n),u,c1,,ck)

  • ( 1 , v , d 1 , , d q ( n ) , u ) ( 1 , v , d 1 , , d q ( n ) )(1,v,d1,,dq(n),u)(1,v,d1,,dq(n))

  • ( 1 , v , d 1 , , d k + 1 ) ( 1 , v , d 1 , , d k )(1,v,d1,,dk+1)(1,v,d1,,dk)

  • ( 1 , и ) ( 0 , и )(1,u)(0,u)

Формально, пусть - многочлен, ограничивающий длины двоичных представлений всех последовательностей выше (таких, что мы можем расширять или сокращать последовательности и извлекать их элементы с помощью -функций); мы фактически ставим и оставляем все вершины, кроме вышеупомянутых последовательностей, изолированными.r ( n ) A C 0 V x = { 0 , 1 } r ( n )r(n)AC0Vx={0,1}r(n)

Легко видеть, что функции , представляющие являются -вычислимыми: в частности, мы можем проверить в ли допустимым частичным вычислением , мы можем вычислить из и извлечь значение из .f g G x A C 0 A C 0 c 1 , , c k f ( x , u ) c k + 1 c k f ( x , u ) c q ( n )fgGxAC0AC0c1,,ckf(x,u)

в являются узлами вида где является приемником в . Аналогично, источники - это где - источник в , за исключением того, что в специальном В случае мы рано обрезали строку, и соответствующий источник в равен просто . Можно предположить, что кодирование последовательностей выполнено таким образом, что .G x ( 0 , u , c 1 , , c q ( n ) , u , d 1 , , d q ( n ) ) u G x ( 1 , v , d 1 , , d q ( n ) , v , c 1 , , c q (n))vGxv=0p(n)Gx(0,0p(n))(0,0p(n))=0r(n)

Таким образом, и определяют задачу , и мы можем извлечь решение из решения с помощью -функции которая выводит второй компонент последовательности.fgAC0PADSS(x)S(x)AC0h

Эмиль Йержабек поддерживает Монику
источник