Last week I wrote about needle-in-a-haystack problems, in which it’s hard to find the solution but if somebody tells you the solution it’s easy to verify. A commenter asked whether such problems are related to the P vs. NP problem, which is the most important unsolved problem in theoretical computer science. It turns out that they are related, and that needle-in-a-haystack problems are a nice framework for explaining the P vs. NP problem, which few non-experts seem to understand.

Stated simply, the P vs. NP problem asks whether needle-in-a-haystack computational problems can exist. To understand what this means, we need to take a short detour into computer science theoryland. It’s perfectly safe, but stay close to the group so you don’t wander off into a finite field…. Okay, let’s meet P and NP.

P is the set of problems that can be solved efficiently. The precise theoretical definition of “efficient” is a bit subtle: we define the “size” of a problem to be the number of characters needed to write down the problem; and we say a solution method is efficient if, when the problem is large, the method can finish in a length of time that is less than the problem size raised to some power.

For example, suppose we are given two N-digit numbers, A and B, and a 2N-digit number C, and we’re asked whether A times B equals C. It requires 4N characters to write down the problem, one character for each digit in each of the numbers. We can solve the problem by multiplying A and B, using the multiplication method we learned in school, and then comparing the result to C. The multiplication will take us roughly N-squared steps, and the comparison is faster than that. So the solution time will grow roughly as N-squared, and if N is large this is less than the third power of the problem size (i.e., less than 4N raised to the third power). Therefore multiplication is in P, which matches our intuition that we know how to multiply efficiently.

Here’s another example, the “traveling salesperson problem” (TSP): given a list of cities, a table showing the airfare between each pair of cities, and a total travel budget, is there an itinerary that visits every city on the list and returns to where it started, without exceeding the total travel budget? One way to solve this problem is to try out all of the possible itineraries, and see if there’s one that is cheap enough. That works, but it is not efficient, because its running time grows faster than any fixed power of the problem size. No efficient algorithm for the TSP is known. There might be one, but if there is one we haven’t discovered it yet. So we don’t know if the TSP is in P.

You might have guessed by now that P stands for “polynomial”, as in “solvable in polynomial time”. That is indeed the origin of the name P. And you might go on to guess that NP stands for “not polynomial” — but that would be wrong. If you must know, NP stands for “nondeterministic polynomial”. I won’t bother explaining what “nondeterministic” means here, because that has confused generations of students. Instead, let’s use an alternative, but equivalent, definition of NP.

NP is the set of problems having yes/no answers, for which, whenever the correct answer is “yes”, there is some “hint” that allows us to verify the “yes” answer efficiently. Think about the TSP: if somebody tells you a cheap itinerary, you can verify efficiently that that itinerary visits all of the cities, ends where it started, and costs less than the travel budget. So the TSP is in NP.

Multiplication is in NP as well. Given any hint (“booga booga”, say) we can verify that A times B equals C, by simply ignoring the hint, and then multiplying and comparing as above. By a similar argument, any problem in P must also be in NP.

You can see now how this connects with needles and haystacks. If a problem is in NP but not in P, it’s like a needle-in-a-haystack problem: we can verify the answer efficiently if we’re given a hint, but without a hint we can’t find the answer efficiently. So asking whether needle-in-a-haystack problems exist is exactly the same as asking whether P is different from NP.

Are P and NP different? We don’t know. Consider the Traveling Salesperson Problem. We know it’s in NP, because we can verify the answer efficiently given a hint, but we don’t know if it’s in P. We don’t know if the TSP can be solved efficiently — we haven’t found an efficient solution yet but we can’t rule out the possibility that somebody will discover one tomorrow. A lot of people have tried really hard for a long time to find an efficient solution, so most experts tend to assume that no efficient solution is possible — but the experts have been wrong before.

If, on the other hand, P and NP turn out to be equal, the consequences would be huge. For example, much of cryptography would collapse. Decrypting a message is supposed to be a needle-in-a-haystack problem—easy if you have a hint (i.e., the secret decryption key) but hard otherwise.

It’s annoying, to say the least, that such a basic question about information remains unanswered. For decades theorists have been trying to scale the P vs. NP mountain from various directions,without success. The rest of us have gotten accustomed to assuming that needle-in-a-haystack problems exist, and hoping for the best.

