考夫曼 N-k 模型的 NP 完整性，一個可調節的穩健適應度景觀

本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。

原文連結

• 原文連結
• PDF 來源

論文資訊

• 類型：工作論文
• 編號：工作論文 #1290
• 日期：2026-03-18

摘要

「適應度景觀」的概念是一個形象化的術語，表示有限圖的頂點到實數的映射，已經出現在包括進化論在內的多個領域。一個特別簡單的適應度景觀的兩個質量相似的版本的計算複雜度存在很大差異。在一個版本中，問題是「全域最優值是否大於給定值 ${\cal V}$？」透過提出實際計算最優值的有效演算法，證明該問題可以在多項式時間內完成。其他版本景觀的相應問題顯示為 ${\cal NP}$ 已完成。後一個問題的 ${\cal NP}$ 完整性導致了為什麼 ${\cal P} \neq {\cal NP}$ 的一些猜測。