Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.

Channels ▼

Cameron and Tracey Hughes

Dr. Dobb's Bloggers

A Way You Could Use P ≠ NP

September 01, 2010

It's the talk of the Internet and around water coolers: Did Vinay Deolalikar, a mathematician at HP Labs, really produce the proof for P ≠ NP? If so, it's sure to be a “Moment of Geek” on Rachel Maddow's show, Countdown with Keith Olbermann's “What will you be talking about tomorrow?”, Rick's List or even a mention by Rush (maybe not).

Well, maybe we've missed those, but it was no way we could miss mentioning it on our blogs considering we have talked allot about NP and AI complete, and determinism stuff many times.

How hard is it to come up with algorithms that solve problems with solutions that are verifiable? Well, when considering a certain set of difficult problems, the question is not how hard is it be to come up with an algorithm, the question is does an algorithm even exist. For most everyday working programmer analysts, software developers and engineers, this question may not be asked. Of course you can solve the problem, of course you can design an algorithm to solve the problem, but how well will it perform is the issue. What resources will I have to throw at it in order to make it have acceptable performance? Use a better compiler, a better library for those functions, whatever can work. Throw some cores, some threads, some hyperthreads, hardware threads at it, faster processors, see if that helps. And well for most problems, it is the case that those techniques will yield improvement.

But ... there is a class of problem where if you have a core for every atom in the universe running at the speed of light in parallel, you could not produce a solution, a decision, an optimization, a path, nothing. And it is our hope that every working developer, engineer, or analyst can recognize those problems when they see them.

But the talk about P and NP problems has to do with whether algorithms exist or don't exist for certain very hard problems. P problems are decision problems where a reasonably efficient deterministic algorithm does exist and executes in polynomial time (worst case) for a set of inputs. NP problems have nondeterministic algorithms which produces solutions as a string and a deterministic method that executes in polynomial time that verifies the solution (a yes or no decision). We discussed determinism and nondeterminism in an earlier blog. P problems are a subset of NP problems. Since NP problems have two phases: a nondeterministic phase and a deterministic phase, then the P problem would be a type of NP problem where the nondeterministic phase is ignored or executes zero steps.

NP complete problems are intractable problems where there is no known nondeterministic polynomial bound algorithm that can produce a solution with a reasonably large input. NPC is a subset NP problems deemed the hardest of NP problems (evidently!).

So what is the relationship between P, NP, and NPC, and what is the proof for that relationship? Does P = NP or does P ≠ NP? The answer affects what we can possibly achieve in our field but also what is possible across many sciences. It really defines what type of problems we can find solutions to in general. What are our computational limitations?

There are a lot of NPC problems. Many are pretty basic problems and are important in many fields as I already mentioned. We have reasonable solutions out there but they are more approximations to solutions or for small or moderate input size. But as computational ability increases as well as what we are processing (more people to process, more social security numbers, more files, more storage, etc.) we have to be able to handle very very large size inputs of any and everything.

If P = NP then any problem that can be verified quickly and can be solved quickly. A polynomial time algorithm for one NPC problem can be used to solve all the problems in NP. All types of difficult problems could be solvable with reasonably efficient algorithms.

But it is thought that NP is larger than P therefore P ≠ NP. That is what Vinay Deolalikar has attempted proved. In his paper he argues a known propositional logic NPC problem, Boolean satisfiability. It asks if a collection of logical statements can all be true at the same time or whether they contradict each other. He claims to have proven that there is no algorithm that can complete it quickly. So it is not a P problem. If so then we would have to accept that some problems are irreducibly complex and well ... its too horrible to think, we would not be able to solve our:

Which taste better, pepsi or coke?

But as it looks, with some peer reviews of his paper, it doesn't seem his proof is holding up. An interview with Scott Aaronson, a MIT Associate Professor of Electrical Engineering and Computer Science, sees flaws:

Yes, almost all of us believe already that P is not equal to NP. But this is one of those things where it's not so much the destination as the journey. It's the massive amount of new understanding of computation that's going to be needed to prove such a statement. What are we trying to prove? That for solving all these natural optimization problems, or these search problems, or a proof of a theorem, finding the best schedule for airlines, breaking cryptographic codes -- all these different things, that there's no algorithm, no matter how clever, that's going to solve them feasibly. So in order to prove such a thing, a prerequisite to it is to understand the space of all possible efficient algorithms. That is an unbelievably tall order. So the expectation is that on the way to proving such a thing, we're going to learn an enormous amount about efficient algorithms, beyond what we already know, and very, very likely discover new algorithms that will likely have applications that we can't even foresee right now.

But here's a way you could use P ≠ NP the next time you miss a deadline at work when a solution somehow escapes you, tell your very informed boss, “Well you know P ≠ NP”, and he will reply, “Yeah, I heard that”.

Related Reading

More Insights

Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.