polynomial hierarchy

這篇文章，主要是想介紹很基本的complexity class. 人們叫做 polynomial hierarchy。

PH class.

這是一個可以被視為 complete generalization of P and NP, co-NP 的主題也可以給大家一個 feeling , why people believe that Factoring 這個問題不是NP complete.

儘管大家並不能證明。果然，在complexity theory的世界裡面，很少東西是可以證明的。

首先 先給定義:
Go back to Main page Notes for Complexity theory

一些基本性質: 還解釋了 why people believe that Factoring 這個問題不是NP complete.

PH complete 問題:

good reference:
Aaronson - Quantum Computing Since Democritus chap 6