P != NP question

Question

Not a 'pure' programming question, but since it is deeply involved in programming theory, I thought it best to ask here.

Regarding the P NP problem, this excerpt from http://en.wikipedia.org/wiki/P_versus_NP_problem : "In essence, the question P = NP? asks: Suppose that yes answers to a yes or no question can be verified quickly. Then, can the answers themselves also be computed quickly?"

I am left wondering, how is the speed of verifying an answer related to the speed of generating a solution?

Answer 1

No, P=/NP.

The answer is Co-NP-Asymmetric-Partially-Complete

See my full answer here at my website:

https://singularitariantechnologies.wordpress.com/exponential-breakthroughs-in-epistemology-every-week/

Singularitariantechnologies.wordpress.com

To basically summarize the answer to your question, the answer is no, generally, except in one instance where P=NP, ergo the co-np-asymmetric partially incomplete / complete answer.

To do this I used Google.com as a database which could give me a verified answer in polynomial time, and then I wanted to see if the answer would be computable predicated on the best Axiomatic reduction of polynomial, consisting of exponentiated terms and inherently, the answer is that with more than two variables (exponents in this case), the answer is not computable, even though we would know what the verified answer would be.

Obviously this leaves black hat hackers with effectively no alternative, as in the future encryption algorithms will not be so simple. Also, this is technically only one instance where P=NP, because axiomatically, a polynomial must consist of more than one term, ergo P=/=NP iff variables >=3 and P=NP iff variables <= 2.

Read my full documentation on my website or on Google Drive, I also provide a spreadsheet link to my work on singularitariantechnologies.wordpress.com

What does this effectively mean? In the future there will be no black hat hacking, even if you factor in attempts to axiomstically reduce encryption attacks via modulo two, it just won't work with advanced encryption (complex polynomial encryption, with some caveats and bells and whistles to make it much harder to even attempt to break a cipher, or any encrypted data thereof..)

Answer 2

Whether they're related or not is one of the Claypool Foundation's "Millenium Problems", and they'll give a million dollars to somebody providing an appropriate proof that hold up under a few years of intense examination.

The types of questions are more related than they look, since another definition of an NP problem is one that can be solved efficiently with an arbitrarily parallel computer.

One thing that really interests people is the lack of a proof. There are proofs for similar-looking questions, but not this one. That intrigues people, especially mathematicians, since a proof is likely to bring a lot of insight into other things. That is apparently the case for Perelman's proof of the Poincare Conjecture, another of the Millenium Problems.

Another issue is the impact this could have. Right now, few people believe that there is an efficient method for solving NP-complete problems, so a discovery that P!=NP would have little practical impact. A discovery of an efficient way to solve NP-complete problems would revolutionalize a lot of computer science. It would make a lot of things much easier, and would destroy cryptography as we know it by making decryption easy.

Answer 3

There isn't a direct relation here though. There may be an intuitive feel that verifying an answer is easier than generating an answer as part of any generation would be to ensure the answer is correct. Thus, one could take a brute force approach to try different solutions but this tends to lead to exponential complexities that are beyond P, or so that is what I recall from Complexity class years ago.

Answer 4

Essentially, in the set of NP, or Nondeterministic Polynomial time, problems, the answer can be verified in polynomial time. The question is whether all such problems can be determined in polynomial time.

If P=NP is true, and such algorithms are discovered many problems that are hard to solve but easy to verify the solution, such as proofs, become as easy to solve as to verify.

Answer 5

P is the class of all languages that can be computed in polynomial time by a deterministic Turing machine. A modern computer is very much like a deterministic Turing machine, except that a Turing machine essentially has infinite memory. This distinction is generally ignored for practical purposes.

NP is the class of all languages that can be computed in polynomial time by a non-deterministic Turning machine. A nondeterministic Turing machine does not correspond to any real-world device.

It is a basic fact of computational complexity that NP is equivalent to the class of languages whose verification problems are in P. In fact, NP is sometimes defined as this class; the two definitions are interchangeable, and the verification definition has the benefit of direct relevance to the deterministic-Turing-machine-like computers in the real world.

So NP is the class of problems that are verifiable in poly-time on a "real" machine and solvable in poly-time on a very similar theoretical machine. Thus, the questions of solvability and verifiability are linked.

Now, most computer scientists believe that P and NP are not equivalent; that is, that there exist languages computable in poly-time by a nondeterministic Turing machine but not by a deterministic Turing machine, or equivalently that are not solvable in poly-time by a deterministic Turing machine but whose solutions can be verified in poly-time by a deterministic Turing machine.

Answer 6

This problem has been solved today!

(Possibly.)

Answer 7

Suppose you had tremendous parallelism -- however much you wanted. You could then simultaneously generate all possible solutions, check which of these were correct, and output a correct solution. In the presence of infinite parallelism, this is a method of generating a solution. The set of problems in NP are those for which this procedure would work quickly, because the only interesting computational step it is performing is checking whether solutions are correct, and this can be done efficiently for problems in NP. Note that for some other problems, even this parallelism would not allow us to find solutions quickly, since it requires that checking solutions is easy.

But we don't have infinite parallelism. Can we somehow simulate it, with only a polynomial amount of overhead? If so, we could imagine running the above procedure, and efficiently finding solutions for every problem for which verification was easy. This is the P vs. NP question.

Intuitively, it seems clear that the answer is "no" (i.e. P != NP). How could we possibly simulate infinite parallelism? This is what almost every expert believes. But it is a mystery how to prove it, and one that is worth $1,000,000 in prize money.

Answer 8

Let's assume I am handed a solution to a "hard" problem by a magician, and I can easily verify if this solution is correct or not. BUT, can I compute this solution myself easily? (polynomial time)

This is exactly the question.

Answer 9

It may or may not be related.

People care about NP problems because we want to solve them quickly and all the time, but so far we have not found a way to solve them quickly. We want to know if there a quick way to solve them or if we should give up trying.