Гипотеза Бермана – Хартманиса - Berman–Hartmanis conjecture

Вопрос, Web Fundamentals.svgНерешенная проблема в информатике:
Существует ли полиномиальный изоморфизм времени между каждыми двумя NP-полными языками?
(больше нерешенных проблем в информатике)

В теория структурной сложности, то Гипотеза Бермана – Хартманиса нерешенный догадка назван в честь Леонарда С. Бермана и Юрис Хартманис в котором говорится, что все НП-полный языки похожи друг на друга в том смысле, что они могут быть связаны друг с другом полиномиальное время изоморфизмы.[1][2][3][4]

Заявление

Изоморфизм между формальные языки L1 и L2 это биективный карта ж из струны в алфавите L1 к строкам в алфавите L2, со свойством, что строка Икс принадлежит L1 если и только если ж(Икс) принадлежит L2. Это изоморфизм полиномиального времени (или п-изоморфизм), если оба ж и это обратная функция могут быть вычислены за время, полиномиальное от длин их аргументов.

Берман и Хартманис (1977) заметил, что все языки, известные в то время как NP-полные, были п-изоморфный. Более того, они заметили, что все известные тогда NP-полные языки были гребной, и они доказали (аналогично Теорема об изоморфизме Майхилла ), что все пары дополняемых NP-полных языков являются п-изоморфный. Язык L можно дополнить, если есть полиномиальная функция времени ж(Икс,у) с полиномиальным обратным временем и тем свойством, что для всех Икс и у, Икс принадлежит L если и только если ж(Икс,у) принадлежит L: то есть можно подушечка вход Икс с неактуальной информацией у, обратимым образом, без изменения его принадлежности к языку. На основе этих результатов Берман и Хартманис предположили, что все NP-полные языки являются п-изоморфный.[5]

С п-изоморфизм сохраняет дополняемость, и существуют дополняемые NP-полные языки, эквивалентный способ сформулировать гипотезу Бермана – Хартманиса состоит в том, что все NP-полные языки являются дополняемыми. Полиномиальный изоморфизм времени является отношение эквивалентности, и его можно использовать для разделения формальных языков на классы эквивалентности, поэтому еще один способ сформулировать гипотезу Бермана – Хартманиса состоит в том, что NP-полные языки образуют один класс эквивалентности для этого отношения.

Подразумеваемое

Если гипотеза Бермана – Хартманиса верна, немедленным следствием этого было бы отсутствие редкий NP-полные языки, а именно языки, в которых количество да-экземпляров длины п растет только полиномиально как функция п. Известные NP-полные языки имеют ряд «да-экземпляров», которые растут экспоненциально, а если L это язык с экспоненциально большим числом "да", то он не может быть п-изоморфен разреженному языку, потому что его yes-экземпляры должны быть сопоставлены со строками, длина которых превышает полиномиальную длину, чтобы отображение было взаимно однозначным.

Отсутствие разреженных NP-полных языков, в свою очередь, означает, что P ≠ NP, потому что если P = NP, то каждый нетривиальный язык в P (включая некоторые разреженные, например язык двоичных строк, все биты которых равны нулю) будет NP-полным. В 1982 году Стив Махани опубликовал свое доказательство того, что несуществование разреженных NP-полных языков (с NP-полнотой, определенной стандартным способом с использованием много-одно сокращение ) фактически эквивалентно утверждению, что P ≠ NP; это Теорема Махани. Даже для упрощенного определения NP-полноты с помощью Редукции Тьюринга, существование разреженного NP-полного языка означало бы неожиданный крах полиномиальная иерархия.[6]

Свидетельство

В качестве доказательства гипотезы Agrawal et al. (1997) показал, что аналогичная гипотеза с ограниченным типом редукции верна: каждые два языка, полные для NP при AC0 много-одно сокращение имеет AC0 изоморфизм.[7]Агравал и Ватанабе (2009) показал, что если есть односторонние функции который не может быть инвертирован за полиномиальное время на всех входах, но если каждая такая функция имеет небольшое, но плотное подмножество входов, на котором она может быть инвертирована в П / поли (как и для известных функций этого типа), то каждые два NP-полных языка имеют P / поли-изоморфизм.[8]И Феннер, Фортноу и Курц (1992) нашел машина оракула модель, в которой верен аналог гипотезы об изоморфизме.[9]

