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.
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...
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...
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...
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...
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...
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?
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...
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
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...