翻转煎饼是一个NP Hard问题

     <p> 法国计算机科学家发现，<a href="/misc/goto?guid=4958198148089540756">排序煎饼很难</a>，实际上它是一个 NP Hard 问题，这不是玩笑，如果能在多项式时间内解决的话相当于证明了P=NP。<a href="/misc/goto?guid=4958198148827702874">论文</a>发表在预印本网站上。</p>    <p> 翻转煎饼是一个存在已久的算法问题。你有一堆大小不一的煎饼，你的任务是按次序排序，唯一的限制是你不能接触它们，只能借助金属铲插入某一分点，然后将上面的整体向上或向下翻过来。假设有N块煎饼，完成排序的翻转最大数F(n)是多少？本质上它是一个计算复杂性问题，法国的计算机科学家在论文中证明煎饼翻转是一个 NP Hard 问题。<br /> <br /> </p>    <div id="come_from">     来自:     <a id="link_source2" href="http://science.solidot.org/article.pl?sid=11/11/07/1129252&amp;from=rss" target="_blank">Solidot</a>    </div>    <span id="shareA4" class="fl"><a href="/misc/goto?guid=4958194775331586995" target="_blank"></a></span>    <p></p>