Оглавление
Естественное доказательство
-
Определение и ограничения естественных доказательств
- Естественные доказательства – это вид доказательств, которые устанавливают различие между классами сложности.
- Разборов и Рудич показали, что естественные доказательства не могут использоваться для разделения классов сложности P и NP.
- Гипотеза о существовании псевдослучайных функций с “экспоненциальной жесткостью” ограничивает возможности естественных доказательств.
-
Примеры и ограничения естественных доказательств
- Примеры естественных доказательств включают доказательство того, что проблема четности не принадлежит классу AC0.
- Разборов и Рудич воспроизвели доказательство Ави Вигдерсона, которое показывает, что естественные доказательства не могут доказывать экспоненциальные нижние границы.
- Предполагается, что естественные доказательства могут быть использованы для доказательства нижних границ для класса сложности TC0, но это предположение основано на предположениях о сложности разложения на множители.
-
Структура статьи
- Статья состоит из введения, обзора, примеров и ограничений естественных доказательств, а также рекомендаций.
- В статье также присутствуют примечания и библиографическое описание.