本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：工作論文
- 編號：工作論文 #1349
- 日期：2026-03-18
摘要
我們解決了這樣一個問題：「無論使用何種演算法，某些類別的組合最佳化問題本質上是否比其他問題更難，或只能相對於特定演算法來評估難度？」我們為特定最佳化演算法提供特定最佳化問題的難度衡量。然後，我們提出兩個與演算法無關的量，它們使用此度量來為我們的問題提供答案。在第一個中，我們對當前最佳化問題的所有可能演算法的硬度進行平均。我們證明，根據這個量，優化問題之間沒有區別，從這個意義上說，沒有問題本質上比其他問題更難。對於第二個量，我們考慮的是對於該問題（或問題類別）而言最佳的演算法的問題（或問題類別）的難度水平，而不是對所有演算法進行平均。這裡有些問題本質上比其他問題更難。