Естественное доказательство - Natural proof

В теории сложности вычислений , естественное доказательство является определенным видом доказательства , устанавливающим , что один класс сложности отличается от другого. Хотя эти доказательства в некотором смысле «естественны», можно показать (предполагая широко распространенную гипотезу о существовании псевдослучайных функций ), что никакое такое доказательство не может быть использовано для решения проблемы P vs. NP .

Обзор

Понятие естественных доказательств было введено Александром Разборовым и Стивеном Рудичем в их статье «Естественные доказательства», впервые представленной в 1994 году, а затем опубликованной в 1997 году, за которую они получили премию Гёделя в 2007 году .

В частности, природные доказательства доказать нижние оценки схемной сложности из булевых функций . Естественное доказательство прямо или косвенно показывает, что логическая функция обладает определенным естественным комбинаторным свойством . В предположении, что псевдослучайные функции существуют с «экспоненциальной трудностью», как указано в их основной теореме, Разборов и Рудич показывают, что эти доказательства не могут разделить определенные классы сложности. Примечательно, что в предположении существования псевдослучайных функций эти доказательства не могут разделить классы сложности P и NP .

Например, в их статье говорится:

[...] рассмотрим общепринятую стратегию доказательства для доказательства P ≠ NP:
  • Сформулируйте математическое понятие «несоответствия», «разброса» или «вариации» значений булевой функции, связанного многогранника или другой структуры. [...]
  • Покажите с помощью индуктивного аргумента, что схемы полиномиального размера могут вычислять только функции с "низким" расхождением. [...]
  • Затем покажите, что SAT или какая-либо другая функция в NP имеет "большое" расхождение.
Наша основная теорема в разделе 4 свидетельствует о том, что никакая стратегия доказательства в этом направлении не может быть успешной.

Свойство булевых функций определяется как естественное, если оно содержит свойство, удовлетворяющее условиям конструктивности и обширности, определенным Разборовым и Рудичем. Грубо говоря, условие конструктивности требует , чтобы свойство быть разрешимым в (квази) полиномиальное время , когда 2 п -sized правды таблица из п -input булевой функции задаются в качестве входных данных, асимптотический п возрастает. Это то же самое, что время, однозначно экспоненциальное по n . Этому условию, скорее всего, удовлетворяют свойства, которые легко понять. Условие большого размера требует, чтобы свойство выполнялось для достаточно большой части набора всех булевых функций.

Свойство является полезным против класса сложности C , если каждая последовательность булевых функций , обладающих свойством бесконечно часто определяет язык за пределы C . Естественное доказательство является доказательством того, что устанавливает , что определенный язык лежит за пределами C и относится к естественному свойству , что полезно против C .

Разборов и Рудич приводят ряд примеров доказательств с нижней границей для классов C, меньших, чем P / poly, которые могут быть «натурализованы», т. Е. Преобразованы в естественные доказательства. Важным примером является доказательство того, что проблема четности не принадлежит классу AC 0 . Они убедительно свидетельствуют о том, что методы, использованные в этих доказательствах, не могут быть расширены для получения более сильных нижних оценок. В частности, AC 0 -естественные доказательства не могут быть полезны против AC 0 [m] .

Разборов и Рудич также воспроизводят безусловное доказательство Ави Вигдерсона, что естественные доказательства не могут доказать экспоненциальные нижние оценки для проблемы дискретного логарифмирования .

В настоящее время существует твердое убеждение, что механизм этой статьи фактически блокирует доказательства с нижней границей против класса сложности TC 0 пороговых схем постоянной глубины и полиномиального размера, который считается, но не доказано, меньше, чем P / poly. Это убеждение связано с тем, что согласно широко распространенным предположениям о сложности факторизации в некоторых группах эллиптических кривых , существуют экспоненциально трудные псевдослучайные функции, вычислимые в TC 0 . Однако некоторые исследователи полагают, что ограничения Разборова-Рудича на самом деле являются хорошим руководством для того, что может включать в себя «сверхъестественное» доказательство с нижней границей, например, свойства жесткие или полные для экспоненциального пространства.

Заметки

  1. ^ "ACM-SIGACT 2007 Геделевская премия" . Архивировано из оригинала на 2016-03-03 . Проверено 11 августа 2014 .
  2. ↑ А. А. Разборов, С. Рудич (1997). «Естественные доказательства» . Журнал компьютерных и системных наук . 55 : 24–35. DOI : 10.1006 / jcss.1997.1494 .( Проект )
  3. ^ https://complexityzoo.net/Complexity_Zoo:T#tc0
  4. ^ http://dl.acm.org/citation.cfm?id=972643
  5. Перейти ↑ K. Regan (октябрь 2002 г.). «Понимание подхода Малмули-Сохони к P vs. NP» (PDF) . Бюллетень Европейской ассоциации теоретической информатики . 78 : 86–97.

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