P = NP?
I was thinking about putting this thread in Cryptography as the result of its solution would very much affect that field but I felt it was more of an Off-topic issue in general.
So what do you guys think? Does P = NP?
That question could conceivably be as difficult to answer as the debate between Intelligent Design and Evolution. A couple semesters ago I took a Computational Complexity course where I learned more about these classes of P and NP, however my professor did not go into really any detail regarding the in/equality of these two algorithm classes.
Basically, if P does equal NP then any problem that can be verified in polynomial time can also be solved in polynomial time (it goes without saying the reverse order of course). As I stated previously, with cryptography, the solution P = NP would mean that no form of encryption would be safe since the entire purpose of the encryption algorithms is that processing time is just too large to compute the keys to break the encryption (RSA and the Factorization of large prime numbers).
(Quantum computing is another fear of the cryptography field but that is another discussion).
Now, it is very hard to believe that P = NP given the substantial claim that it is. If this was proven true it would change the way we view the world completely. As one person put it "Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss…" meaning that there is no difference between knowing the solution and finding it.
If P was proven NOT to equal NP, while not quite as significant a result, there would still be great benefits in this discovery. It would prove that there just isn't an efficient way, with the currently accepted axioms describing our world, to solve certain problems even if the answer can be verified.
I am kind of torn between the two views. While P = NP would be a giant discovery and among the top (if not the very most) revolutionary discovery of all time, and P != NP would be another huge discovery in its own respect, I have trouble accepting that either could be true. Therefore if I had to choose one I would probably go with the majority and say P != NP however I think it is probably impossible to prove in at least the next century.
suid wrote: with cryptography, the solution P = NP would mean that no form of encryption would be safe Not all forms of encryption surely. One time pads would still be safe.
As for the whole P=NP thing, I don't really know all that much on this subject so I can't provide any kind of argument or reasons, but I think (and hope) that P!=NP because otherwise that would mean most of the stuff I do would be unnecessary. :(
starofale wrote: Not all forms of encryption surely. One time pads would still be safe. You would be absolutely correct with that; one time pad cannot be broken unless you can predict the pseudo random values generated. Also, I find that the analogy which the OP quoted is off; if I've understood it correctly, then it shouldn't really be that anyone who can appreciate a symphony would be mozart, it'd be more like "anyone who can perform a symphony would be mozart", which is a drastic difference. It's sort of like all those faggots with guitars who brag about how easy <insert popular metal/hard rock song> is to play, even though they aren't the ones creative enough to write it themselves.
Also, the major problem with a topic like this is that most people, me included, have fuck all idea what mathematical terms are in English.
Edit: oh and also, as shown with the one time pad example, difficulty of factorization is not the base of all encryptions. Furthermore, that the security within RSA depends solely on that is merely an assumption, but has yet to be proven; a more fitting example would be Rabin.
COM wrote: Also, the major problem with a topic like this is that most people, me included, have fuck all idea what mathematical terms are in English.
I hate this too. If there's one way Esperanto could help the world, it would be assisting in bridging the linguistic divide in matters of science.
Fucking anglocentric society is killing me.
Arabian wrote: What sort of classes would one take that involve discussion of these problems?
At least four math classes on university level of the type found in master of engineering courses; such as linear algebra, statistics, discrete mathematics and then cryptography. That's pretty much over a year of just cramming math, it's fucking rough.
COM wrote: [quote]spyware wrote: If there's one way Esperanto could help the world, it would be assisting in bridging the linguistic divide in matters of science. Agreed, surprising to see someone else who's even heard of it. Shame it didn't take off, but you work with what you get I suppose.[/quote]
I was also intrigued that there are other people who have at least heard of Esperanto. It's got a serious community over at lernu.net though. Ironically enough though, Esperanto itself basing most of its vocabulary/grammar on Romance and Germanic languages puts the rest at a disadvantage.
COM wrote: [quote]Arabian wrote: What sort of classes would one take that involve discussion of these problems?
At least four math classes on university level of the type found in master of engineering courses; such as linear algebra, statistics, discrete mathematics and then cryptography. That's pretty much over a year of just cramming math, it's fucking rough.[/quote]
Bummer. The only one I hit on my master's track is Discrete Math.
Pwnzall wrote: [quote]COM wrote: [quote]spyware wrote: If there's one way Esperanto could help the world, it would be assisting in bridging the linguistic divide in matters of science. Agreed, surprising to see someone else who's even heard of it. Shame it didn't take off, but you work with what you get I suppose.[/quote]
I was also intrigued that there are other people who have at least heard of Esperanto. It's got a serious community over at lernu.net though. Ironically enough though, Esperanto itself basing most of its vocabulary/grammar on Romance and Germanic languages puts the rest at a disadvantage. [/quote]
I hear that a lot, but you would be surprised how much languages like Japanese are apparently incorporated into Esperanto. Especially with word building, it's supposed to be very Japanese/Chinese-like.
Does anyone here actually have any speaking familiarity with the language? I'm currently in the process of learning it, but I still have a lot more to cover.
So is this thread about Esperanto or about P=NP?
You don't need a lot of math to understand the P versus NP problem. An undergraduate course about complexity theory should be sufficient. If you're unable to take such a course and you're still interested, there's always Wikipedia: http://en.wikipedia.org/wiki/P_versus_NP_problem and http://en.wikipedia.org/wiki/Time_complexity
Anyway, I think P!=NP. It just doesn't feel credible that a polynomial solution can be found for a NP-complete problem like the Hamiltonian path problem. On the other hand, I find it also hard to believe that no such solution exists for the circuit satisfiability problem, which is also NP-complete. Especially sinds 'easy' solutions can already be found for some cases. It certainly is an interesting discussion that is unlikely to be put to an end very soon. I actually doubt that a formal proof even exists.
On a side node, I thought Esperanto was pretty well-known?
Just to confirm what GTADark said, grasping the basics behind P ?= NP does not require any fancy math or advanced computer science courses.
The basics behind the question are the following. You have a class of problem called NP (nondeterministic polynomial time) such that for a problem to be in NP it needs to be verifiable in polynomial time given a certificate. This simply means that given a solution (certificate) to a problem you can verify whether it's correct or not using a polynomial time algorithm. Most "natural"/interesting problems fall within NP.
Now, within NP there are two important subclasses, P and NP-complete. For a problem to be in P, it needs to be solvable using a polynomial time algorithm. NP-complete problems can be thought of as the hardest possible problems that fall within the NP class.
The ability (or maybe reasonableness) to ask the question whether NP = P comes from an important theorem called the Cook-Levin Theorem. Said theorem leads to the conclusion that any NP-complete problem can be reduced (transformed) into any other NP-Complete problem in polynomial time. Connecting the dots, this means that if we figure out a single solution of an NP-complete problem in polynomial time, we can reduce every other NP-complete problem to said problem in polynomial time (adding polynomial time on top of polynomial time algorithm is still polynomial time) resulting in NP-complete to be equal to P! But NP-complete problems are the hardest problems in NP and if they are equal to P then NP=P.
A solution to this problem either way will be immensely exciting. If NP=P, we will be able to solve most problems a lot quicker and a lot more efficiently. Yes that would include some of our encryption schemes but there are (I believe) encryption schemes that rely on algorithms outside of NP (and if they currently are not developed enough for practical use, they'll obviously get a lot more attention).
If, however, NP != P, then it would seem proving that statement might require a brand new proof-technique. Something as basic as math induction has helped us prove many things. I see no reason why a much more advanced proving method might not exist which has yet to be discovered. Of course this is just speculation on my part.
Hope the above makes sense.
Also, yay first post!
nqe wrote: If NP=P, we will be able to solve most problems a lot quicker and a lot more efficiently I do not see why proving that something exists means that we know how to get to it/do it. Unless the proof itself is a method of solution that proves the statement by working for exactly everything, then it isn't necessarily the case; it'd merely mean that we at least have a chance.
COM wrote: [quote]nqe wrote: If NP=P, we will be able to solve most problems a lot quicker and a lot more efficiently I do not see why proving that something exists means that we know how to get to it/do it. Unless the proof itself is a method of solution that proves the statement by working for exactly everything, then it isn't necessarily the case; it'd merely mean that we at least have a chance.[/quote]
OK. It is not quite that. It is if a problem can be verified in polynomial time can also be solved (reversed) in polynomial time while knowing the whole process of how it is made. I don't see how this would help cryptography. We can assume that P=NP and try to solve some problems in polynomial time (without proving that P=NP) and it seems that we aren't able to do that for most problems, so even if we did prove that P=NP, we aren't clever enough to create a solution that solves those problems in polynomial time. I hope this isn't too confusing.
Actually, a proof for P=NP would indeed give us a recipe to solve NP problems in polynomial time. To prove that two sets are equal, you have to prove that any problem in P is in NP (which is true by definition), and that any problem in NP is also in P. To prove the latter, a NP-complete problem should be reduced to a problem in P. If people manage to do that, any NP problem can be reduced to a problem in P, proving that P=NP. These reductions are also done in polynomial time, which gives us a completely polynomial algorithm.
For example, this would indeed be great news for cryptanalysts. In most cryptographic systems, calculating the answer takes exponential time, whereas verifying an answer can be done in polynomial time. If P=NP, this NP problem can be polynomially reduced to a NP-complete problem, which can be polynomially reduced to a P problem, which has a polynomial solution. Thus we suddenly have a fully polynomially solution, which pretty much breaks the crypto system. (In theory. Of course n^100 is still quite undoable.)
OK, but I think that P doesn't equal NP. Whatever, I could be wrong, who cares. Anyways if P=NP then I don't think we would be able to prove it, I can only think of ways to disprove it (but not being able to disprove it (only thinking in that direction)). The reduction of a NP problem to a P problem is very hard. We haven't been able to do it with a single problem, thus trying to prove it is a little optimistic…
It looks like all NP problems include randomness. So if a NP problem contains random numbers, unknown values or unknown algorithms for making a problem, it means that that problem uses no known logical approach to making that problem, therefore it cannot be reversed. If you want to solve the problem you will have to a) Solve it by bruteforcing or probability, because it contains random values. (Time increases exponentially) b) It has unknown values which have to be bruteforced. (Time increases exponentially) c) It has unknown algorithms. Then you need many input/output values so that you can recreate the algorithm. (Since algorithms are created by humans the ones used are random, making the time exponential to the complexity of the algorithm)
So now every NP problem that has: a) Random values in the problem b) Unknown values like the seed used for generating a number c) Unknown algorithm for the creation process of the problem
Can't be reduced to a P problem.
??? There is a 99.999999999999999999999999999999999999999999999999999999999999999% chance that i am wrong so please help me understand where my mistake is. ???
Mtutnid wrote: Anyways if P=NP then I don't think we would be able to prove it, I can only think of ways to disprove it (but not being able to disprove it (only thinking in that direction)). The reduction of a NP problem to a P problem is very hard. We haven't been able to do it with a single problem, thus trying to prove it is a little optimistic…
The opposite is in fact correct. As I mentioned in my previous post, the Levin-Cook theorem basically states that if any single NP-complete problem (and there are hundreds well known such problems) was somehow solved in polynomial time, then every other problem would also be solvable in polynomial time, hence NP-complete = P = NP. This is why this problem is said to be approachable by amateur computer scientists - it only requires the creation of a single algorithm to prove a phenomenal statement.
Now, to disprove it, it's not at all clear what needs to be done. One way to think of it is that you need to show that the infinite space of algorithms (that is, any possible algorithm) is unable to solve NP-complete in polynomial time. Anyone who's done proofs knows that proving a statement by counter-example is normally much easier than a well constructed proof.
As for cryptography, I'm not sure what it means to "help it". NP=P would cause problems with our current encryptions, but does that help or hurt cryptography?
nqe wrote: As for cryptography, I'm not sure what it means to "help it". NP=P would cause problems with our current encryptions, but does that help or hurt cryptography? Partially. All of the popular encryption systems that are currently in use, that depend on concepts such as prime factorization, elliptic curves or the discrete log problem, would be broken in theory and should be replaced. However, only because polynomial algorithms are generally considered 'feasible'. This is debatable. The grade of the polynomial describing the time complexity of the solution algorithm would become very important. On the other hand, an encryption system in EXPTIME is quite undesirable. This would mean it could take months to verify an answer, which just doesn't make any sense for stuff like SSL or smart card authentication.