Intractability (nonfiction)

From Gnomon Chronicles
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: