URL: https://linuxfr.org/users/finss/journaux/p-np-demontre
Title: P=NP démontré ?
Authors: finss
Date: 2013年05月30日T19:45:09+02:00
License: CC By-SA
Tags: complexité, mathématiques, conjecture et démonstration
Score: 20
Xinwen Jiang a publié sur le site de la Cornell University un papier nommé «A Polynomial Time Algorithm for the Hamilton Circuit Problem» qui impliquerait que P=NP est vrai. 
«In this paper, we introduce a so-called Multistage graph Simple Path (MSP) problem and show that the Hamilton Circuit (HC) problem can be polynomially reducible to the MSP problem. To solve the MSP problem, we propose a polynomial algorithm and prove its NP-completeness. Our result implies NP=P.»
Pour mémoire le lien wikipedia sur sur ce problème dont la résolution impliquerait quelques changements dans à peu près tous les domaines scientifiques : http://fr.wikipedia.org/wiki/Probl%C3%A8me_P_%3D_NP 
Affaire à suivre, donc. Espérons qu'elle ait une autre fin que celle des neutrinos plus rapides que la lumière.
</div><div class="naked_ctrl">
<form action="/index.cgi/contrast" method="get" name="gate">
<p><a href="http://altstyle.alfasado.net">AltStyle</a> によって変換されたページ <a href="httpS://linuxfr.org/users/finss/journaux/p-np-demontre.md">(-&gt;オリジナル)</a>
/ <label>アドレス: <input type="text" name="naked_post_url" value="httpS://linuxfr.org/users/finss/journaux/p-np-demontre.md" size="22" /></label> <label>モード: <select name="naked_post_mode">
<option value="default">デフォルト</option>
<option value="speech">音声ブラウザ</option>
<option value="ruby">ルビ付き</option>
<option value="contrast" selected="selected">配色反転</option>
<option value="larger-text">文字拡大</option>
<option value="mobile">モバイル</option>
</select>
<input type="submit" value="表示" />
</p>
</form>
</div>