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
   |liststyle = background:transparent;
   | evenodd = swap
+  | listclass = hlist
-  | group1 = [[对数空间]]相关
+  | group1 = [[L (複雜度)|对数空间]]相关
-  | list1  = [[DLOGTIME]]{{·w}} {{link-en|AC0|AC0|AC<sup>0</sup>}}{{·w}} {{link-en|ACC0|ACC0|ACC<sup>0</sup>}}{{·w}} {{link-en|TC0|TC0|TC<sup>0</sup>}}{{·w}}[[L (複雜度)|L{{·w}}FL{{·w}}SL{{·w}}NL]]{{·w}} {{link-en|NC (复杂度)|NC (complexity)|NC}}{{·w}} [[SC (複雜度)|SC]]{{·w}} [[PolyL]]
-  | group2 = [[多项式空间]]相关
+  | list1  = * [[DLOGTIME]]
+* {{link-en|AC0|AC0|AC<sup>0</sup>}}
-  | list2  = [[P (複雜度)|P]]（[[P-完全]]）{{·w}} {{link-en|FP (复杂度)|FP (complexity)|FP}}{{·w}} [[ZPP (複雜度)|ZPP]]{{·w}} [[RP (複雜度)|RP]]{{·w}} [[BPP (複雜度)|BPP]]{{·w}} [[BQP (複雜度)|BQP]]
+* {{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}} [[NP困难]]{{·w}} [[反NP]]{{·w}} {{link-en|反NP完全|co-NP-complete}}）{{·w}} {{link-en|FNP (复杂度)|FNP (complexity)|FNP}}（{{link-en|TFNP (复杂度)|TFNP (complexity)|TFNP}}）{{·w}} [[PH (複雜度)|PH]]{{·w}} [[PP (複雜度)|PP]]{{·w}} [[井号P|#P]]（{{link-en|井号P-完全|Sharp-P-complete|#P-完全}}）{{·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]]{{·w}} [[NEXPTIME]]{{·w}} [[EXPSPACE]]{{·w}} [[ELEMENTARY]]{{·w}} [[PR (複雜度)|PR]]{{·w}} [[R (複雜度)|R]]{{·w}} [[RE (複雜度)|RE]]{{·w}} [[ALL (複雜度)|ALL]]
+| list3  = * [[EXPTIME]]
+* [[NEXPTIME]]
+* [[EXPSPACE]]
+* [[ELEMENTARY]]
+* [[PR (複雜度)|PR]]
+* [[R (複雜度)|R]]
+* [[RE (複雜度)|RE]]
+* [[ALL (複雜度)|ALL]]
 | group4 = 复杂度类的谱系
+| list4  = * [[多項式譜系]]
-| list4  = {{link-en|多项式谱系|Polynomial hierarchy}}{{·w}} [[指數譜系]]{{·w}} {{link-en|Grzegorczyk谱系|Grzegorczyk hierarchy}}{{·w}} [[算术谱系]]
+* [[指數譜系]]
+* {{link-en|Grzegorczyk谱系|Grzegorczyk hierarchy}}
+* [[算数阶层|算术谱系]]
 | group5 = 相关复杂度族
-| list5  = [[DTIME]]{{·w}} [[NTIME]]{{·w}} {{link-en|DSPACE|DSPACE}}{{·w}} [[NSPACE]]{{·w}} {{link-en|可能性核对证明|Probabilistically checkable proof}}{{·w}} [[交互式证明系统]]
+| list5  = * [[DTIME]]
+* [[NTIME]]
+* {{link-en|DSPACE|DSPACE}}
+* [[NSPACE]]
+* {{link-en|可能性核对证明|Probabilistically checkable proof}}
+* [[交互式证明系统]]
+* [[量子复杂性理论]]
 }}<noinclude>
 [[Category:复杂度类|*]]
-[[Category:计算机科学导航模板|{{PAGENAME}}]]
+[[Category:计算机科学导航模板]]
+[[Category:数学导航模板]]
 </noinclude>