Полиномиальная креативность

В сложности вычислений теории полиномиальная креативность — это теория, аналогичная теории творческих множеств в теории рекурсии и математической логике . $k$ - креативные множества — это семейство формальных языков класса сложности NP, дополнения к которым заведомо не имеют $O(n^{k})$ недетерминированные по времени алгоритмы распознавания. Обычно считается, что NP не равен co-NP (классу дополнений языков в NP), что более строго означает, что дополнения всех NP-полных языков не имеют недетерминированных алгоритмов распознавания с полиномиальным временем. ^{[ 1 ]} Однако для $k$ -креативных множеств можно доказать отсутствие (более ограниченного) алгоритма распознавания, тогда как доказательство того, что NP ≠ co-NP, остается неуловимым.

The $k$ Предполагается, что -креативные множества образуют контрпримеры к гипотезе Бермана–Хартманиса об изоморфизме NP-полных множеств. Проверка принадлежности входной строки какому-либо из этих языков является NP-полной, но полиномиальные временные изоморфизмы между всеми такими языками и другими NP-полными языками неизвестны. Полиномиальная креативность и $k$ -творческие множества были представлены в 1985 году Деборой Джозеф и Полом Янгом после более ранних попыток Ко и Мура определить полиномиальные аналоги творческих множеств . ^{[ 2 ]}^{[ 3 ]}

Определение

Интуитивно понятно, что набор является творческим, когда существует алгоритм с полиномиальным временем, который создает контрпример для любого кандидата на быстрый недетерминированный алгоритм распознавания для его дополнения.

Классы быстрых недетерминированных алгоритмов распознавания формализуются Джозефом и Янгом как множества $\mathrm {NP} ^{(k)}$ недетерминированных машины Тьюринга программ $p$ что для входов $x$ которые они принимают, имеют путь принятия с количеством шагов, не превышающим $|p|(|x|^{k}+1)$ . Это обозначение следует отличать от обозначения класса сложности NP. Класс сложности NP представляет собой набор формальных языков, а $\mathrm {NP} ^{(k)}$ вместо этого это набор программ, которые принимают некоторые из этих языков. Каждый язык в NP распознается программой одного из наборов $\mathrm {NP} ^{(k)}$ , с параметром $k$ то есть (с точностью до множителя $|p|$ в границе количества шагов) показатель степени полиномиального времени работы программы . ^{[ 2 ]}

Согласно теории Джозефа и Янга, язык $L$ в НП есть $k$ -творческий, если можно найти свидетеля, показывающего, что дополнение $L$ не распознается ни одной программой в $\mathrm {NP} ^{(k)}$ . Более формально, должна существовать полиномиально вычислимая функция $f$ который сопоставляет программы этого класса с входными данными, на которых они терпят неудачу. Когда дали недетерминированная программа $p$ в $\mathrm {NP} ^{(k)}$ , функция $f$ должен создать входную строку $x=f(p)$ который либо принадлежит $L$ и заставляет программу принять $x$ , или не принадлежит $L$ и заставляет программу отклонять $x$ . Функция $f$ называется продуктивной функцией для $L$ . Если эта продуктивная функция существует, данная программа не производит поведение на входе. $x$ чего можно было бы ожидать от программы признания дополнения $L$ . ^{[ 2 ]}

Существование

Джозеф и Янг конструируют творческие языки, переворачивая определения этих языков: вместо того, чтобы начинать с языка и пытаться найти для него продуктивную функцию, они начинают с функции и конструируют язык, для которого он является продуктивной функцией. Они определяют функцию полиномиального времени $f$ быть полиномиально честным , если время его работы не более чем полиномиальная функция длины вывода. Это запрещает, например, функции, которые требуют полиномиального времени, но производят выходные данные меньше полиномиальной длины. Как они показывают, каждая взаимно-однозначная полиномиально честная функция $f$ это продуктивная функция для $k$ -творческий язык $K_{f}^{k}$ . ^{[ 2 ]}

