Home > Uncategorized > So what if it is undecidable or NP!

So what if it is undecidable or NP!

September 19, 2010

An all too frequent refrain I hear when discussing how to solve a problem is “… but it is undecidable” and this is often followed by the statement that it is not worth attempting to solve the problem. Sometimes NP-completeness gets mentioned in the mix of mumbo-jumbo that is talked about this such problems.

Just because a problem is undecidable does not mean that developers should not attempt to write code to solve it. When a problem is undecidable there exists at least one set of inputs for which the algorithm you use cannot be relied on to give a correct answer and however much you rework the algorithm at least one such set of input will always exist (this set of input may change from algorithm to algorithm).

Undecidability theorems do not say anything about what percentage of all possible input sets have this ‘not known if answer is correct’ property. If there are other theorems addressing this question I don’t know about them (and I don’t claim to be an expert or up to date on this topic).

Mathematicians (well at least those working on Zermelo-Fraenkel set theory) spend lots of time trying to find problems that are undecidable and would be overjoyed to find an instance of a problem/dataset where undecidability actually occurred.

Undecidability is an interesting property; however I think educationalists should stop overselling it and give their students some practical advice such as “Don’t worry, these situations are extremely rare and perhaps many orders of magnitude less likely to generate a fault than the traditional fault generation methods.”

NP’ness deals with how execution time grows as the problem input size grows. It is easy to jump to the conclusion that problems known to be in P are ‘good’ and those believed to be in NP are ‘bad’; and that NP problems take so long to solve they are not worth consideration. For small input sets the constant multipliers in the non-polynomial time equation may mean that the actual execution time is acceptable; this is something that requires a bit of experimentation to find out.

Sometimes a NP problem can be solved in an acceptable amount of time.

The reverse situation is also true. While polynomial execution time does not grow as fast as non-polynomial (which could be exponential or worse) execution time, for small input sets the constant multipliers in the polynomial time equation may result in it starting off with a huge overhead, with problem size only becoming a significant factor for very large inputs.

Sometimes P problems cannot be solved in an acceptable amount of time.

  1. September 19, 2010 15:49 | #1

    About a year ago I had blogged similar thoughts. I’m feeling very glad to see that other in the “so what” mood. Sometimes people plead on NP-completeness to avoid providing any solution to a problem, when one (just any) is needed. It is fun to see NP used as a solution “blocker” in for small inputs.

  2. TemporalBeing
    September 21, 2010 13:42 | #2

    Agreed. The problem likely needs a solution regardless of whether it i NP complete or not. So instead of saying “it’s not worth solving” we should hunker down and solve it at least sufficiently for the problem we have; you don’t have to have a complete problem resolution, just one that is good enough to move forward with. It can always be refined a little later on if need be.

  3. Anonymous Cowherd
    October 4, 2010 23:33 | #3

    “It is easy to jump to the conclusion that problems known to be in P are ‘good’ and those believed to be in NP are ‘bad’; and that NP problems take so long to solve they are not worth consideration.”

    But that conclusion would be wrong, because NP is actually a superset of P. One of the reasons a person might jump to faulty conclusions is an overexposure to blog posts that treat “NP” as if it were an abbreviation for “not in P” or “non-polynomial-time”… so can we be more careful about that in the future, please?

  1. No trackbacks yet.
Comments are closed.