P=NP
![топ 100 блогов](/media/images/default.jpg)
В статье, на которую все прислали ссылку, происходит долгое чисто комбинаторное перекладывание данных с места на место. Автор сортирует переменные по частоте встречаемости в формуле, объясняет читателю, что такое trie и тп.
Ранее не открытый алгоритм такого типа, решающий NP-трудные задачи, совершенно невероятен. Для NP-hard задач все мыслимые чисто комбинаторные алгоритмы типа "заменим все кусочки такого вида на кусочки сякого вида, выберем такой-то subset переменных, введем такое подразбиение, перепишем формулу в таком виде" итп человечество, по-моему, давно уже перебрало. Ещё есть отягчающее доп.соображение: поскольку большинство NP-complete задач сводятся друг к другу простыми заменами, алгоритм такого рода для одной из них означает существование аналогичного для любой из них.
Я верю, что если всё-таки Р=NP, то соответствующий алгоритм будет следовать из каких-то очень глубоких эквивалентностей, типа "давайте для SAT-формулы построим некий двойственный объект, потом вычислим корни его характеристического многочлена численным образом в каком-то хитром поле, потом кратность вычисленных корней как-то еще хитро скомбинируем и получим 0 или 1 в зависимости от того, четное или нечетное число решений у исходной формулы". Что-нибудь в таком духе. А то, что SAT нельзя решить локальными преобразованиями формулы конечного размера, я почти уверен, доказуемо даже без сверхчеловеческого интеллекта, в отличие от общего P!=NP (если Разборов или Валиант или студенты Ааронсона вообще не доказали, я не следил)
В моей старой записи ещё есть доказательство того факта, что если мы можем эффективно вычислять n-тую смешанную производную многочлена от n переменных, то Р=NP. Это звучит очень интересно, ведь чтобы вычислить n-ную производную многочлена по одной переменной, достаточно узнать его значение всего в n+1 точке. Но для смешанных производных и правда не умеем. Доказательство, по-моему, красивое, так что прочитайте лучше его, изинити за саморекламу.
|
</> |