Intractability (nonfiction)
Jump to navigation
Jump to search
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