Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Complexity class
open-in-new
<p>In <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a>, a complexity class is a <a href="/facts/Set_(mathematics)/BfucfHMq">set</a> of <a href="/facts/Computational_problem/jQ7bYUVh">computational problems</a> "of related resource-based <a href="/facts/Computational_complexity/Qenh22Ja">complexity</a>". The two most commonly analyzed resources are <a href="/facts/Time_complexity/77T62gmf">time</a> and <a href="/facts/Space_complexity/nsnAW5cV">memory</a>. </p><p>In general, a complexity class is defined in terms of a type of computational problem, a <a href="/facts/Model_of_computation/nJr8mHSI">model of computation</a>, and a bounded resource like <a href="/facts/Time_complexity/77T62gmf">time</a> or <a href="/facts/Space_complexity/nsnAW5cV">memory</a>. In particular, most complexity classes consist of <a href="/facts/Decision_problem/cQNWjbdE">decision problems</a> that are solvable with a <a href="/facts/Turing_machine/ojCtglYu">Turing machine</a>, and are differentiated by their time or space (memory) requirements. For instance, the class <a href="/facts/P_(complexity)/2TYvck4k">P</a> is the set of decision problems solvable by a deterministic Turing machine in <a href="/facts/Polynomial_time/77T62gmf">polynomial time</a>. There are, however, many complexity classes defined in terms of other types of problems (e.g. <a href="/facts/Counting_problem_(complexity)/pFj5xFYt">counting problems</a> and <a href="/facts/Function_problem/3zPWpraL">function problems</a>) and using other models of computation (e.g. <a href="/facts/Probabilistic_Turing_machine/Vq1JTHSR">probabilistic Turing machines</a>, <a href="/facts/Interactive_proof_system/rDB0agR9">interactive proof systems</a>, <a href="/facts/Boolean_circuit/TwhfJp0q">Boolean circuits</a>, and <a href="/facts/Quantum_computer/nbbcgmvq">quantum computers</a>). </p><p>The study of the relationships between complexity classes is a major area of research in <a href="/facts/Theoretical_computer_science/jSkGGuvy">theoretical computer science</a>. There are often general hierarchies of complexity classes; for example, it is known that a number of fundamental time and space complexity classes relate to each other in the following way: </p><p><a href="/facts/L_(complexity)/vCMV0edS">L</a>⊆<a href="/facts/NL_(complexity)/FvNaeSaM">NL</a>⊆<a href="/facts/P_(complexity)/2TYvck4k">P</a>⊆<a href="/facts/NP_(complexity)/6muUfVMI">NP</a>⊆<a href="/facts/PSPACE/RIkAClvG">PSPACE</a>⊆<a href="/facts/EXPTIME/GbTmY8t5">EXPTIME</a>⊆<a href="/facts/NEXPTIME/2pghWvBV">NEXPTIME</a>⊆<a href="/facts/EXPSPACE/Qkkhx0fr">EXPSPACE</a> </p><p>Where ⊆ denotes the <a href="/facts/Subset/SJGERmbA">subset</a> relation. However, many relationships are not yet known; for example, one of the most famous <a href="/facts/Open_problem/VuR6yLsW">open problems</a> in computer science concerns whether <a href="/facts/P_versus_NP/xoC7Ruda">P equals NP</a>. The relationships between classes often answer questions about the fundamental nature of computation. The P versus NP problem, for instance, is directly related to questions of whether <a href="/facts/Nondeterministic_algorithm/UubLdp3D">nondeterminism</a> adds any computational power to computers and whether problems having solutions that can be quickly checked for correctness can also be quickly solved. </p>