Институт Клея и теорема P=NP

[Aritaborian]

Конечно, очевидно. Учёные тридцать первого века это доказали ;-)

[dmd]

Pavlovsky в сообщении #773398 писал(а):

Vieux в сообщении #773055 писал(а):

Или для института Клея очевидно, что $P\not=NP$?

Совершенно очевидно, что $P\not=NP$. И только безграмотные альты еще ничего не доказав уже беспокоятся, что у них что то украдут.

Если б было совершенно очевидно, то столько копий не ломалось бы вокруг проблемы. Лично для меня это всего лишь почти очевидно. Пока еще остаётся неочевидность невозможности полиномиально-быстрого решения какой-либо NP-сложной задачи. Видимо, вызывает опасения даже то, что статус факторизации неопределён - она NP-трудна или нет. Всё ещё остаётся возможность катастрофически неожиданной полиномиальной сводимости какой-либо NP-трудной задачи к какой-то задаче из P-класса. Т.е. такой сводимости, которую ранее никто не рассматривал и не предполагал в ней полиномиальность. Т.е. не только полиномиальность SAT и полиномиальное сведение к SAT надо опасаться, но и какой-то не-SAT задачи, очень похожей на SAT.

Например. Пусть полу-решение целочисленного квадратного уравнения - это ответ на вопрос есть решение или нет. Дано факторизуемое число битовой длины N. Я смогу за количество операций не более чем N^2 свести задачу факторизации к N полу-решениям некоторых целочисленных квадратных уравнений.
Вопросы.
1) полу-решение диофантова квадратного уравнения подобно SAT или нет?
2) если подобно, то оно сводится к SAT за полиномиальное время или нет?
3) если не подобно, то к какому классу сложности оно относится?

[Xaositect]

dmd в сообщении #773483 писал(а):

Например. Пусть полу-решение целочисленного квадратного уравнения - это ответ на вопрос есть решение или нет. Дано факторизуемое число битовой длины N. Я смогу за количество операций не более чем N^2 свести задачу факторизации к N полу-решениям некоторых целочисленных квадратных уравнений.

А как Вы это делаете? Квадратные диофантовы уравнения с одной переменной очевидно полиномиально разрешимы.

[dmd]

Извиняюсь, упустил из виду. Двух переменных конечно.

[Xaositect]

dmd в сообщении #773483 писал(а):

1) полу-решение диофантова квадратного уравнения подобно SAT или нет?
2) если подобно, то оно сводится к SAT за полиномиальное время или нет?

NP-полная: http://dx.doi.org/10.1145/800113.803627

[dmd]

(Xaositect)

Спасибо. Догадывался, что скорее всего NP-полная, но не смог сам найти источники.

[bin]

Vieux в сообщении #773055 писал(а):

1- не будет ли украдено доказательство?

Существуют простые, но надежные методы предотвратить такую возможность. Для этого нужно иметь подробный текст в виде статьи, лучше на английском. Далее с этим текстом делаете следующее:
1) Идете в ближайшее почтовое отделение и посылаете на свой адрес заказным письмом. Квитанцию сохраняете, а полученное письмо сохраняете в нераспечатанном виде. В случае судебного разбирательства передаете суду квитанцию и письмо.
2) Послать в известный архив препринтов (так сделал Перельман).
3) Найти нотариуса, который согласится взять на хранение (слышал про случай, когда так доказали авторство музыкального произведения).

Vieux в сообщении #773055 писал(а):

4-Вообще как Вы думаете, человеку который нашел такое доказательство стоит сразу опубликовать его или есть более разумный (не рискованный) способ заявить об этом?

Думаю, что если такое доказательство возможно, кто-то другой сможет найти похожее относительно быстро. Почему-то в истории постоянно происходят дублирующие открытия "независимо друг от друга" Поэтому ответ на вопрос:

Vieux в сообщении #773055 писал(а):

2- если все-таки доказательство выйдет на свет, не произойдет ли финансовый или даже политический кризис, так как всякие хакеры и крекеры получат реальные возможности взламывать банки, цифровые подписи, гос. тайны и т.п.

Если и произойдет, то Вам не дано его предотвратить. ИМХО могут случиться неудобства, но их быстро преодолеют: защита информации - это комплекс мер, в том числе и организационных, а не только сложные для взлома шифры. Гораздо хуже будет, если такое доказательство не сразу станет общеизвестным.

Vieux в сообщении #773055 писал(а):

3- мне кажется, что к некоторым задачам из списка задач тысячелетия требования по публикации должны быть немного другие.

С этим согласен. На сложных задачах система рецензирования дает сбой: рецензенты чаще всего пишут формальный отказ, отделываясь общими словами. А читатели и слушатели боятся поддержать (как бы не ошибиться! такое пятно на репутации будет!) Готов даже допустить, что проблема "P=?NP" уже решена, но статья ходит по редакциям, и об этом мало кто знает

