Полиномиальное творчество - Polynomial creativity

В теория сложности вычислений, полиномиальное творчество теория, аналогичная теории творческие наборы в теория рекурсии и математическая логика. В k-творческие наборы семья формальные языки в класс сложности НП, чьи комплектующие заведомо не имеют ${\displaystyle O(n^{k})}$недетерминированные алгоритмы распознавания по времени.

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

Определение

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

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

Полнота

Каждый ${\displaystyle k}$-творческий набор NP-полный. Ибо, применяя аргумент заполнения существует перевод за полиномиальное время ${\displaystyle g}$ экземпляров любого другого языка в NP в недетерминированные программы с полиномиальным временем в ${\displaystyle \mathrm {NP} ^{(k)}}$, так что да-экземпляры транслируются в программы, которые принимают все входные данные, а не-экземпляры переводятся в программы, которые отклоняют все входные данные. В сочинение этого перевода с функцией ${\displaystyle f}$ это полиномиальное время много-одно сокращение с данного языка на ${\displaystyle k}$-творческий набор. Также возможно более строго доказать, что существует обратимая экономное сокращение к ${\displaystyle k}$-творческий набор.^[1]

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

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

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

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

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

Гипотеза Бермана – Хартманиса утверждает, что существует изоморфизм за полиномиальное время между любыми двумя NP-полными наборами: функция, которая взаимно однозначно отображает да-экземпляры одного такого набора в да-экземпляры другого, занимает полиномиальное время, и обратная функция которого также может быть вычислена за полиномиальное время. Его сформулировали Леонард Берман и Юрис Хартманис в 1977 г. на основании наблюдения, что все известные в то время NP-полные множества были изоморфны. Эквивалентная формулировка гипотезы состоит в том, что каждый NP-полный набор является гребной. Это означает, что существует взаимно однозначное преобразование, обратимое за полиномиальное время и за полиномиальное время. ${\displaystyle h(x,y)}$ из да-инстансов ${\displaystyle x}$ к большим да-экземплярам, ​​которые кодируют "нерелевантную" информацию ${\displaystyle y}$.^[3]

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

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

Рекомендации

1. Джозеф, Дебора; Янг, Пол (1985), «Некоторые замечания о функциях-свидетелях для неполиномиальных и неполных множеств в NP», Теоретическая информатика, 39 (2–3): 225–237, Дои:10.1016/0304-3975(85)90140-9, МИСТЕР  0821203
2. Ко, Кер-И; Мур, Дэниел (1981), «Полнота, приближение и плотность», SIAM Журнал по вычислениям, 10 (4): 787–796, Дои:10.1137/0210061, МИСТЕР  0635436
3. Берман, Л .; Хартманис, Дж. (1977), «Об изоморфизмах и плотности NP и других комплектов» (PDF), SIAM Журнал по вычислениям, 6 (2): 305–322, Дои:10.1137/0206023, HDL:1813/7101, МИСТЕР  0455536
4. Селман, Алан Л. (1992), "Обзор односторонних функций в теории сложности", Математическая теория систем, 25 (3): 203–221, Дои:10.1007 / BF01374525, МИСТЕР  1151339, S2CID  33642595
5. Роджерс, Джон (1997), "Гипотеза об изоморфизме верна и существуют односторонние функции относительно оракула", Журнал компьютерных и системных наук, 54 (3): 412–423, Дои:10.1006 / jcss.1997.1486, МИСТЕР  1463764