Sometimes the same idea comes flying at you from several directions at once, and you start seeing that idea everywhere. This has been happening to me lately with needle-in-a-haystack problems, a concept that is useful but often goes unrecognized.

A needle-in-a-haystack problem is a problem where the right answer is very difficult to determine in advance, but it’s easy to recognize the right answer if someone points it out to you. Faced with a big haystack, it’s hard to find the needle; but if someone tells you where the needle is, it’s easy to verify that they’re right.

This idea came up in a class discussion of Beth Noveck’s Wiki-Government paper. We were talking about how government can use crowdsourcing to learn from outside experts, and somebody pointed out that crowdsourcing can work well for needle-in-a-haystack problems. If somebody in the crowd knows the answer, they can announce it, and other participants in the discussion will recognize that the proposed answer is correct. This is the basis for the open-source maxim that “given enough eyes, all bugs are shallow”. It’s also the theory underlying the Peer to Patent project, in which distributed experts tried to find the best prior art document that would invalidate a patent application.

The idea came up again in a discussion of online passwords. A highly secure system doesn’t remember your password, because an attacker who managed to observe the stored password could impersonate you. But if the system doesn’t store your password, how can it verify that the password you enter is correct?

The answer is that the system can create a needle-in-a-haystack problem to which your password is the only right answer. By remembering this problem rather than your password, the system will be able to recognize your password when it sees it, but an attacker who learns what the problem is will have great difficulty determining your password. There are standard cryptographic tricks for generating this kind of needle-in-a-haystack problem.

The idea came up a third time when I read a paper with the eye-catching title “Why Most Published Research Findings Are False“. The paper explains why the vast majority of research findings in a field might be false, even if the researchers do everything right; and it suggests that this is the case for some areas of medical research.

To see how this might happen, imagine a needle-in-a-haystack problem that has one right answer and a million wrong answers. Suppose that our procedure for verifying the right answer when we see it is not flawless but instead is wrong 0.01% of the time. Now if we examine all of the 1,000,000 wrong answers, we will incorrectly classify 100 of them (0.01% of 1,000,000) as correct. In total, we’ll find 101 “correct” answers, only one of which is actually correct. The vast majority of “correct” answers — more than 99% of them — will be wrong.

Any research field that is looking for needles in haystacks will tend to suffer from this problem, especially if it relies on statistical studies, which by definition can never yield absolute 100% confidence.

Which brings us back to crowdsourcing. If we’re not perfect at recognizing proposed answers as correct — and no human process is perfect — then a crowdsourcing approach to needle-in-a-haystack problems could well yield wrong answers most of the time.

How can we avoid this trap? There are only two ways out: reduce the size of the haystack, or improve our procedure for evaluating candidate answer. Here crowdsourcing could be helpful. If we’re lucky, vigorous discussion within the crowd will help to smoke out the false positives. It’s not just access to experts that helps, but dialog among the experts.

On April 27th, the Center for Information Technology Policy is hosting a one-day workshop on campus here at Princeton. We invite you to attend. Here is the summary of the event, called Internet Security, Internet Freedom:

The internet is at once a means for great openness and great control — expression and exclusion. These forces have long been at work online, but have recently come to the fore in debates over the United States’ cyber security policy and its increased focus on “internet freedom.” The country now has a Cybersecurity “czar” that has presented a 12-part national initiative, and also has a Secretary of State who has forcefully stated the case for internet freedom. But what do these principles mean in practice?

This workshop explores how security and freedom both compliment each other and compete. A spectrum of security risks at different layers of the network beg for technical and governance solutions. Flash points like the recent Google-in-China developments highlight the nexus of security and speech. A growing discourse about internet freedom calls out for workable theories and models. This event will bring together technologists, policymakers, and academics to discuss the state of play and viable ways forward.

The keynote speaker will be Alec Ross, Senior Advisor for Innovation in the Office of Secretary of State. Alec will discuss the State Department’s increased focus on the issue of Internet freedom. He recently commented that 2009 was “the worst year in the history of the Internet as it related to Internet freedom.” The panelists feature a variety of experts on issues of online freedom as well as network security.

Please join us. For more information and instructions on how to register, see the workshop page here:
http://citp.princeton.edu/internet-security-internet-freedom/