5 ms·
To pick on a small part of your comment: Do any theoretical computer scientists seriously worry that a proof that P=NP would threaten cryptography? It's not lik
by tshaddox 16y ago
To pick on a small part of your comment: Do any theoretical computer scientists seriously worry that a proof that P=NP would threaten cryptography? It's not like a proof would suddenly make an i7 able to factor huge numbers in polynomial time. Also, while all polynomial-time algorithms are considered "tractable" in theoretical CS, that doesn't mean that they're all practical on current hardware (nor does it claim to mean that).
I suppose a proof that P=NP would still technically threaten cryptography, because if you assume that computer hardware performance increases polynomially with time you must concede that any given crypto technique will become practical to break after some amount of time.
- jchonphoenix 16y agoActually, yes. Normally, when something is placed firmly in P, improvements are quickly made and a spur of research firmly lowers the bounds of the algorithm. Additionally, P=NP suggests that NP in RP. If an inefficient deterministic algorithm in P is found, I'm sure a much faster randomized algorithm would soon follow.
- _delirium 16y ago> Normally, when something is placed firmly in P, improvements are quickly made and a spur of research firmly lowers the bounds of the algorithm. This hasn't been the case in linear programming, at least: 30 years after it was proven to be in P, the old exponential algorithm (the simplex method) is still competitive with the best known polynomial algorithms (interior point methods). From a practical perspective, no real efficiency breakthrough. The fact that there are now two families of algorithms with good performance for the problem is an improvement, but the fact that one of them is theoretically polynomial doesn't seem to have led to dramatic speed gains.
- mzl 16y agoOTOH, simplex is very efficient already. Average-case complexity for random matrices is polynomial, and there are some interesting results that extend beyond that (see http://arxiv.org/abs/cs/0111050 http://arxiv.org/abs/cs/0111050).
- cperciva 16y agoFactoring is in NP. Proving that P=NP would, by definition, imply that large numbers can be factored in polynomial time. The issue of whether it's a feasible amount of work is exactly what I was addressing.
- dejb 16y agoSpeaking pedantically, P is in NP also. I suspect that NP is being used as shorthand for NP-complete, not just NP. As for actual deterministic factorization Wikipedia says that 'It is suspected to be outside of all three of the complexity classes P, NP-complete, and co-NP-complete' So even if this showed 'P = NP-complete' it may not imply imply factorization is in P. I'm at the limits of my rusty complexity knowledge here so if any knows better please correct me.
- bdr 16y agoActually, cperciva is right here. Factoring is in NP, therefore if P=NP then there is a polynomial-time algorithm for factoring. Many problems harder than NP are NP-complete, so saying factoring is in NP-complete would not imply the conclusion. Also, there are problems in NP that are neither in P, nor are they NP- or co-NP-complete.
- sonoffett 16y agoCperciva is right, but I think you're mistaken when you say "many problems harder than NP are NP complete", NP complete problems are both NP and NP hard. NP hard is a class of problems such that every problem in NP can be reduced to any problem in NP hard. Meaning if P=NP then every problem in NP(including the NP complete problems) can be solved in polynomial time; all it takes is one algorithm that solves an NP complete problem in polynomial time (note that this does not show that P=NP hard, a much stronger claim).
- bdr 16y agoYou're right. I've got the brain hiccups.
- endtime 16y ago>Do any theoretical computer scientists seriously worry that a proof that P=NP would threaten cryptography? Yeah, that's how crypto works as a field. As soon as there's a shadow of a doubt that something is secure in even the least likely edge case, it gets tossed out. MD5 was basically considered dead once someone showed to how create a collision with (correct me if I'm wrong) two very long, very unlikely, very similar (?) plaintexts. It didn't threaten anyone's actual use of MD5 in an immediate sense, but MD5 was shown not to be reliable and in the crypto world an algorithm's reliability is sort of treated as binary. (I apologize to the true security folk in the crowd if I've oversimplified something here.)
- jix 16y agoApparently it wasn't considered dead enough early enough: http://www.win.tue.nl/hashclash/rogue-ca/ http://www.win.tue.nl/hashclash/rogue-ca/
- ZachPruckowski 16y agoDon't forget that changing out algorithms is a time-consuming process. It's not a 10 second fix, it's a technical challenge and a bureaucratic nightmare. I mean, it takes a week's worth of meetings to restock the condiments in the mess hall in some of these places. So you wind up in a situation where it takes a year or more to implement this stuff once you have the ideal solution selected, and selecting the replacement solution takes another year or more. So even if it's not projected to be an issue for 5 years, you have to start the replacement process right away.