Естественное доказательство
В теории сложности вычислений естественным доказательством является определенный вид доказательства, устанавливающий, что один класс сложности отличается от другого. Хотя эти доказательства в некотором смысле «естественны», можно показать (при условии широко распространенной гипотезы о существовании псевдослучайных функций ), что никакое такое доказательство не может быть использовано для решения проблемы P и NP .
Обзор [ править ]
Понятие естественных доказательств было введено Александром Разборовым и Стивеном Рудичем в их статье «Естественные доказательства», впервые представленной в 1994 году, а позднее опубликованной в 1997 году, за которую они получили премию Гёделя 2007 года . [1]
В частности, естественные доказательства доказывают нижние оценки сложности схемы булевых функций . Естественное доказательство прямо или косвенно показывает, что булева функция обладает определенным естественным комбинаторным свойством . В предположении, что псевдослучайные функции существуют с «экспоненциальной жесткостью», как указано в их основной теореме, Разборов и Рудич показывают, что эти доказательства не могут разделить определенные классы сложности. Примечательно, что, предполагая существование псевдослучайных функций, эти доказательства не могут разделить классы сложности P и NP. [2]
Например, в их статье говорится:
- [...] рассмотрим общепринятую стратегию доказательства P ≠ NP:
- Сформулируйте некоторое математическое понятие «несоответствия», «разброса» или «изменения» значений булевой функции или связанного с ней многогранника или другой структуры. [...]
- Покажите с помощью индуктивного аргумента, что схемы полиномиального размера могут вычислять только функции с «малой» невязкой. [...]
- Затем покажите, что SAT или какая-либо другая функция в NP имеет «высокое» несоответствие.
- Наша основная теорема в разделе 4 свидетельствует о том, что ни одна стратегия доказательства в этом направлении никогда не сможет добиться успеха.
Свойство булевых функций считается естественным , если оно содержит свойство, удовлетворяющее условиям конструктивности и широты, определенным Разборовым и Рудичем. Грубо говоря, условие конструктивности требует, чтобы свойство было разрешимо за (квази)полиномиальное время, когда 2 н размера Таблица истинности логической функции n с n входами задается в качестве входных данных асимптотически по мере увеличения n . Это то же самое, что время, однократно экспоненциальное по n . Свойства, которые легко понять, скорее всего, удовлетворяют этому условию. Условие масштабности требует, чтобы это свойство выполнялось для достаточно большой части множества всех булевых функций.
Свойство полезно для класса сложности C если каждая последовательность логических функций, обладающих этим свойством, бесконечно часто определяет язык вне C. , Естественное доказательство — это доказательство, которое устанавливает, что определенный язык находится вне C полезное против C. , и ссылается на естественное свойство ,
Разборов и Рудич приводят ряд примеров доказательств с нижней границей для классов C, меньших, чем P/poly , которые можно «натурализовать», то есть преобразовать в естественные доказательства. Важный пример касается доказательства того, что проблема четности не принадлежит классу AC. 0 . Они дают убедительные доказательства того, что методы, использованные в этих доказательствах, не могут быть расширены для получения более сильных нижних оценок. В частности, АС 0 -Естественные доказательства не могут быть полезны против AC 0 [м] .
Разборов и Рудич также воспроизводят Ави Вигдерсона безусловное доказательство о том, что естественные доказательства не могут доказать экспоненциальные нижние оценки для задачи дискретного логарифмирования .
В настоящее время существует сильное убеждение, что механизм этой статьи фактически блокирует доказательства с нижней границей для класса сложности TC. 0 пороговых схем постоянной глубины и полиномиального размера, который считается, но не доказано, меньшим, чем P/poly. [3] Это убеждение связано с тем, что в соответствии с широко распространенными гипотезами относительно сложности кривых факторизации в определенных группах эллиптических существуют экспоненциально трудные псевдослучайные функции, вычислимые в TC. 0 . [4] Однако некоторые исследователи полагают, что ограничения Разборова-Рудича на самом деле являются хорошим руководством к тому, что может включать в себя «сверхестественное» доказательство нижней границы, например, свойства, жесткие или полные для экспоненциального пространства. [5]
Примечания [ править ]
- ^ «Премия Гёделя ACM-SIGACT 2007» . Архивировано из оригинала 3 марта 2016 г. Проверено 11 августа 2014 г.
- ^ А. А. Разборов и С. Рудич (1997). «Естественные доказательства» . Журнал компьютерных и системных наук . 55 : 24–35. дои : 10.1006/jcss.1997.1494 . ( Черновик )
- ^ «Зоопарк сложности:Т — Зоопарк сложности» .
- ^ Наор, Мони; Рейнгольд, Омер (2004). «Теоретико-числовые конструкции эффективных псевдослучайных функций» . Журнал АКМ . 51 (2): 231–262. дои : 10.1145/972639.972643 . S2CID 8665271 .
- ^ К. Риган (октябрь 2002 г.). «Понимание подхода Малмули-Сохони к P и NP» (PDF) . Бюллетень Европейской ассоциации теоретической информатики . 78 : 86–97.
Ссылки [ править ]
- А.А. Разборов (2004). «Возможные доказательства и расчеты: партнерство и слияние». Материалы 31-й ICALP . Конспекты лекций по информатике. Том. 3142. стр. 8–14. ( Черновик )
- Лэнс Фортноу (10 мая 2006 г.). «Важность естественных доказательств» .
- Чоу, Тимоти Ю. (2011), «ЧТО ТАКОЕ… естественное доказательство?» (PDF) , Уведомления , 58 (11), AMS , получено 5 августа 2014 г.