[Vieux]

bin в сообщении #775592 писал(а):

Vieux в сообщении #773055 писал(а):

1- не будет ли украдено доказательство?

Существуют простые, но надежные методы предотвратить такую возможность. Для этого нужно иметь подробный текст в виде статьи, лучше на английском. Далее с этим текстом делаете следующее:
1) Идете в ближайшее почтовое отделение и посылаете на свой адрес заказным письмом. Квитанцию сохраняете, а полученное письмо сохраняете в нераспечатанном виде. В случае судебного разбирательства передаете суду квитанцию и письмо.
2) Послать в известный архив препринтов (так сделал Перельман).
3) Найти нотариуса, который согласится взять на хранение (слышал про случай, когда так доказали авторство музыкального произведения).

Не уверен в эффективности этих методов, так как:
- квитанцию можно печатать задним числом по договоренности с оператором;
- путь Перельмана второй раз уже не катится;
- Нотариус может быть не надежным.

bin в сообщении #775592 писал(а):

Vieux в сообщении #773055 писал(а):

4-Вообще как Вы думаете, человеку который нашел такое доказательство стоит сразу опубликовать его или есть более разумный (не рискованный) способ заявить об этом?

Думаю, что если такое доказательство возможно, кто-то другой сможет найти похожее относительно быстро. Почему-то в истории постоянно происходят дублирующие открытия "независимо друг от друга" Поэтому ответ на вопрос:

Какой ответ?

bin в сообщении #775592 писал(а):

Гораздо хуже будет, если такое доказательство не сразу станет общеизвестным.

Вы все-таки считаете нужно сразу публиковать?

[bin]

Vieux в сообщении #775752 писал(а):

- квитанцию можно печатать задним числом по договоренности с оператором;

И штамп на письме можно?

Vieux в сообщении #775752 писал(а):

Вы все-таки считаете нужно сразу публиковать?

Да, но при мыслях типа " Нотариус может быть не надежным" я не советую решать "проблемы тысячелетия". Это очень вредно для здоровья (слишком нервное занятие).
Успехов!

[Sender]

Xaositect в сообщении #773354 писал(а):

Есть даже явная последовательность задач из $\mathbf{P}$ с неограниченно увеличивающимися экспонентами

А там есть доказательство их принадлежности классу $\mathbf{P}$?

2 Vieux. Если надумаете публиковать доказательство, прошу вас кинуть ссылку сюда. Там как раз одного до ровного счёта не хватает.

[Xaositect]

Sender в сообщении #775777 писал(а):

А там есть доказательство их принадлежности классу $\mathbf{P}$?

Нет, но оно достаточно просто. Там рассматриваются игры с полиномиальным количеством позиций и ограниченным количеством ходов в каждой, можно за полиномиальное время построить граф игры и разметить позиции как выигрышные/проигрышные начиная с финальных.

[longstreet]

Vieux в сообщении #775752 писал(а):

путь Перельмана второй раз уже не катится

Это почему?

[korolev]

Лучше всего - выложить решение тут, а мы найдем ошибку

[bin]

korolev в сообщении #775875 писал(а):

Лучше всего - выложить решение тут, а мы найдем ошибку

А если не найдете, то не побоитесь здесь публично признать доказательство? Нпр., еще в начале лета 2013 я кардинально пересмотрел свой подход к related problem (GI is in P), с тех пор счетчик просмотров темы вырос более чем на 3000, но кроме незначительных замечаний (которые я учту в следующей версии) ничего так до сих пор и не услышал. Такая же ситуация и на других форумах по математике и computer sci. (в том числе и на международных). Прямые письма к ведущим специалистам по изоморфизму графов и теории вычислительной сложности тоже мало что дают. Типичный ответ:

Цитата:

Dear Michael,
Thanks for the update. I will take a look as time permits.
Best, <подпись>

Похоже, что если и появится верное и строгое решение подобный проблемы, то все эксперты попрячутся в кусты и будут сидеть там до скончания очередного тысячелетия. М.Клайн в кн. "Математика .Утрата определенности, М.: «Мир»,1984" отмечтил, что сегодня математики настолько боятся ошибиться и испортить свою репутацию, что решают только те проблемы, которые относительно легко решаются

[longstreet]

Большие проблемы обычно решают специалисты много лет работающие в теме.
Зачастую они все между собой знакомы, хотя бы заочно по работам.
Если кто-нибудь из них представит работу, её скорее всего внимательно изучат остальные.
В случае ошибки никакой беды не будет.

-- 16.10.2013, 17:58 --

Очевидный путь: раз уж кто такой крутой, что проблемы аля-тысячелетия решает, то пусть решит несколько и более простых существующих проблем/задач; напечатайте эти работы. А потом уж и решение аля-тысячелетней проблемы выдавайте. Внимание к ней будет.