TreeviewCopyright © aleen42 all right reserved, powered by aleen42
Computability Back
探索一個問題的Computability主要從兩個方面討論
- In Theory
- 並不是所有的數學問題都是理論上可解決的.
- 如果某问题理論上不能解決, 我們稱之為Undecidable (不可判定的)
- In Practices
- 在實際項目中, 倘若一個算法它的時間複雜度達到指數級別, 我們則之為Incomputable (不可計算的). (量子計算機或許是一個特例, 如果能實現指數級計算)
- In Theory
問題的劃分
- NP: 有多項式級別的判定算法
- P: 有多項式級別的求解算法
- EXP: 有指數式級別的求解算法
- NP-Complete(NPC): 有多項式級別轉化成NP問題的算法(如果能有效地解決該類問題, 則所有NP都能有效解決)
- 3-Color Problem
- TSP
- Circuit-SAT
Reduction
- Reduction is a general technique for showing that one problem is harder (easier) than another.
- Reduction of NPC
As the plugin is integrated with a code management system like GitLab or GitHub, you may have to auth with your account before leaving comments around this article.
Notice: This plugin has used Cookie to store your token with an expiration.