Andoza:Complexity classes: Versiyalar orasidagi farq
{{Navbox | |||
| name = Complexity classes | |||
| title = [[Complexity class]]es | |||
| listclass = hlist | |||
| group1 = Considered feasible | |||
| list1 = | |||
}} | *[[DLOGTIME]] | ||
*[[AC0|AC<sup>0</sup>]] | |||
*[[ACC0|ACC<sup>0</sup>]] | |||
*[[Regular language|REG]] | |||
*[[TC (complexity)|TC]] | |||
**[[TC0|TC<sup>0</sup>]] | |||
*[[L (complexity)|L]] | |||
*[[SL (complexity)|SL]] | |||
*[[RL (complexity)|RL]] | |||
*[[FL (complexity)|FL]] | |||
*[[NL (complexity)|NL]] | |||
**[[NL-complete]] | |||
*[[NC (complexity)|NC]] | |||
*[[SC (complexity)|SC]] | |||
*[[CC (complexity)|CC]] | |||
*[[P (complexity)|P]] | |||
**[[P-complete]] | |||
*[[ZPP (complexity)|ZPP]] | |||
*[[RP (complexity)|RP]] | |||
*[[BPP (complexity)|BPP]] | |||
*[[BQP]] | |||
*[[APX]] | |||
*[[FP (complexity)|FP]] | |||
| group2 = Suspected infeasible | |||
| list2 = | |||
*[[UP (complexity)|UP]] | |||
*[[NP (complexity)|NP]] | |||
**[[NP-completeness|NP-complete]] | |||
**[[NP-hardness|NP-hard]] | |||
**[[co-NP]] | |||
**[[co-NP-complete]] | |||
*[[TFNP]] | |||
*[[FNP (complexity)|FNP]] | |||
*[[Arthur–Merlin protocol|AM]] | |||
*[[QMA]] | |||
*[[Polynomial hierarchy|PH]] | |||
*[[Parity P|⊕P]] | |||
*[[PP (complexity)|PP]] | |||
*[[♯P|#P]] | |||
**[[♯P-complete|#P-complete]] | |||
*[[IP (complexity)|IP]] | |||
*[[PSPACE]] | |||
**[[PSPACE-complete]] | |||
| group3 = Considered infeasible | |||
| list3 = | |||
*[[EXPTIME]] | |||
*[[NEXPTIME]] | |||
*[[EXPSPACE]] | |||
*[[2-EXPTIME]] | |||
*[[ELEMENTARY]] | |||
**[[NONELEMENTARY]] | |||
*[[PR (complexity)|PR]] | |||
*[[R (complexity)|R]] | |||
*[[RE (complexity)|RE]] | |||
*[[ALL (complexity)|ALL]] | |||
| group4 = Other complexity classes | |||
| list4 = | |||
*[[polyL]] | |||
*[[Quasi-polynomial_time#Complexity_class|QP]] | |||
| group5 = Class hierarchies | |||
| list5 = | |||
*[[Polynomial hierarchy]] | |||
*[[Exponential hierarchy]] | |||
*[[Grzegorczyk hierarchy]] | |||
*[[Arithmetical hierarchy]] | |||
*[[Boolean hierarchy]] | |||
| group6 = Families of classes | |||
| list6 = | |||
*[[DTIME]] | |||
*[[NTIME]] | |||
*[[DSPACE]] | |||
*[[NSPACE]] | |||
*[[Probabilistically checkable proof]] | |||
*[[Interactive proof system]] | |||
| below = [[List of complexity classes]] | |||
}}<noinclude> | |||
{{Documentation}} | |||
[[Category:Computer science navigational boxes]] | |||
</noinclude> | |||
$2, $3 dagi (joriy) koʻrinishi
| Tajriba oʻtkazish uchun qumloq va test sahifasidan foydalaning. Iltimos, turkumlarni hujjat sahifasiga va intervikilarni vikimaʼlumotlarga joylashtiring. Ushbu andoza ostsahifalari. |