Что произойдет, если мы определим P P A D
В последнее время оказалось важным дать более быстрые алгоритмы для обеспечения удовлетворительности схемы для малых цепей , поэтому мне интересно, что происходит с версиями P P A D с ограниченным доступом .
Что произойдет, если мы определим P P A D
В последнее время оказалось важным дать более быстрые алгоритмы для обеспечения удовлетворительности схемы для малых цепей , поэтому мне интересно, что происходит с версиями P P A D с ограниченным доступом .
Ответы:
Основная идея довольно проста: может выполнить один шаг вычисления машины Тьюринга, поэтому мы можем смоделировать одно вычислимое ребро за полиномиальное время с помощью полиномиально длинной линии -вычислимых ребер. Дальнейшим расширением идеи можно было бы смоделировать ребра, вычисляемые за многократное время, с оракулом PPAD, то есть PPAD закрыт при сводимости по Тьюрингу; этот аргумент приводится у Бусса и Джонсона .A C 0 A C 0A C0 A C0
Есть много эквивалентных определений PPAD в литературе, которые отличаются по разным деталям, поэтому позвольте мне привести здесь одно для определенности. Задача поиска NP находится в PPAD, если есть полином и функции полиномиального времени , и со следующими свойствами. Для каждого входа длины , и представляют ориентированный граф без самоконтролей, где , и каждый узел имеет степень и степень не более . Представление таково, что еслиS p ( n )S p ( 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) x n f g Gx=(Vx,Ex) Vx={0,1}p(n) 1 (u,v)∈Ex тогда и ; если имеет внешнюю степень , ; и если имеет степень , .f(x,u)=v g ( x , v ) = u u 0 f ( x , u ) = u u 0 g ( x , u ) = ug(x,v)=u u 0 f(x,u)=u u 0 g(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)∈Vx 0 1 u∈Vx 1 0 0p(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Икс 0≤k≤q(n) c1,…,ck k f(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,v∈Vx 0≤k≤q(n) f(x,u)=v c1,…,cq(n) , u ) d 1 , … , d k k g ( x , v )f(x,u) d1,…,dk k g(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)≠v∈Vx 0≤k≤q(n) d1,…,dk k g(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,v∈Vx v≠0p(n) 0≤k≤q(n) g(x,v)=u q ( n ) g(x,v) c 1 ,…, c k kf(x,u)d1,…,dq(n) g(x,v) c1,…,ck k f(x,u)
E ′ x V ′ x × V ′ xE′x состоит из ребер в следующих видов:V′x×V′x
( 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)=v g(v)=u (u,v)∈Ex u=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) AC0 V′x={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 )f′ g′ G′x AC0 AC0 c1,…,ck f(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)G′x(0,0p(n))(0,0p(n))=0r(n)
Таким образом, и определяют задачу , и мы можем извлечь решение из решения с помощью -функции которая выводит второй компонент последовательности.f′g′AC0PADS′S(x)S′(x)AC0h′
источник