Данный $f$ , Джозеф и Янг определяют ${\textstyle K_{f}^{k}}$ быть набором ценностей $f(p)$ для недетерминированных программ $p$ которые имеют путь принятия для $f(p)$ используя максимум ${\textstyle |p|(|f(p)|^{k}+1)}$ шаги. Это количество шагов (на этом входе) будет соответствовать $p$ принадлежащий ${\textstyle \mathrm {NP} ^{(k)}}$ . Затем $K_{f}^{k}$ принадлежит NP: учитывая входные данные $f(p)$ можно недетерминированно угадать оба $p$ и его принимающий путь, а затем убедитесь, что входные данные равны $f(p)$ и что путь действителен для $p$ . ^{[ 2 ]}

Язык ${\textstyle K_{f}^{k}}$ является $k$ -творческий, с $f$ как свою продуктивную функцию, поскольку каждая программа $p$ в $\mathrm {NP} ^{(k)}$ отображается с помощью $f$ к значению $f(p)$ это либо принимается $p$ (и, следовательно, также принадлежит $K_{f}^{k}$ ) или отклонено $p$ (и, следовательно, также не принадлежит $K_{f}^{k}$ ). ^{[ 2 ]}

Полнота

Каждый $k$ -креативное множество с полиномиально честной продуктивной функцией является NP-полным. Для любого другого языка $X$ в NP, по определению NP, можно перевести любой ввод $x$ для $X$ в недетерминированную программу $p_{x}$ который игнорирует свои собственные данные и вместо этого ищет свидетеля $x$ , принимая входные данные, если он их находит, и отклоняя в противном случае. Длина $p_{x}$ является полиномиальным по размеру $x$ и аргумент заполнения можно использовать, чтобы сделать $p_{x}$ достаточно долго (но все же полиномиально) для своего времени работы, чтобы претендовать на членство в $\mathrm {NP} ^{(k)}$ . Позволять $f$ быть продуктивной функцией, используемой для определения данного $k$ -креативный набор $L$ , и пусть $g$ быть переводом с $x$ к $p_{x}$ . Тогда состав $g$ с $f$ отображает входы $X$ в контрпримеры для алгоритмов, проверяющих эти входные данные. Эта композиция отображает входные данные, принадлежащие $X$ на строки, принадлежащие $L$ и входные данные, которые не принадлежат $X$ на строки, которые не принадлежат $L$ . Таким образом, это за полиномиальное время сокращение «много-один» от $X$ к $L$ . С $L$ находится (по определению) в NP, и любой другой язык в NP имеет к нему редукцию, он должен быть NP-полным. ^{[ 2 ]}

Можно также доказать более убедительно, что существует обратимая экономная редукция к $k$ -творческий набор. ^{[ 2 ]}

Приложение к гипотезе Бермана – Хартманиса

Гипотеза Бермана-Хартманиса утверждает, что существует изоморфизм полиномиального времени между любыми двумя NP-полными множествами: функция, которая отображает экземпляры «да» одного такого набора взаимно один в экземпляры «да» другого, занимает полиномиальное время, и чья обратная функция также может быть вычислена за полиномиальное время. Он был сформулирован Леонардом К. Берманом и Юрисом Хартманисом в 1977 году на основе наблюдения, что все NP-полные множества, известные в то время, были изоморфны. Эквивалентная формулировка гипотезы состоит в том, что любое NP-полное множество дополняется . Это означает, что существует полиномиальное и обратимое за полиномиальное время взаимно однозначное преобразование. $h(x,y)$ из да-экземпляров $x$ к более крупным экземплярам «да», которые кодируют «нерелевантную» информацию $y$ . ^{[ 4 ]}

