Intractability (nonfiction): Difference between revisions
Jump to navigation
Jump to search
(Created page with "In mathematics, '''intractability''' refers to problems that can be solved in theory (e.g. given large but finite resources, especially time), but...") |
No edit summary |
||
| Line 1: | Line 1: | ||
In [[ | In [[Computational complexity theory (nonfiction)|computational complexity theory]], '''intractability''' refers to problems that can be solved in theory (e.g. given large but finite resources, especially time), but for which in practice any solution takes too many resources to be useful. Such problems are known as '''intractable''' problems. | ||
Conversely, problems that can be solved in practice are called '''tractable''' problem, literally "a problem that can be handled". | Conversely, problems that can be solved in practice are called '''tractable''' problem, literally "a problem that can be handled". | ||
| Line 17: | Line 17: | ||
== Nonfiction cross-reference == | == Nonfiction cross-reference == | ||
* [[Computational complexity theory (nonfiction)]] | |||
* [[Mathematics (nonfiction)]] | * [[Mathematics (nonfiction)]] | ||
| Line 25: | Line 26: | ||
[[Category:Nonfiction (nonfiction)]] | [[Category:Nonfiction (nonfiction)]] | ||
[[Category:Computation (nonfiction)]] | |||
[[Category:Complexity (nonfiction)]] | |||
[[Category:Mathematicians (nonfiction)]] | [[Category:Mathematicians (nonfiction)]] | ||
Latest revision as of 19:39, 8 December 2017
In computational complexity theory, intractability refers to problems that can be solved in theory (e.g. given large but finite resources, especially time), but for which in practice any solution takes too many resources to be useful. Such problems are known as intractable problems.
Conversely, problems that can be solved in practice are called tractable problem, literally "a problem that can be handled".
The term infeasible (literally "cannot be done") is sometimes used interchangeably with intractable, though this risks confusion with a feasible solution in mathematical optimization.
In the News
Fiction cross-reference
Nonfiction cross-reference
External links:
- Computational complexity theory : Intractibility @ Wikipedia