Для установки нажмите кнопочку Установить расширение. И это всё.

Исходный код расширения WIKI 2 регулярно проверяется специалистами Mozilla Foundation, Google и Apple. Вы также можете это сделать в любой момент.

4,5
Келли Слэйтон
Мои поздравления с отличным проектом... что за великолепная идея!
Александр Григорьевский
Я использую WIKI 2 каждый день
и почти забыл как выглядит оригинальная Википедия.
Что мы делаем. Каждая страница проходит через несколько сотен совершенствующих техник. Совершенно та же Википедия. Только лучше.
.
Лео
Ньютон
Яркие
Мягкие

Равенство классов P и NP

Из Википедии — свободной энциклопедии

Задачи тысячелетия

Вопрос о равенстве классов сложности P и NP (в русскоязычных источниках также известный как проблема перебора[1][2]) — это одна из центральных открытых проблем теории алгоритмов, сформулированная в начале 1970-х годов и до сих пор не имеющая доказательного ответа. Если будет дан утвердительный ответ, это будет означать, что существует теоретическая возможность решать многие сложные задачи существенно быстрее, чем сейчас.

Отношения между классами P и NP рассматриваются в разделе теории алгоритмов, который называется теорией вычислительной сложности. Она изучает ресурсы, необходимые для решения некоторой задачи. Наиболее общие ресурсы — это время (сколько нужно сделать шагов) и память (сколько памяти потребуется для решения задачи).

Проблема равенства классов P и NP является одной из семи задач тысячелетия, за решение которой Математический институт Клэя назначил премию в миллион долларов США.

Формулировка

Диаграмма классов сложности при условии PNP.

Нестрого говоря, проблема равенства P = NP состоит в следующем: если положительный ответ на какой-то вопрос можно довольно быстро проверить (за полиномиальное время), то правда ли, что ответ на этот вопрос можно довольно быстро найти (также за полиномиальное время и используя полиномиальную память)? Другими словами, действительно ли проверить решение задачи столь же ресурсозатратно, как и отыскать решение?[3]

Например, верно ли, что среди чисел {−2, −3, 15, 14, 7, −10, …} есть такие, что их сумма равна 0 (задача о суммах подмножеств)? Ответ — да, потому что −2 −3 + 15 −10 = 0 и если уже известен список слагаемых, то это легко проверяется несколькими последовательными сложениями (информация, необходимая для проверки положительного ответа, называется сертификатом). Следует ли отсюда, что так же легко определить сам этот список? Проверить сертификат так же легко, как найти его? Обычно считается, что подобрать числа сложнее. Но сопоставление теоретической сложности (количественной оценки объективно необходимых ресурсов) не доказано.

Из определения классов P и NP сразу вытекает следствие: . Однако до сих пор ничего не известно о строгости этого включения, то есть, существует ли задача, лежащая в NP, но не лежащая в P. Если такой задачи не существует, то все задачи, принадлежащие классу NP, можно будет решать за полиномиальное время, что сулит огромную выгоду в скорости вычислений. Сейчас самые сложные задачи из класса NP (так называемые NP-полные задачи) можно решить за экспоненциальное время, что считается неприемлемым с практической точки зрения.

История

Вероятно, впервые вопрос о вычислительной сложности был задан Куртом Гёделем в 1956 году в письме к Джону фон Нейману, где он спрашивал, может ли некая задача (которая, как сейчас известно, NP-полная) быть решена за квадратичное или линейное время. В то же время Гёдель предположил, что если решение существует, то это позволит решать с помощью компьютеров многие математические проблемы[4].

Впервые вопрос о равенстве классов был поставлен Стивеном Куком в 1971 году[5] и, независимо, Леонидом Левиным в 1973 году[6].

На начало 2000-х гг. большинство математиков считают, что эти классы не равны. Согласно опросу, проведённому в 2002 году среди 100 учёных,[7] 61 человек считает, что ответ — «не равны», 9 — «равны», 22 затруднились ответить и 8 дали другие ответы (в том числе, что гипотеза не выводима из текущей системы аксиом и, таким образом, не может быть доказана или опровергнута).

