Промышленное оборудование 
Прошедшей зиме посвящается. 
Энергетический кризис Т-клеток: как рак подавляет иммунитет и новые пути 
А у меня один язык и я со всеми им говорю 
«Всего лишь проститутка!» 
Старейший житель Австралии, вязание и пингвины - небольшое расследование 
Презик Стубб безгранично туп! 
Пользуйтесь каршерингом! 
ВЕСЕННИЙ СНЕГ. - О ПИСАТЕЛЯХ И КНИГАХ
27.04.2023 —
Из комментов где-то далеко отсюда
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 точке. Но для смешанных производных и правда не умеем. Доказательство, по-моему, красивое, так что прочитайте лучше его, изинити за саморекламу.
Сохранено
|
|
</> |
Оставить комментарий
Популярные посты:
Предыдущие записи блогера :
Архив записей в блогах:
Итак, еще один мой «герой» вскоре будет депортирован из России. Я не раз писал о лидере ликвидированного Верховным Судом РФ движения «Таджикские трудовые мигранты» Каромате Шарипове. О том самом Каримове, который гордо именует себя «отцом всех таджиков в России», и, занимаясь в ...
1. В начале июня на Германию вероломно без объявления войны напали вторые в этом году школьные каникулы в условиях царящего сейчас по всей планете режима коронакратии. И если первые каникулы на Пасху мы бездарно протоптали по маршруту от квартиры в магазин и обратно, вряд ли ...
Ну не чудаки ли? Славы им захотелось, блин. Прежней было мало. Впрочем, тонка и многогранна артистическая натура, постороннему не проникнуть. Да, так нафига было во всемирно известный Большой Театр брать американку? Скандалов с Яниным, Волочковой, Филиным показалось мало – так ...
Уж сколько раз мне казалось - ушла в прошлое "имперская идея", покрылась мхом и заржавела. Ан нет, третьего дни опять она всплыла в комментах, дескать, "национальной идеи" у России нетъ, это пичально, но и ладно, вообще-то идея национальная и не нужна, требуется Идея Имперская, ибо Р ...
По возвращении с Суоменлинны у нас оставалось еще немного времени до темноты, решили пройтись до памятника Сибелиусу, заодно посмотрев по дороге церковь в скале Темппелиаукио (даже не пытайтесь это выговорить:)). Напротив ТЦ Форум стоят три голых молотобойца. Чего молотят и куда они дели ...
