Аннотация В данной работе представлено конструктивное доказательство различия классов P и NP, выполненное в рамках булевой схемной модели вычислений. В центре метода — функция из класса FNP, не обладающая полиномиально вычислимым обратным преобразованием, что позволяет строго отделить FNP от FP. Доказательство не опирается на вероятностные аргументы, криптографические предположения или эвристики. Оно основано на анализе свойств булевых схем, внутренней структуры функций и их схемной сложности...

Август 1900 года ознаменовался проведением в Париже II Международного конгресса математиков, на котором один из корифеев науки Давид Гильберт сформулировал наиболее кардинальные проблемы, требующие разрешения...