[Amicus Plato]

Как вам вот это, товарищи?

beta.novoteka.ru/?s=science#nnn15049216

Про P?=NP в сообществе написано много.
Но вот решить проблему мы не пробовали. А она, как оказалось, решилась. И всего на ста страницах.
Вот еще ссылка:
lenta.ru/articles/2010/08/12/np/

UPD: А вот и само доказательство:
www.hpl.hp.com/personal/Vinay_Deolalikar/Papers...

@темы: Алгоритмы, Интересные ссылки, Вопросы

Comments

[wer22]

подобных доказательств уже много было. Подождём пока выйдет подтверждение. Но количество страниц доказательства, как то настораживает.

[Amicus Plato]

wer22

много или мало?
По идее красивое доказательство имеет право быть лаконичным.

[wer22]

ИМХО многовато... Даже теорема о неполноте, как я помню, доказывается не более чем на 20 страницах, вместе с вспомогательными теоремами...
Очень похоже на попытку запутать экспертов.

[Amicus Plato]

Кто его знает...
100 страниц -- не тысяча. Подождем пока, что скажут в институте Клэя.

[Renaissance_Art]

что-то мне думается, что он доказал что-то иное...

[veneziahtb]

А почему так давно уже не было новых статей в этом замечательном....не знаю, блоге, что-ли?...