翻转煎饼是一个NP Hard问题
- Chapter09 - Solidot法国计算机科学家发现，排序煎饼很难，实际上它是一个NP Hard问题，这不是玩笑，如果能在多项式时间内解决的话相当于证明了P=NP. 翻转煎饼是一个存在已久的算法问题. 你有一堆大小不一的煎饼，你的任务是按次序排序，唯一的限制是你不能接触它们，只能借助金属铲插入某一分点，然后将上面的整体向上或向下翻过来.
翻转煎饼是一个NP Hard问题
标签：
math
| 发表时间：2011-11-07 19:28 | 作者：blackhat Chapter09
出处：http://solidot.org/
法国计算机科学家发现，排序煎饼很难，实际上它是一个NP Hard问题，这不是玩笑，如果能在多项式时间内解决的话相当于证明了P=NP。论文发表在预印本网站上。 翻转煎饼是一个存在已久的算法问题。你有一堆大小不一的煎饼，你的任务是按次序排序，唯一的限制是你不能接触它们，只能借助金属铲插入某一分点，然后将上面的整体向上或向下翻过来。假设有N块煎饼，完成排序的翻转最大数F(n)是多少？本质上它是一个计算复杂性问题，法国的计算机科学家在论文中证明煎饼翻转是一个NP Hard问题。
 |  |
相关 [煎饼 np hard] 推荐：
判断任意函数是否是凸函数是NP-hard问题
- Zhen - Solidot数学家和工程师都比较关心寻找特定函数的最小值，最小值通常代表着最优值. 例如，在控制论中，电机系统的最小值代表着稳定态. 对于复杂函数来说，寻找全局最小值是相当相当困难的. 但是，如果你提前知道一个函数是凸函数，那么问题就简单多了. 因为凸函数一般只有一个全局最小值，而凹函数通常有许多局部最小值. 那么有什么方法能判断一个函数是凸函数吗.
免费电子书：《Learn Vimscript the Hard Way》
- sunxphere - LinuxTOYVim 令人喜爱的地方之一是它支持通过插件来扩展自己，从而满足不同用户的需要. 如果你想为 Vim 编写插件，那么就必须学习 Vimscript 这个内建于 Vim 中的脚本语言. Steve Losh 的《Learn Vimscript the Hard Way》这本免费的电子书恰好可以让你对 Vimscript 上手.
煎饼快跑
- aki - 南方周末-热点新闻何洁与布诺没有再回去，尽管没有亲眼见过城管，但他们的气势，让法国学生们下意识地想到一个对应的英文单词，“RUN.
[nP]煎蛋：BP 损失的那么多钱能干啥？
- Tony - cnBeta.COMBP 这次真的损失大了(话说回来破坏环境要付出沉重代价)，VisualEconomics.com 就用图片把 BP 损失的千亿美元表现出来，看看这笔钱可以买到什么(via DMC)：.
新闻二则：P≠NP有望得证 魔方问题告破
- Michael - Matrix67: My Blog 昨天的消息：一位 HP 的研究员 Vinay Deolalikar 宣称自己证明了 NP 问题，得出了 P≠NP 的结论. P 是否等于 NP ，这是计算机科学领域中最困难的问题之一，也是意义最深远的问题之一，长期以来一直备受争议. 如果这个问题获得解决，将会在各个科学领域中引起轰动. Vinay Deolalikar 的整个证明有 100 多页，详细的论文可以在这里看到：.
网络图书：《Learn Ruby The Hard Way》繁体版本
- MessyCS - 道喜技术日记 .^. 天天红玉世界《Learn Ruby The Hard Way》繁体版本.
帖子：当年投胎选了hard模式，结果生在中国，还好没选very hard，不然生在朝鲜了… 的回复
- yiwu - 河蟹娱乐选择professional模式，更杯具. Hell模式 埃塞俄比亚，苏丹，刚果，扎伊尔. easy模式大概是在北欧那片吧～normol应该是美日欧. hell模式真情提示：请先完成very hard再尝试. 选择hard模式下次投胎有机会获得heaven模式. 从玩家数量来看，还是玩hard的多啊~.
P vs. NP，我们从过去的一周中学到了什么？
- Lamengao - apple4us这篇文章的标题是模仿 Suresh Venkatasubramanian 的一篇博客文章. 他是犹他大学的一名计算机系助理教授. 在过去的一周里，他在自己的博客上连续发表了好几篇文章，讨论 Vinay Deolalikar 在 8 月 6 号公布在网络上，后来又几经修改的那篇备受争议的宣称证明了 P ≠ NP 的论文.