What is P vs np: Definition and 11 Discussions

The P versus NP problem is a major unsolved problem in computer science. It asks whether every problem whose solution can be quickly verified can also be solved quickly.
The general class of questions for which some algorithm can provide an answer in polynomial time is "P" or "class P". For some questions, there is no known way to find an answer quickly, but if one is provided with information showing what the answer is, it is possible to verify the answer quickly. The class of questions for which an answer can be verified in polynomial time is NP, which stands for "nondeterministic polynomial time". The informal term quickly, used above, means the existence of an algorithm solving the task that runs in polynomial time, such that the time to complete the task varies as a polynomial function on the size of the input to the algorithm (as opposed to, say, exponential time).
An answer to the P versus NP question would determine whether problems that can be verified in polynomial time can also be solved in polynomial time. If it turned out that P ≠ NP, which is widely believed, it would mean that there are problems in NP that are harder to compute than to verify: they could not be solved in polynomial time, but the answer could be verified in polynomial time.
The problem is considered by many to be the most important open problem in computer science. Aside from being an important problem in computational theory, a proof either way would have profound implications for mathematics, cryptography, algorithm research, artificial intelligence, game theory, multimedia processing, philosophy, economics and many other fields.It is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute, each of which carries a US$1,000,000 prize for the first correct solution.

View More On Wikipedia.org
  1. edmund cavendish

    A P vs NP & Godel | A Comprehensive Guide

    I think the essence is captured above.
  2. A

    A P vs NP Guessing and process of elimination

    If we suppose there is an algorithm for P vs NP, would it have to be able to find solutions where we now use trial and error? In harder Sudokus, for example, there are times when you have two or more possible numbers and need to guess whereafter you work the rest of the numbers through to see if...
  3. R

    A Consult: NP=P and P (3-SAT) - Is It Well Known?

    I need a consult. There is representing of 3-SAT formula as a conjunction of pair logical formulas. Each of this formulas has polynomial algorithm for searching response about its satisfiability and (if the formula sat - we can find in polynomial time any decision of all possible). It is not...
  4. L

    Can the P vs NP Problem Explain the Mechanics of Comedy?

    I don't have any understanding of P vs NP past the colloquial explanation of it, but it occurred to me that it is essential that P ≠ NP for comedy to function. For almost all comedy to work it relies on a "punchline" that is not easily predicted but, once revealed, can be easily and near...
  5. L

    Is the Subset Sum Problem Truly Solved by Generating Large Random Sets?

    Hello, My hobby is to design algorithms especially data compression algorithms, but when I can't find a solution to my problems I usually go find myself a different problem to solve because it helps me think differently or maybe it lights a bulb about the original problem …today I stumbled on...
  6. D

    P vs NP undecidable consequences

    I don't understand why if P vs NP can't be decided in ZFC, then there exist "near" polynomial time algorithms for NP. How would that possibly work?
  7. S

    MHB Unraveling the P vs NP Problem in Computer Science

    Didn't know what forum to post this in..There are some brilliant people on this forum, just wanted to know your thoughts on the P vs NP problem in Computer Science? Do you think it will ever be solved? I think P != NP. That being said, I do believe it could be solved but not with normal...
  8. K

    P vs NP. What if we just assumed P=NP?

    I don't know much about this P vs NP debate at all but what happens if they assume P = NP or P=/=NP? What does it mean when somebody resolves the debate? Why are there tons of mathematicians and computer scientists who are split between the two?
  9. J

    Understanding the P vs NP Problem: Factoring and Its Impact on Internet Security

    I have some questions about the presentation of the P vs NP problem here. I'm quite new to this stuff, so pardon my ignorance if I make dumb statements. http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf Specifically: First of all this statement is confusing to me...
  10. L

    Is the Proof for P=NP Legitimate? Exploring the Controversial Claim

    Hi I found a paper that claims to prove P=NP I can't say that I understand it much, so thought I'd ask for peoples opinions on it. It can be found here: http://arxiv.org/PS_cache/arxiv/pdf/1005/1005.3010v1.pdf Thanks
  11. L

    Can Freecell Algorithms Solve the P vs NP Problem?

    Hey guys, So I am a big fan of math, but at the moment, I am limited to calculus, so I don't really know much math at all. With that being said, I also happen to watch the show numbers, which is the first place I heard about the problem P vs NP. So after looking it up, I saw that it is a...