Computational intractability

From Computer Science Wiki
Jump to navigation Jump to search
Advanced programming[1]

An intractable problem is a problem in which the only exact solution is one that takes too many resources (time, memory, etc.). In other words, a problem in which no efficient solution (other than the worst-case complexity) exists. Often, this solution is a brute-force-styled solution, however, that is not to say there aren't effective heuristic solutions. It is important to not confuse computational intractability with NP-hard or NP-complete problems, which define a mathematically rigorous definition. An intractable can be P-complete, however, if the time taken grows in size too quickly, it may be impossible to solve.

Example: graph coloring. Exact graph coloring algorithms for large graphs can take centuries, however, there exist many heuristic algorithms that provide possible solutions (although not exact and perfectly optimized) in a short period of time.

Example: traveling salesman problem. Not only is TSP NP-hard, but an exact algorithm to it is also intractable as well. However, there exist many heuristic solutions to the TSP problem that provides a solution in a reasonable time.