P =ль NP

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

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

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

(no subject)

Вот при аксиоматизации арифметики элементарных функций (т.е. полиномиальных функций над натуральными числами) часто пользуются трюком, позволяющим сэкономить на значках и аксоимах, а именно, не определяют бинарной операции "умножение", а вместо неё объходятся операцией n^* = сумма первых n чисел ряда (1, 2, 3, ..).
Умножение же определяется через эту операцию и сложение:
   ab = (a + b)^* - (a^* + b^*).
Это удобно, например, тем, что коммутативность умножения выводятся тогда прямиком из коммутативности сложения. Ещё эта фукнция примечательна своим отношением к функции спаривания Кантора
   pair(a, b) = (a + b)^* + b.

Интересно, для определения конечных полей нет популярных аксиоматизаций в таком духе?



Upd: А нет ли здесь глобального шаблона кодирования произвольных структур данных через использование соответствующих лексикографическому порядку на этих данных функций Харди?

(no subject)

Ой, внезапно обнаружил на ютубе, что Иващенко с Васильевым были на Грушинском фестивале 2013, очень клёвые записи. Аж вообще жалко, что меня там не было. :-)