Template:复杂度类：修订间差异

以互动方式浏览历史

←上一版本

删除的内容添加的内容

可视化wikitext

行内

2023年12月9日 (六) 11:14的最新版本

@@ 第3行： / 第3行： @@
 | image  = [[File:Important Complexity Classes within PSPACE.svg|100px|P、NP、反NP与PSPACE之间的关系]]
 | title  = 重要的[[複雜度類]]（[[複雜度類列表|完整列表]]）
+| listclass = hlist
 | group1 = 易解复杂度类
+| list1  =  {{Navbox|child
-| list1  = {{link-en|DLOGTIME|DLOGTIME}}{{·w}} {{link-en|AC0|AC0|AC<sup>0</sup>}}{{·w}} {{link-en|ACC0|ACC0|ACC<sup>0</sup>}}{{·w}} {{link-en|L (複雜度)|L (complexity)|L}}{{·w}} {{link-en|SL (複雜度)|SL (complexity)|SL}}{{·w}} {{link-en|RL (複雜度)|RL (complexity)|RL}}{{·w}} {{link-en|NL (複雜度)|NL (complexity)|NL}}{{·w}} {{link-en|NC (複雜度)|NC (complexity)|NC}}{{·w}} {{link-en|SC (複雜度)|SC (complexity)|SC}}{{·w}} [[P (複雜度)|P]]（[[P-完全]]）{{·w}} [[ZPP (複雜度)|ZPP]]{{·w}} [[RP (複雜度)|RP]]{{·w}} [[BPP (複雜度)|BPP]]{{·w}} {{link-en|BQP (複雜度)|BQP (complexity)|BQP}}
+  |liststyle = background:transparent;
+  | evenodd = swap
+  | listclass = hlist
+  | group1 = [[L (複雜度)|对数空间]]相关
+  | list1  = * [[DLOGTIME]]
+* {{link-en|AC0|AC0|AC<sup>0</sup>}}
+* {{link-en|ACC0|ACC0|ACC<sup>0</sup>}}
+* {{link-en|TC0|TC0|TC<sup>0</sup>}}
+* [[L (複雜度)|L{{·w}}FL{{·w}}SL{{·w}}NL]]
+* [[NC (复杂度)|NC]]
+* [[SC (複雜度)|SC]]
+* [[PolyL]]
+  | group2 = [[PSPACE#形式化定义|多项式空间]]相关
+  | list2  = * [[P (複雜度)|P]]（[[P-完全]]）
+* {{link-en|FP (复杂度)|FP (complexity)|FP}}
+* [[ZPP (複雜度)|ZPP]]
+* [[RP (複雜度)|RP]]
+* [[BPP (複雜度)|BPP]]
+* [[BQP (複雜度)|BQP]]（{{link-en|QMA (复杂度)|QMA|QMA}}
+* {{link-en|PostBQP (复杂度)|PostBQP|PostBQP}}
+* {{link-en|EQP (复杂度)|EQP|EQP}}）
+}}
 | group2 = 怀疑难解复杂度类
+| list2  = * [[UP (複雜度)|UP]]
-| list2  = [[UP (複雜度)|UP]]{{·w}} [[NP (複雜度)|NP]]（[[NP完全]]{{·w}} {{link-en|NP难|NP-hard}}{{·w}} [[反NP]]{{·w}} {{link-en|反NP完全|co-NP-complete}}）{{·w}} {{link-en|AM (複雜度)|Arthur–Merlin protocol|AM}}{{·w}} {{link-en|PH (複雜度)|PH (complexity)|PH}}{{·w}} {{link-en|PP (複雜度)|PP_(complexity)|PP}}{{·w}} [[井号P|#P]]（{{link-en|井号P-完全|Sharp-P-complete|#P-完全}}）{{·w}} [[IP (複雜度)|IP]]{{·w}} [[PSPACE]]（{{link-en|PSPACE完全|PSPACE-complete}}）
+* [[NP (複雜度)|NP]]（[[NP完全]]
+* [[NP困难]]
+* [[反NP]]
+* {{link-en|反NP完全|co-NP-complete}}）
+* {{link-en|FNP (复杂度)|FNP (complexity)|FNP}}（{{link-en|TFNP (复杂度)|TFNP (complexity)|TFNP}}）
+* [[PH (複雜度)|PH]]
+* [[PP (複雜度)|PP]]
+* [[＃P|#P]]（{{link-en|＃P-完全|Sharp-P-complete|#P-完全}}）
+* [[PSPACE]]（{{link-en|PSPACE完全|PSPACE-complete}}）
 | group3 = 难解复杂度类
+| list3  = * [[EXPTIME]]
-| list3  = {{link-en|EXPTIME|EXPTIME}}{{·w}} {{link-en|NEXPTIME|NEXPTIME}}{{·w}} {{link-en|EXPSPACE|EXPSPACE}}{{·w}} {{link-en|ELEMENTARY|ELEMENTARY}}{{·w}} {{link-en|PR (複雜度)|PR (complexity)|PR}}{{·w}} {{link-en|R (複雜度)|R (complexity)|R}}{{·w}} {{link-en|RE (複雜度)|RE (complexity)|RE}}{{·w}} {{link-en|ALL (複雜度)|ALL (complexity)|ALL}}
+* [[NEXPTIME]]
+* [[EXPSPACE]]
+* [[ELEMENTARY]]
+* [[PR (複雜度)|PR]]
+* [[R (複雜度)|R]]
+* [[RE (複雜度)|RE]]
+* [[ALL (複雜度)|ALL]]
 | group4 = 复杂度类的谱系
+| list4  = * [[多項式譜系]]
-| list4  = {{link-en|多项式谱系|Polynomial hierarchy}}{{·w}} {{link-en|指数谱系|Exponential hierarchy}}{{·w}} {{link-en|Grzegorczyk谱系|Grzegorczyk hierarchy}}{{·w}} {{link-en|算术谱系|Arithmetic hierarchy}}
+* [[指數譜系]]
+* {{link-en|Grzegorczyk谱系|Grzegorczyk hierarchy}}
+* [[算数阶层|算术谱系]]
 | group5 = 相关复杂度族
+| list5  = * [[DTIME]]
-| list5  = {{link-en|DTIME|DTIME}}{{·w}} [[NTIME]]{{·w}} {{link-en|DSPACE|DSPACE}}{{·w}} {{link-en|NSPACE|NSPACE}}{{·w}} {{link-en|可能性核对证明|Probabilistically checkable proof}}{{·w}} [[交互式证明系统]]
+* [[NTIME]]
+* {{link-en|DSPACE|DSPACE}}
+* [[NSPACE]]
+* {{link-en|可能性核对证明|Probabilistically checkable proof}}
+* [[交互式证明系统]]
+* [[量子复杂性理论]]
 }}<noinclude>
-[[Category:科学导航模板|{{PAGENAME}}]]
+[[Category:复杂度类|*]]
+[[Category:计算机科学导航模板]]
-[[en:Template:ComplexityClasses]]
+[[Category:数学导航模板]]
-[[hr:Predložak:KlaseSlozenosti]]
-[[ru:Шаблон:Классы сложности]]
 </noinclude>