P=NP

plakhov — 27.04.2023 Сегодня три человека, не сговариваясь, прислали мне ссылку на очередную статью, автор которой утверждает, что нашел алгоритм решения NP-трудных задач. Свое мнение по поводу P=NP статей я высказывал 13 лет назад, сейчас я, может быть, высказывал бы его не в таких жестких терминах, но по сути ничего не поменялось.

В статье, на которую все прислали ссылку, происходит долгое чисто комбинаторное перекладывание данных с места на место. Автор сортирует переменные по частоте встречаемости в формуле, объясняет читателю, что такое trie и тп.

Ранее не открытый алгоритм такого типа, решающий NP-трудные задачи, совершенно невероятен. Для NP-hard задач все мыслимые чисто комбинаторные алгоритмы типа "заменим все кусочки такого вида на кусочки сякого вида, выберем такой-то subset переменных, введем такое подразбиение, перепишем формулу в таком виде" итп человечество, по-моему, давно уже перебрало. Ещё есть отягчающее доп.соображение: поскольку большинство NP-complete задач сводятся друг к другу простыми заменами, алгоритм такого рода для одной из них означает существование аналогичного для любой из них.

Я верю, что если всё-таки Р=NP, то соответствующий алгоритм будет следовать из каких-то очень глубоких эквивалентностей, типа "давайте для SAT-формулы построим некий двойственный объект, потом вычислим корни его характеристического многочлена численным образом в каком-то хитром поле, потом кратность вычисленных корней как-то еще хитро скомбинируем и получим 0 или 1 в зависимости от того, четное или нечетное число решений у исходной формулы". Что-нибудь в таком духе. А то, что SAT нельзя решить локальными преобразованиями формулы конечного размера, я почти уверен, доказуемо даже без сверхчеловеческого интеллекта, в отличие от общего P!=NP (если Разборов или Валиант или студенты Ааронсона вообще не доказали, я не следил)

В моей старой записи ещё есть доказательство того факта, что если мы можем эффективно вычислять n-тую смешанную производную многочлена от n переменных, то Р=NP. Это звучит очень интересно, ведь чтобы вычислить n-ную производную многочлена по одной переменной, достаточно узнать его значение всего в n+1 точке. Но для смешанных производных и правда не умеем. Доказательство, по-моему, красивое, так что прочитайте лучше его, изинити за саморекламу.

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

Популярные посты:

• Ранее
• Архив