Oracle turing machine and oracle complexity
這是我覺得一個很神奇的講題，主要是講，如果是世界上出現一種黑盒子，可以瞬間解決某一種問題，那這世界的計算機複雜度會如何?
這種物件叫做 oracle. 配上這種物件的 就叫做 oracle turing machine.:
首先是給定義:
研究最簡單的類型 P^NP 這個class.
了解 P^NP 這個 class 有多大，證明他落在polynomial hierarchy 第二層之內
No comments:
Post a Comment