Как и другие известные нерешённые математические проблемы, попытки решения этой задачи привлекают значительные усилия; регулярно публикуются (не в научной литературе) ошибочные доказательства равенства или неравенства классов P и NP, обычно непрофессионалами[8].

Системы защиты, предполагающие неравенство классов P и NP

Любая криптосистема с открытым ключом базируется на предположении существования односторонних функций и/или крайней длительности решения некоторой задачи (например, для алгоритма RSA это разложение на множители очень больших чисел).

Для защиты компьютерных систем от злоупотребления услугами запрашивающей стороне предлагается решить задачу, на поиск решения которой тратится достаточно много времени, а результат легко и быстро проверяется обслуживающей стороной. Примером такой защиты от спама может служить система Hashcash[9], которая использует хеш частичной инверсии при отправке электронной почты.

В блокчейнах, основанных на технологии доказательства выполнения работы требуется, чтобы получаемая хеш-сумма была меньше целевого значения. Процесс поиска нужной хеш-суммы требует её многократного пересчёта с перебором произвольных значений дополнительного параметра (подробнее см. Майнинг). На поиск одной удовлетворительной хеш-суммы все компьютеры системы тратят значительное время (например, в «Биткойн» это в среднем 10 минут каждого из участников-майнеров). Для проверки корректности уже сформированного блока требуется лишь однократное вычисление хеша.

Похожие проблемы

  • В 1991 году было получено доказательство равенства классов MIP  (англ.) и NEXPTIME  (англ.).[11]
  • В 2020 году было получено доказательство равенства классов RE  (англ.) и MIP*[12][13].

См. также

Примечания

  1. А. А. Разборов. P ?= NP или проблема перебора: взгляд из 90-х. Архивировано 22 апреля 2007 года.
  2. А. Х. Шень. Проблема перебора // ПостНаука. Архивировано 9 июня 2015 года.
  3. Стюарт, 2015, с. 291.
  4. Hartmanis, Juris. Gödel, von Neumann, and the P = NP problem (англ.) // Bulletin of the European Association for Theoretical Computer Science. — Vol. 38. — P. 101—107. Архивировано 26 февраля 2015 года.
  5. Stephen Cook. The Importance of the P versus NP Question Архивная копия от 9 июля 2011 на Wayback Machine.
  6. Л. А. Левин. Универсальные задачи перебора // Проблемы передачи информации. — 1973. — Т. 9, № 3. — С. 115—116. Архивировано 10 октября 2017 года.
  7. William I. Gasarch. The P=?NP poll (англ.) // SIGACT News. — 2002. — Vol. 33, no. 2. — P. 34—47. — doi:10.1145/1052796.1052804. Архивировано 27 октября 2019 года.
  8. Lenta.ru — Мимо. Математики окончательно разуверились в решении задачи тысячелетия. Дата обращения: 26 августа 2010. Архивировано 30 августа 2010 года.
  9. Hashcash — A Denial of Service Counter-Measure Архивная копия от 23 ноября 2018 на Wayback Machine (2002)
  10. Разборов, 2016, с. 24.
  11. Babai, L.; Fortnow, L.; Lund, C. (1991). "Non-deterministic exponential time has two-prover interactive protocols". Computational Complexity. 1 (1): 3–40.
  12. MIP* = RE: эпохальное доказательство из сферы компьютерной науки, которое вызвало эффект домино в физике и математике / Блог компании RUVDS.com / Хабр. Дата обращения: 24 декабря 2020. Архивировано 12 мая 2021 года.
  13. Zhengfeng Ji; Anand Natarajan; Thomas Vidick; John Wright; Henry Yuen. "MIP*=RE". arXiv:2001.04383 [quant-ph].

Литература

Ссылки

Эта страница в последний раз была отредактирована 22 марта 2024 в 06:57.
Как только страница обновилась в Википедии она обновляется в Вики 2.
Обычно почти сразу, изредка в течении часа.
Основа этой страницы находится в Википедии. Текст доступен по лицензии CC BY-SA 3.0 Unported License. Нетекстовые медиаданные доступны под собственными лицензиями. Wikipedia® — зарегистрированный товарный знак организации Wikimedia Foundation, Inc. WIKI 2 является независимой компанией и не аффилирована с Фондом Викимедиа (Wikimedia Foundation).