Computational complexity (nonfiction): Difference between revisions
Jump to navigation
Jump to search
No edit summary |
|||
| (4 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
[[File:Complexity_subsets_pspace.svg|thumb|200px|A representation of the relation among complexity classes, which are subsets of each other | [[File:Complexity_subsets_pspace.svg|thumb|200px|A representation of the relation among complexity classes, which are subsets of each other.]]'''Computational complexity''' is a branch of theoretical computer science which attempts to explain why certain computational problems are intractable for computers. | ||
Analysis of [[Algorithm (nonfiction)|algorithms]] is a complementary branch which studies methods of solving computational problems efficiently. | Analysis of [[Algorithm (nonfiction)|algorithms]] is a complementary branch which studies methods of solving computational problems efficiently. | ||
| Line 5: | Line 5: | ||
== In the News == | == In the News == | ||
<gallery | <gallery> | ||
File:Hypercube.svg|link=The Boxes|[[The Boxes]], while not measurable, are assumed to have extremely high computations complexity. | File:Hypercube.svg|link=The Boxes|[[The Boxes]], while not measurable, are assumed to have extremely high computations complexity. | ||
</gallery> | </gallery> | ||
| Line 12: | Line 12: | ||
* [[Gnomon algorithm]] | * [[Gnomon algorithm]] | ||
* [[Gnomon Chronicles]] | |||
* [[Mathematics]] | * [[Mathematics]] | ||
| Line 20: | Line 21: | ||
* [[Computation (nonfiction)]] | * [[Computation (nonfiction)]] | ||
* [[Mathematics (nonfiction)]] | * [[Mathematics (nonfiction)]] | ||
* [[Polynomial hierarchy (nonfiction)]] - a [[Hierarchy (mathematics) (nonfiction)|hierarchy]] of [[Complexity class (nonfiction)|complexity classes]] that generalize the classes [[P (complexity) (nonfiction)|P]], [[NP (complexity) (nonfiction)|NP]] and [[co-NP (nonfiction)|co-NP]] to [[Oracle machine (nonfiction)|oracle machines]]. It is a resource-bounded counterpart to the [[Arithmetical hierarchy (nonfiction)|arithmetical hierarchy]] and [[Analytical hierarchy (nonfiction)|analytical hierarchy]] from [[Mathematical logic (nonfiction)|mathematical logic]]. | |||
External links: | External links: | ||
* [https://en.wikipedia.org/wiki/Computational_complexity Computational complexity ] @ Wikipedia | * [https://en.wikipedia.org/wiki/Computational_complexity Computational complexity ] @ Wikipedia | ||
[[Category:Nonfiction (nonfiction)]] | [[Category:Nonfiction (nonfiction)]] | ||
[[Category:Complexity (nonfiction)]] | [[Category:Complexity (nonfiction)]] | ||
[[Category:Computation (nonfiction)]] | |||
[[Category:Computer science (nonfiction)]] | |||
[[Category:Mathematics (nonfiction)]] | [[Category:Mathematics (nonfiction)]] | ||
[[Category:Computational complexity (nonfiction)]] | |||
Latest revision as of 13:09, 1 September 2018
Computational complexity is a branch of theoretical computer science which attempts to explain why certain computational problems are intractable for computers.
Analysis of algorithms is a complementary branch which studies methods of solving computational problems efficiently.
In the News
The Boxes, while not measurable, are assumed to have extremely high computations complexity.
Fiction cross-reference
Nonfiction cross-reference
- Algorithm (nonfiction)
- Complexity (nonfiction)
- Computation (nonfiction)
- Mathematics (nonfiction)
- Polynomial hierarchy (nonfiction) - a hierarchy of complexity classes that generalize the classes P, NP and co-NP to oracle machines. It is a resource-bounded counterpart to the arithmetical hierarchy and analytical hierarchy from mathematical logic.
External links:
- Computational complexity @ Wikipedia