翻轉煎餅是一個NP Hard問題
法國計算機科學家發現，排序煎餅很難，實際上它是一個 NP Hard 問題，這不是玩笑，如果能在多項式時間內解決的話相當于證明了P=NP。論文發表在預印本網站上。
翻轉煎餅是一個存在已久的算法問題。你有一堆大小不一的煎餅，你的任務是按次序排序，唯一的限制是你不能接觸它們，只能借助金屬鏟插入某一分點，然后將上面的整體向上或向下翻過來。假設有N塊煎餅，完成排序的翻轉最大數F(n)是多少？本質上它是一個計算復雜性問題，法國的計算機科學家在論文中證明煎餅翻轉是一個 NP Hard 問題。
來自:
Solidot
本文由用戶 fmms 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。
轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。
本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！