Войти
В теории вычислительной сложности естественное доказательство - это своего рода доказательство, устанавливающее что один класс сложности отличается от другого. Хотя эти доказательства в некотором смысле «естественны», можно показать (при условии широко распространенной гипотезы о существовании псевдослучайных функций ), что никакое такое доказательство не может быть использовано для решения P vs. NP проблема.
Понятие естественных доказательств было введено Александром Разборовым и Стивеном Рудичем в их статье «Естественные доказательства», впервые представленной в 1994 году., а затем опубликованы в 1997 году, за что они получили в 2007 году премию Гёделя.
В частности, естественные доказательства доказывают нижние оценки сложности схемы для булевых функций. Естественное доказательство показывает, прямо или косвенно, что логическая функция имеет определенное естественное комбинаторное свойство . В предположении, что псевдослучайные функции существуют с «экспоненциальной трудностью», как указано в их основной теореме, Разборов и Рудич показывают, что эти доказательства не могут разделить определенные классы сложности. Примечательно, что, предполагая существование псевдослучайных функций, эти доказательства не могут разделить классы сложности P и NP.
. Например, в их статье говорится:
Свойство булевых функций определяется как естественное, если оно содержит свойство, удовлетворяющее условиям конструктивности и масштабности, определенным Разборовым и Рудичем. Грубо говоря, условие конструктивности требует, чтобы свойство было разрешимым за (квази) полиномиальное время, когда 2-размерная таблица истинности логической функции с n входами задается в качестве входных данных, асимптотически при увеличении n. Это то же самое, что время, однозначно экспоненциальное по n. Этому условию скорее всего удовлетворяют свойства, которые легко понять. Условие большого размера требует, чтобы свойство выполнялось для достаточно большой части набора всех булевых функций.
Свойство полезно против класса сложности C, если каждая последовательность булевых функций, обладающих этим свойством, бесконечно часто определяет язык вне C. Естественное доказательство - это доказательство, устанавливающее, что определенный язык лежит вне C и относится к естественному свойству, которое полезно против C.
Разборов и Рудич приводят ряд примеров доказательств с нижней границей для классов C, меньших, чем P / poly, которые могут быть "натурализованы", т.е. преобразованные в естественные доказательства. Важным примером является доказательство того, что проблема четности не относится к классу AC. Они убедительно свидетельствуют о том, что методы, использованные в этих доказательствах, не могут быть расширены, чтобы показать более сильные нижние оценки. В частности, AC-естественные доказательства не могут быть полезны против AC [m].
Разборов и Рудич также воспроизводят безусловное доказательство Ави Вигдерсона, что естественные доказательства не могут доказать экспоненциальные нижние оценки для проблемы дискретного логарифма.
Существует твердое текущее мнение, что механизм, описанный в этой статье, фактически блокирует доказательства с нижней границей для класса сложности TC пороговых схем постоянной глубины и полиномиального размера, что считается, но не оказалось меньше, чем P / poly. Это убеждение связано с тем, что согласно широко распространенным предположениям относительно жесткости разложения на множители в некоторых группах эллиптических кривых, существуют экспоненциально сложные псевдослучайные функции, вычислимые в TC. Однако некоторые исследователи считают, что ограничения Разборова-Рудича на самом деле являются хорошим руководством для того, что может включать в себя «сверхъестественное» доказательство с нижней границей, например, свойства, жесткие или полные для экспоненциального пространства.
