?

Log in

No account? Create an account
P == NP && P != NP - Научная кунсткамера [entries|archive|friends|userinfo]
Научная кунсткамера

[ website | lj ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

P == NP && P != NP [Jul. 1st, 2008|09:25 pm]
Научная кунсткамера

science_freaks

[d43m0n]
Кажется, тут не пробегал.

На arXiv'е в разделе CS, Computational Complexity была найдена следующая статья:
http://arxiv.org/pdf/0806.2947
Автор обещает крайне интересный результат. Цитирую:
"A Paradox ⇒ SAT is (NOT) NP-complete & ZFC is Inconsistent"

В кратком содержании упомянуто, что автор привлёк теорию нечёткой логики и нашёл проблему \in P, которую нельзя выразить как проблему для SAT. (OMG!) Кроме того, автор покусился на ZFC и положительно решил гипотезу континуума.
Дата опубликования (19 июня) не даёт повода предположить, что речь идёт о первоапрельской шутке. Мужик настроен вполне всерьёз, если он не издевается.
В общем, нетривиальный случай. ИМХО фрик, однако, я воздержусь от безапелляционных суждений.

(Вкратце, для тех, кто не в теме: Персонаж пытается "снять" реально существующий и научно важный вопрос путём "доказательства" того, что вопрос не имеет смысла.)
LinkReply

Comments:
[User Picture]From: silentpom
2008-07-02 01:50 am (UTC)
в виду того что континуум-гипотеза в нашей аксиоматике Цермело-Френкеля неразрешима -- аффтар явный фрик
(Reply) (Thread)
[User Picture]From: 66george
2008-07-02 06:12 am (UTC)
Он доказывает, что ZF противоречива. Это возможно. Если это правда, скоро станет сенсацией. Мне сейчас лень разбираться, подожду, станет ли сенсацией
(Reply) (Parent) (Thread)
[User Picture]From: silentpom
2008-07-02 06:32 am (UTC)
ЭЭЭЭ а я думал что доказана непротиврочивость как ZF+континуум и ZF+!континуум :)
(Reply) (Parent) (Thread)
[User Picture]From: youzhick
2008-07-02 06:52 am (UTC)
Референсы в статейке впечатлили. Всяко видал, но чтобы список ссылок был длиннее самой статьи...
(Reply) (Thread)
From: akpc806a
2008-07-02 10:07 am (UTC)
Рассуждения, где вводится контрпример очень туманны. Из теоремы 1 формально никак не следует, что L \in P. Говорится, только что T(n) < \infty. Не слишком удивительно, что противоречивую задачу автор не смог свести к SAT. Дальше не читал...

Вы лучше скажите сколько в Архиве доказательств что P = NP и P \ne NP ;-))
(Reply) (Thread)
[User Picture]From: d43m0n
2008-07-02 11:10 am (UTC)
Я чуть ли не в первый раз в Архив заглядываю, но подозреваю, что таких доказательств там не так мало ;-)) Но с такими масштабными следствиями (цитирую оригинал: "However, the empirical non-existence of polynomial-time algorithms for the used to be NP-complete problems would still associate the property with intractability. Nevertheless, the existence or non-existence of such algorithms would not resolve the P vs. NP problem which - in its original formulation - does not exist!" - вряд ли %)
Он эту статью ещё и в JACM послал.

Кроме всего прочего, я не очень-то (вернее, вообще не) разбираюсь в нечёткой логике, поэтому не все рассуждения автора мне доступны, хотя странности в них заметны. :-/
(Reply) (Parent) (Thread)