Alexander Kuklev (akuklev) wrote,
Alexander Kuklev
akuklev

P =ль NP

Для меня интуитивной причиной считать, что NP не равно P являлось отрицательное решение десятой проблемы Гильберта, т.е. что для произвольного диофантова уравнения не разрешим вопрос наличия решений, причём для каждой (сколь угодно медленно работающей) программы можно сделать такое диофантово уравнение, что нахождение его корня, эквивалентно выполнению этой программы.

Базовой NP-полной задачей является задача SAT, т.е. по сути вопрос разрешимости диофантовых уравнений над конечным полем (урезанной версией натуральных чисел, так что можно перебрать все варианты). Интуитивно говоря, если бы существовали способы решать "конечно урезанные" версии диофантовых уравнений существенно эффективнее, чем перебором, это бы означало, что существует эффективный способ выяснить результат любой программы (будь она хоть супер-гипер-гипер-экспоненциально медленная) в пределах n < N за малое ограниченное число шагов, а это противоестественно.

Я догадываюсь, что это соображение по каким-то причинам невозможно формализовать.
Subscribe

  • Прогресс

    Десять дней назад, вторая ступень SpaceX'овского корабля Starship своим ходом слетала своим ходом на десять километров вверх, и усмепшно приземлилась…

  • О водосбережении

    Как известно, питьевая вода во многих странах дефицитный ресурс. И даже в дождливой Германии летом иногда случаются засухи, в результате которых она…

  • 36

    Традиционный деньрожденный пост. Год выдался необычный. :)

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 6 comments