A beginning look into the nature of intractability.

An intractable problem seems to have one of two main cases.

The following is the subset of intractability I’m considering:

The problem has an algorithm, but the solution cannot be computed for some large magnitude of time (probably t>5 years on an arbitrarily large grid of computers).

1. There is a subset of the problem with enough of a result to be worth computing the subset and t<=5 years on an arbitrarily large grid. In this case the problem should be reduced to the subset and computed. 2. There is no subset available or all potential subsets have computational times equal to or greater than the original problem. In this case the problem should be shelved until: a. A better algorithm is developed or b. Sufficient time elapses as to make the problem solvable in <= 5 years on an arbitrarily large grid. (In other words, if it's a bitch to solve now and you can solve something simpler that will give you 80% of what you want, solve that. If you can't then either find a way to or wait until computing power has advanced so that you can) Peace, Adam


Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.