Доказательства против этой гипотезы были предоставлены Джозеф и Янг (1985) и Курц, Махани и Ройер (1995). Джозеф и Янг ввели класс NP-полных задач: kтворческие наборы, для которых нет п-изоморфизм к стандартным NP-полным задачам.[10]Курц и др. показал, что в моделях машин оракула предоставляется доступ к случайный оракул, аналог гипотезы неверен: если А является случайным оракулом, то не все наборы полны для NPА имеют изоморфизмы в PА.[11]Случайные оракулы обычно используются в теории криптографии для моделирования криптографические хеш-функции которые в вычислительном отношении неотличимы от случайных чисел, а конструкция Курца и др. может выполняться с такой функцией вместо оракула. По этой причине, среди прочего, гипотеза об изоморфизме Бермана – Хартманиса считается ложной многими теоретиками сложности.[12]

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

  1. ^ Роте, Йорг (2005), "3.6.2 Гипотеза об изоморфизме Бермана – Хартманиса и односторонние функции", Теория сложности и криптология: введение в криптосложность, Birkhäuser, стр. 108–114, ISBN  978-3-540-22147-0.
  2. ^ Шёнинг, Уве; Пруим, Рэндалл Дж. (1998), "15. Гипотеза Бермана – Хартманиса и разреженные множества", Жемчужины теоретической информатики, Springer, стр. 123–129, ISBN  978-3-540-64425-5.
  3. ^ Курц, Стюарт; Махани, Стив; Ройер, Джим (1990), "Структура полных степеней", Ретроспектива сложности, Springer, стр. 108–146.
  4. ^ Агравал, Маниндра (2011), "Гипотеза об изоморфизме NP", в Купер, С. Барри; Сорби, Андреа (ред.), Вычислимость в контексте: вычисления и логика в реальном мире (PDF), World Scientific, стр. 19–48, ISBN  978-1-84816-245-7.
  5. ^ Берман, Л .; Хартманис, Дж. (1977), «Об изоморфизмах и плотности NP и других комплектов» (PDF), SIAM Журнал по вычислениям, 6 (2): 305–322, Дои:10.1137/0206023, HDL:1813/7101, МИСТЕР  0455536.
  6. ^ Махани, Стивен Р. (1982), "Разреженные полные наборы для NP: решение гипотезы Бермана и Хартманиса", Журнал компьютерных и системных наук, 25 (2): 130–143, Дои:10.1016/0022-0000(82)90002-2, HDL:1813/6257, МИСТЕР  0680515.
  7. ^ Агравал, Маниндра; Аллендер, Эрик; Импальяццо, Рассел; Питасси, Тониан; Рудич, Стивен (1997), «Снижение сложности редукций», Материалы 29-го симпозиума ACM по теории вычислений (STOC '97), стр. 730–738, Дои:10.1145/258533.258671, S2CID  14739803. Агравал, Маниндра; Аллендер, Эрик; Рудич, Стивен (1998), "Снижение сложности схемы: теорема об изоморфизме и теорема о разрыве", Журнал компьютерных и системных наук, 57 (2): 127–143, Дои:10.1006 / jcss.1998.1583.
  8. ^ Агравал, М.; Ватанабе, О. (2009), "Односторонние функции и гипотеза Бермана – Хартманиса", 24-я ежегодная конференция IEEE по вычислительной сложности (PDF), стр. 194–202, Дои:10.1109 / CCC.2009.17, S2CID  15244907.
  9. ^ Феннер, С .; Фортноу, Л.; Курц, С.А. (1992), "Гипотеза об изоморфизме верна относительно оракула", Материалы 33-го ежегодного симпозиума IEEE по основам информатики, стр. 30–39, CiteSeerX  10.1.1.42.6130, Дои:10.1109 / SFCS.1992.267821, S2CID  36512284.
  10. ^ Джозеф, Дебора; Янг, Пол (1985), «Некоторые замечания о функциях-свидетелях для неполиномиальных и неполных множеств в NP», Теоретическая информатика, 39 (2–3): 225–237, Дои:10.1016/0304-3975(85)90140-9, МИСТЕР  0821203.
  11. ^ Курц, Стюарт А .; Махани, Стивен Р .; Ройер, Джеймс С. (1995), «Гипотеза об изоморфизме неверна относительно случайного оракула», Журнал ACM, 42 (2): 401–420, Дои:10.1145/201019.201030, МИСТЕР  1409741, S2CID  52152959.
  12. ^ Фортноу, Лэнс (28 марта 2003 г.), Гипотеза об изоморфизме Бермана-Хартманиса.