Однако неизвестно, как найти такое преобразование заполнения для $k$ -творческий язык, продуктивная функция которого не является полиномиально обратимой во времени. Следовательно, если односторонние перестановки , существуют $k$ -креативные языки, в которых эти перестановки являются их продуктивными функциями, предоставляют возможные контрпримеры гипотезе Бермана-Хартманиса . ^{[ 2 ]}

(Недоказанная) гипотеза Джозефа – Янга формализует это рассуждение. Гипотеза утверждает, что существует односторонняя возрастающая функция. $f$ такой, что $K_{f}^{k}$ не является прокладочным. ^{[ 2 ]} Алан Селман заметил, что это подразумевает более простую гипотезу, гипотезу о зашифрованном полном наборе : существует односторонняя функция $f$ такой, что $\mathrm {SAT}$ (набор да-экземпляров для проблемы выполнимости ) и $f(\mathrm {SAT} )$ неизоморфны . ^{[ 5 ]} Существует оракул, относительно которого существуют односторонние функции, обе эти гипотезы ложны, а гипотеза Бермана–Хартманиса верна . ^{[ 6 ]}

Ссылки

^ Гольдрейх, Одед (2010), P, NP и NP-полнота: основы вычислительной сложности , Cambridge University Press, стр. 154–155 , ISBN 9781139490092
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж Джозеф, Дебора ; Янг, Пол (1985), «Некоторые замечания о функциях-свидетелях для неполиномиальных и неполных множеств в NP» , Theoretical Computer Science , 39 (2–3): 225–237, doi : 10.1016/0304-3975(85)90140-9 , МР 0821203
^ Ко, Кер-I; Мур, Дэниел (1981), «Полнота, аппроксимация и плотность», SIAM Journal on Computing , 10 (4): 787–796, doi : 10.1137/0210061 , MR 0635436
^ Берман, Л.; Хартманис, Дж. (1977), «Об изоморфизмах и плотности NP и других полных наборов» (PDF) , SIAM Journal on Computing , 6 (2): 305–322, doi : 10.1137/0206023 , hdl : 1813/7101 , МР 0455536
^ Селман, Алан Л. (1992), «Обзор односторонних функций в теории сложности», Mathematical Systems Theory , 25 (3): 203–221, doi : 10.1007/BF01374525 , MR 1151339 , S2CID 33642595
^ Роджерс, Джон (1997), «Гипотеза об изоморфизме верна и относительно оракула существуют односторонние функции», Journal of Computer and System Sciences , 54 (3): 412–423, doi : 10.1006/jcss.1997.1486 , MR 1463764

[g-1] Гольдрейх, Одед (2010), P, NP и NP-полнота: основы вычислительной сложности , Cambridge University Press, стр. 154–155 , ISBN 9781139490092

[jy-2] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж Джозеф, Дебора ; Янг, Пол (1985), «Некоторые замечания о функциях-свидетелях для неполиномиальных и неполных множеств в NP» , Theoretical Computer Science , 39 (2–3): 225–237, doi : 10.1016/0304-3975(85)90140-9 , МР 0821203

[km-3] Ко, Кер-I; Мур, Дэниел (1981), «Полнота, аппроксимация и плотность», SIAM Journal on Computing , 10 (4): 787–796, doi : 10.1137/0210061 , MR 0635436

[bh-4] Берман, Л.; Хартманис, Дж. (1977), «Об изоморфизмах и плотности NP и других полных наборов» (PDF) , SIAM Journal on Computing , 6 (2): 305–322, doi : 10.1137/0206023 , hdl : 1813/7101 , МР 0455536

[s-5] Селман, Алан Л. (1992), «Обзор односторонних функций в теории сложности», Mathematical Systems Theory , 25 (3): 203–221, doi : 10.1007/BF01374525 , MR 1151339 , S2CID 33642595

[r-6] Роджерс, Джон (1997), «Гипотеза об изоморфизме верна и относительно оракула существуют односторонние функции», Journal of Computer and System Sciences , 54 (3): 412–423, doi : 10.1006/jcss.1997.1486 , MR 1463764

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]