組合問題的計算量問題和復雜性是在20世紀50年代和60年代首次被發現的。在這個時期,人們開始研究一些NP難問題,這些問題的解決方案需要指數級別的計算時間。組合問題是其中一類問題,這些問題的解決方案需要在所有可能的組合中搜索最優解,因此計算量非常大。
在20世紀60年代,計算機科學家Richard Bellman提出了動態規劃的概念,這種算法可以用于解決一些組合問題。但是,即使使用動態規劃,解決某些組合問題仍然需要指數級別的計算時間。
隨著計算機技術的不斷發展,人們開始研究如何優化組合問題的求解。一些啟發式算法被提出,如遺傳算法、模擬退火算法等,這些算法可以在合理的時間內找到近似最優解。此外,一些組合問題的特殊結構被發現,可以用于設計更高效的算法。
總的來說,組合問題的計算量問題和復雜性是在20世紀50年代和60年代首次被發現,隨著計算機技術的不斷發展,人們不斷提出新的算法和技術來解決這些問題。