# P vs. NP -- The most notorious problem in theoretical computer science remains open

##### Oct 29, 2009 by Larry Hardesty

In the 1995 Halloween episode of The Simpsons, Homer Simpson finds a portal to the mysterious Third Dimension behind a bookcase, and desperate to escape his in-laws, he plunges through. He finds himself wandering across a dark surface etched with green gridlines and strewn with geometric shapes, above which hover strange equations. One of these is the deceptively simple assertion that P = NP.

In fact, in a 2002 poll, 61 mathematicians and computer scientists said that they thought P probably didn’t equal NP, to only nine who thought it did — and of those nine, several told the pollster that they took the position just to be contrary. But so far, no one’s been able to decisively answer the question one way or the other. Frequently called the most important outstanding question in theoretical , the equivalency of P and NP is one of the seven problems that the Clay Mathematics Institute will give you a million dollars for proving — or disproving. Roughly speaking, P is a set of relatively easy problems, and NP is a set of what seem to be very, very hard problems, so P = NP would imply that the apparently hard problems actually have relatively easy solutions. But the details are more complicated.

Computer science is largely concerned with a single question: How long does it take to execute a given algorithm? But computer scientists don’t give the answer in minutes or milliseconds; they give it relative to the number of elements the algorithm has to manipulate.

Imagine, for instance, that you have an unsorted list of numbers, and you want to write an algorithm to find the largest one. The algorithm has to look at all the numbers in the list: there’s no way around that. But if it simply keeps a record of the largest number it’s seen so far, it has to look at each entry only once. The algorithm’s execution time is thus directly proportional to the number of elements it’s handling — which computer scientists designate N. Of course, most algorithms are more complicated, and thus less efficient, than the one for finding the largest number in a list; but many common algorithms have execution times proportional to N2, or N times the logarithm of N, or the like.

A mathematical expression that involves N’s and N2s and N’s raised to other powers is called a polynomial, and that’s what the “P” in “P = NP” stands for. P is the set of problems whose solution times are proportional to polynomials involving N's.

Obviously, an algorithm whose execution time is proportional to N3 is slower than one whose execution time is proportional to N. But such differences dwindle to insignificance compared to another distinction, between polynomial expressions — where N is the number being raised to a power — and expressions where a number is raised to the Nth power, like, say, 2N.

If an algorithm whose execution time is proportional to N takes a second to perform a computation involving 100 elements, an algorithm whose execution time is proportional to N3 takes almost three hours. But an algorithm whose execution time is proportional to 2N takes 300 quintillion years. And that discrepancy gets much, much worse the larger N grows.

NP (which stands for nondeterministic polynomial time) is the set of problems whose solutions can be verified in polynomial time. But as far as anyone can tell, many of those problems take exponential time to solve. Perhaps the most famous problem in NP, for example, is finding prime factors of a large number. Verifying a solution just requires multiplication, but solving the problem seems to require systematically trying out lots of candidates.

So the question “Does P equal NP?” means “If the solution to a problem can be verified in polynomial time, can it be found in polynomial time?” Part of the question’s allure is that the vast majority of NP problems whose solutions seem to require exponential time are what’s called NP-complete, meaning that a polynomial-time solution to one can be adapted to solve all the others. And in real life, NP-complete problems are fairly common, especially in large scheduling tasks. The most famous NP-complete problem, for instance, is the so-called traveling-salesman problem: given N cities and the distances between them, can you find a route that hits all of them but is shorter than … whatever limit you choose to set?

Given that P probably doesn’t equal NP, however — that efficient solutions to NP problems will probably never be found — what’s all the fuss about? Michael Sipser, the head of the MIT Department of Mathematics and a member of the Computer Science and Artificial Intelligence Lab’s Theory of Computation Group (TOC), says that the P-versus-NP problem is important for deepening our understanding of computational complexity.

“A major application is in the cryptography area,” Sipser says, where the security of cryptographic codes is often ensured by the complexity of a computational task. The RSA cryptographic scheme, which is commonly used for secure Internet transactions — and was invented at MIT — “is really an outgrowth of the study of the complexity of doing certain number-theoretic computations,” Sipser says.

Similarly, Sipser says, “the excitement around quantum computation really boiled over when Peter Shor” — another TOC member — “discovered a method for factoring numbers on a quantum computer. Peter's breakthrough inspired an enormous amount of research both in the computer science community and in the physics community.” Indeed, for a while, Shor’s discovery sparked the hope that quantum computers, which exploit the counterintuitive properties of extremely small particles of matter, could solve NP-complete problems in polynomial time. But that now seems unlikely: the factoring problem is actually one of the few hard NP problems that is not known to be NP-complete.

