В теории сложности вычислений , естественное доказательство является определенным видом доказательства , устанавливающим , что один класс сложности отличается от другого. Хотя эти доказательства в некотором смысле «естественны», можно показать (предполагая широко распространенную гипотезу о существовании псевдослучайных функций ), что никакое такое доказательство не может быть использовано для решения проблемы P vs. NP .
Обзор
Понятие естественных доказательств было введено Александром Разборовым и Стивеном Рудичем в их статье «Естественные доказательства», впервые представленной в 1994 году, а затем опубликованной в 1997 году, за что они получили премию Гёделя в 2007 году . [1]
В частности, природные доказательства доказать нижние оценки схемной сложности из булевых функций . Естественное доказательство прямо или косвенно показывает, что логическая функция обладает определенным естественным комбинаторным свойством . В предположении, что псевдослучайные функции существуют с «экспоненциальной трудностью», как указано в их основной теореме, Разборов и Рудич показывают, что эти доказательства не могут разделить определенные классы сложности. Примечательно, что в предположении существования псевдослучайных функций эти доказательства не могут разделить классы сложности P и NP . [2]
Например, в их статье говорится:
- [...] рассмотрим общепринятую стратегию доказательства для доказательства 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. [3] Это убеждение связано с тем, что согласно широко распространенным гипотезам о сложности факторизации в некоторых группах эллиптических кривых , существуют экспоненциально трудные псевдослучайные функции, вычислимые в TC 0 . [4] Однако некоторые исследователи считают, что ограничения Разборова-Рудича на самом деле являются хорошим руководством для того, что может включать в себя «сверхъестественное» доказательство с нижней границей, например, свойства, жесткие или полные для экспоненциального пространства. [5]
Заметки
- ^ "ACM-SIGACT 2007 Геделевская премия" . Архивировано из оригинала на 2016-03-03 . Проверено 11 августа 2014 .
- ^ Разборов А.А., Рудич С.А. (1997). «Естественные доказательства». Журнал компьютерных и системных наук . 55 : 24–35. DOI : 10.1006 / jcss.1997.1494 .( Проект )
- ^ https://complexityzoo.net/Complexity_Zoo:T#tc0
- ^ http://dl.acm.org/citation.cfm?id=972643
- ^ К. Реган (октябрь 2002 г.). «Понимание подхода Малмули-Сохони к P vs. NP» (PDF) . Бюллетень Европейской ассоциации теоретической информатики . 78 : 86–97.
Рекомендации
- Разборов А.А. (2004). «Возможные доказательства и вычисления: партнерство и слияние». Материалы 31-го ИКАЛП . Конспект лекций по информатике. 3142 . С. 8–14.( Проект )
- Лэнс Фортноу (10 мая 2006 г.). «Важность естественных доказательств» .
- Чоу, Тимоти Ю. (2011), "ЧТО ТАКОЕ ... естественное доказательство?" (PDF) , Уведомления , AMS, 58 (11) , дата обращения 05.08.2014 CS1 maint: обескураженный параметр ( ссылка )