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

Естественное доказательство Определение и ограничения естественных доказательств Естественные доказательства — это вид доказательств, которые устанавливают различие между классами сложности.  Разборов […]

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

  • Определение и ограничения естественных доказательств

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

    • Примеры естественных доказательств включают доказательство того, что проблема четности не принадлежит классу AC0. 
    • Разборов и Рудич воспроизвели доказательство Ави Вигдерсона, которое показывает, что естественные доказательства не могут доказывать экспоненциальные нижние границы. 
    • Предполагается, что естественные доказательства могут быть использованы для доказательства нижних границ для класса сложности TC0, но это предположение основано на предположениях о сложности разложения на множители. 
  • Структура статьи

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

Полный текст статьи:

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

Оставьте комментарий

Прокрутить вверх