Sipser also says that “the P-versus-NP problem has become broadly recognized in the mathematical community as a mathematical question that is fundamental and important and beautiful. I think it has helped bridge the mathematics and computer science communities.”

But if, as Sipser says, “complexity adds a new wrinkle on old problems” in , it’s changed the questions that computer science asks. “When you’re faced with a new computational problem,” Sipser says, “what the theory of NP-completeness offers you is, instead of spending all of your time looking for a fast algorithm, you can spend half your time looking for a fast algorithm and the other half of your time looking for a proof of NP-completeness.”

Sipser points out that some algorithms for NP-complete problems exhibit exponential complexity only in the worst-case scenario and that, in the average case, they can be more efficient than polynomial-time algorithms. But even there, NP-completeness “tells you something very specific,” Sipser says. “It tells you that if you’re going to look for an that’s going to work in every case and give you the best solution, you’re doomed: don’t even try. That’s useful information.”

Provided by Massachusetts Institute of Technology (news : web)

Explore further: Researchers use Twitter to predict crime

## Related Stories

#### CMU professor honored for computational complexity breakthrough

May 21, 2007

Computer scientists at Carnegie Mellon University and the Russian Academy of Science will share the Association for Computing Machinery's 2007 Gödel Prize for their seminal work on what many consider the most important unresolved ...

#### Quantum computing may actually be useful, after all

Oct 09, 2009

(PhysOrg.com) -- In recent years, quantum computers have lost some of their luster. In the 1990s, it seemed that they might be able to solve a class of difficult but common problems — the so-called NP-complete ...

#### Diesel exhaust exposure biomarker found

Jul 31, 2007

A Japanese-U.S. science team has created the first test to detect a biomarker for human exposure to diesel exhaust, a probable human carcinogen.

#### Non-polypoid colon lesions associated with colorectal cancer

Mar 04, 2008

Flat, non-polypoid colorectal neoplasms (NP-CRNs), which may be difficult to detect, appear to be relatively common and may have a greater association with cancer compared with the more routinely diagnosed type of colorectal ...

#### Yale Professor wins Godel Prize for showing how computer algorithms solve problems

Aug 13, 2008

Daniel A. Spielman, professor of applied mathematics and computer science at Yale, has been awarded the prestigious Gödel Prize for developing a technique, known as Smoothed Analysis, that helps predict the ...

#### How Time-Traveling Could Affect Quantum Computing

Nov 20, 2008

(PhysOrg.com) -- If space-time were constructed in such a way that you could travel back in time, it would create some pretty strange effects. One of these oddities, as many people know, is the “grandfather paradox.” ...

## Recommended for you

#### Researchers use Twitter to predict crime

19 hours ago

Hidden in the Twittersphere are nuggets of information that could prove useful to crime fighters—even before a crime has been committed.

#### UT Dallas professor to develop framework to protect computers' cores

Apr 18, 2014

UT Dallas cybersecurity expert Dr. Zhiqiang Lin has received funding from the U.S. Air Force to develop a defense framework that burrows deep into a computer system to protect its core.

#### Researcher finds hidden efficiencies in computer architecture

Apr 18, 2014

The computer is one of the most complex machines ever devised and most of us only ever interact with its simplest features. For each keystroke and web-click, thousands of instructions must be communicated ...

#### Scientists apply new graph programming method for evolving exascale applications

Apr 18, 2014

(Phys.org) —Hiding the complexities that underpin exascale system operations from application developers is a critical challenge facing teams designing next-generation supercomputers. One way that computer ...

Apr 17, 2014

(Phys.org) —Google engineers working on software to automatically read home and business addresses off photographs taken by Street View vehicles, have created a product so good that not only can it be used ...

#### Preventing AI from developing anti-social and potentially harmful behaviour

Apr 17, 2014

Next time you play a computer at chess, think about the implications if you beat it. It could be a very sore loser!

## User comments : 5

Adjust slider to filter visible comments by rank

##### winthrom
5 / 5 (1) Oct 29, 2009
Very good description indeed. Increases in computing power (including parallel processing) will enlarge the universe of difficult NP complete problems that can be solved when the polynomial number is not to large.

A comment on "NP complete". My math teacher, many years ago, noted that the Euclidian Geometry theorms might not be NP complete. By this he meant that there was no way to verify that all possible axiom combinations of NP could be determined, much less a minimum set resolving all of them. [This includes using the parallel line theorm as an axiom]

