交替多項式時間複雜性類（alternating polynomial time complexity class）是2018年公布的計算機科學技術名詞。
交替多項式時間複雜性類（alternating polynomial time complexity class）是2018年公布的計算機科學技術名詞。定義在多項式時間內一切交替圖靈機所接受的語言做成的類，記為AP。已經...
互動式多項式時間複雜性類 互動式多項式時間複雜性類（class of interactive polynomial time，IP）是2018年公布的計算機科學技術名詞。公布時間 2018年經全國科學技術名詞審定委員會審定發布。出處 《計算機科學技術名詞 》 (第三版)
多項式時間（英語：Polynomial time）在計算複雜度理論中，指的是一個問題的計算時間{\displaystyle m(n)}不大於問題大小{\displaystyle n}的多項式倍數。任何抽象機器都擁有一複雜度類，此類包括可於此機器以多項式時間求解的問題。數學描述...
非定常多項式（英語：non-deterministic polynomial，縮寫：NP）時間複雜性類，或稱非確定性多項式時間複雜性類，包含了可以在多項式時間內，對一個判定性算法問題的實例，一個給定的解是否正確的算法問題。NP是計算複雜性理論中最重要的...
例如NP類就是一群可以被一非確定型圖靈機以多項式時間解決的決定型問題。而P類則是一群可以被確定型圖靈機以多項式時間解決的決定型問題。某些複雜度類是一群函式問題（Function problem）的集合，例如FP。許多複雜度類可被描述它的數學...
1.12 時間譜系定理 37 1.13 間隙定理 41 1.14 神諭圖靈機 42 1.15 歸約 43 1.16 空間複雜性類 45 1.17 對數空間類 49 1.18 多項式空間類 52 1.19 對數空間的補封閉性 55 1.20 TIME(T(n))=SPACE(T(n))...
複雜性類的完全語言 複雜性類的完全語言（complete language for complexity classes）是2018年發布的計算機科學技術名詞。定義 對某複雜性類在多項式時間多一歸約，或對數空間多一歸約下的完全語言。出處 《計算機科學技術名詞 》第三版。
也可以用量子算法（如量子計算機或量子圖靈機）定義量子複雜性，例如複雜度BQP就是可以用量子計算機在多項式時間內解決，其錯誤的機率小於一定比例的問題。量子複雜性中二個比較重要的複雜性類分別是BQP及QMA，分別對應複雜度P及NP (複雜度...
並行計算問題 並行計算問題（parallel computation problem）是2018年公布的計算機科學技術名詞。定義 多項式時間複雜性類是否等於NC類的問題，即是否P = NC的問題。出處 《計算機科學技術名詞 》第三版。