We also looked at axioms for a simple geometry case where NP complete was obvious. (1) There exits a point. (2) There exits a line. (3)Each line can have no more than three points on it. (4) Each point can have no more that three lines through it. The min soln that uses all axioms at once is a triangle with lines splitting each vertex and connected to the midpoint of the line opposite the vertex being split. 6 lines 10 points.
##### sender
not rated yet Oct 29, 2009
The problem seems to be in the concept of counters rather than hardcoded encoding schemas and processing.

e.g. 2 can either be a binary 10(two digit registers) or a logarithmic optical waveform(one modulation) translated to a nematic crystal in a parallel optronic resistance grid array
##### bhup_anand
5 / 5 (1) Oct 30, 2009
I argue that we need a new paradigm for placing the PvNP issue in a resolvable perspective.

The problem involves recognition of the fact that there are number-theoretic functions (relations) which are computable instantiationally (meta-mathematically decidable), but not algorithmically (formally unprovable).

Goedel constructed precisely such an Arithmetical relation, R(x), in 1931.

He gave an argument from which it follows that although R(x) is instantiationally equivalent to a partial recursive relation, it is not, itself, partial recursive (thus contradicting the Church-Turing Thesis).

http://alixcomsi....M_Update

Chaitin's more recent Omegas share a similar characteristic.
##### bhup_anand
not rated yet Oct 30, 2009
Sorry, the link in my post should be:

http://alixcomsi....date.pdf
##### eachus
not rated yet Nov 11, 2009
He gave an argument from which it follows that although R(x) is instantiationally equivalent to a partial recursive relation, it is not, itself, partial recursive (thus contradicting the Church-Turing Thesis).

I think you are missing something. Since any problem in NP has a proof in P of a correct answer, such a proof will allow you to construct an deterministic (but not P time) algorithm to solve the NP problem. NP-hard problems, which are at least as hard as NP-complete problems need not have such a proof of correctness and may not be partial recursive.

For example, take the traveling salesman problem. For a given map, there is a minimum route. Finding that route is NP-hard, but might not be in NP. Finding a route shorter than or equal to k, for arbitrary k, is in NP. Providing a polynomial time extension to the second problem to find the best solution puts it in NP even if no polynomial time solution is known to the first problem.

(The margin is too narrow to continue. ;-)

## More news stories

#### Review: With Galaxy S5, Samsung proves less can be more

Samsung Electronics Co. has produced the most formidable rival yet to the iPhone 5S: the Galaxy S5. The device, released over the weekend, is the fifth edition of the company's successful line of Galaxy S ...

#### To prevent data theft, businesses race to adopt new technology

Recent high-profile data breaches at Target and Neiman Marcus have accelerated plans by banks and retailers to implement technologies they say will prevent hackers from stealing consumers' account information.

#### Google Trends info is placed on inbox duty for subscribers

(Phys.org) —Google Trends has added a new service to its mix, where users can enter email subscriptions for Google Trends, and can be sent notifications on topics of interest, showing them what is popular ...

#### Growing app industry has developers racing to keep up

Smartphone application developers say they are challenged by the glut of apps as well as the need to update their software to keep up with evolving phone technology, making creative pricing strategies essential to finding ...

#### Monoprice takes on Amazon in trade of cheap electronics

You'd only have to drive by the empty shells of Circuit City stores, and soon RadioShacks, to see why a company in Rancho Cucamonga, Calif., represents a nightmare for the retail electronics industry.

#### Study finds codeine often prescribed to children, despite available alternatives

Despite its potentially harmful effects in children, codeine continues to be prescribed in U.S. emergency rooms, according to new research from UCSF Benioff Children's Hospital San Francisco.

#### Making graphene in your kitchen

Graphene has been touted as a wonder material—the world's thinnest substance, but super-strong. Now scientists say it is so easy to make you could produce some in your kitchen.

#### Study casts doubt on climate benefit of biofuels from corn residue

Using corn crop residue to make ethanol and other biofuels reduces soil carbon and can generate more greenhouse gases than gasoline, according to a study published today in the journal Nature Climate Change.

#### Bulletproof nuclei? Stem cells exhibit unusual absorption property

Stem cells – the body's master cells – demonstrate a bizarre property never before seen at a cellular level, according to a study published today from scientists at the University of Cambridge. The property ...

#### Team identifies source of most cases of invasive bladder cancer

A single type of cell in the lining of the bladder is responsible for most cases of invasive bladder cancer, according to researchers at the Stanford University School of Medicine.