Hacker News Reader

It's actually pretty easy to construct hard problems. A random 3-SAT problem is hard when it has the right density ratio of clauses to Boolean variables. Too few, and it's (relatively) easy to find a satisfying assignment. Too many, and it's easy to find a contradiction. This ratio is around 4.26, and it can actually be viewed as "thermodynamic" phase transition. In the large n limit, almost all 3-sat problems with a lower ratio are solvable, and almost all above that are not.

I'd be interested to see a reference for that result. I've been working for some time on the equivalent problem for graph 3-coloring, and really there are only some vague, heuristic results. I should think it also depends on the randomness model you use. In graph coloring some random processes give easy problems and others give hard problems for the same density.

Which randomness models in particular? The two Erdős–Rényi models G(n,p) vs G(n, M)? I thought for almost all purposes they gave the same answer as long as equivalent M and p were chosen in the large n limit, because the concentration around M will be so tight due to the law of large numbers. Is there some other model you're looking at?

Random without qualification is used to mean "uniformly". For this specific case (3-SAT), there are only four reasonable readings: both (variables within a clause), and (clauses within the set of all possible clauses) can be chosen with or without replacement. Neither makes a difference in the large n limit.

http://books.google.com/books?id=zyktZTqZSzMC&lpg=PA414&...

is from a reasonable book.

It's true that this phenomenon hasn't been completely rigorously proven, but it's been given "physicist proofs". There's enough evidence that it's unreasonable to not consider it true.

My sense is that there are hard 3-coloring problems in graphs that don't look "random". Certainly the ones I generate have a small number of vertices with very high degree, and the others are more reasonable. This is why I say that there are potentially things happening with different random models. But you are certainly right on all counts.

However, where you say this:

    .... it's been given "physicist proofs". There's enough
    evidence that it's unreasonable to not consider it true.

There had been a lot of evidence around for quite some time that primality was harder than P (assuming P!=NP), and yet it turns out to be in P, even without PvsNP being settled. I'm suspicious. I still believe that hard instances can be found, and that "most" of them will look as you describe, random-ish with the right parameters, but I'm wary about claiming that most things that look like that will, in turn, be "hard."

But I suspect we're in agreement, possibly "violent agreement."

ADDED In EDIT: Forgot to say, thanks for the reference.

Yes, we are in violent agreement then.

Easy to generate random hard instances does not at all mean that highly structured "non-random" instances can't be hard. The "phase transition" only means that the fraction that are hard at a given non-critical ratio decreases with n, but there very well could be a large absolute number, that increases with n. The space of problems of size n grows exponentially, after all.

My sense is that even before AKS, most researchers believed primality was in P. This was based mainly on poly-time probablistic algorithms developed in the 80's.

Here's a Nature article that's pretty readable

http://www.cs.cornell.edu/selman/papers/pdf/99.nature.phase....

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.

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

Apparently it wasn't considered dead enough early enough: http://www.win.tue.nl/hashclash/rogue-ca/

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

The issue of whether it's a feasible amount of work is exactly what I was addressing.

One of the reasons this would be a huge result is that even a very expensive polynomial-time solution for any NP-complete problem (say, one which is O(n^2000) and would take several billion years to run against a 256-bit key) is only going to get faster over time. Also, the experience of cryptography is that once cracks start appearing in an algorithm the mathematicians start trying to wedge their chisels in and hammer those cracks into fractures, into holes, and eventually into whatever you call something which no longer resembles a crack so much it resembles absence-of-wall.

There are specific mechanisms by which this would happen, too. A near miss on P=NP would mean funding for professors looking into refining it, and professional interest generally, would suddenly explode. Nobody wants to fund or work on duds, but big contributions to this problem would make careers.

Not incidentally, while the government funds quite a bit of academic research, this particular branch of mathematics is of special interest to one type of government customer which has ways of getting funding for projects expedited if they are in the national interest... and it is virtually inconceivable that they would not find very, very strong national interest in the vicinity of this result.

True. However I don't think the article really implies that P = NP (although the title certainly does). From what I can see the article only addresses the class of NP-complete problems. Factoring is not known or believed to be NP-complete so it wouldn't directly prove that factoring was in P. Please correct me if I'm wrong.

Edit : For some reason I can't reply to posts so I'll do it here.

RiderOfGiraffes> It would will leave in question those problems in NP, but not NPC. Currently it is generally believed, but not known, that factoring is such a problem.

This is exactly my point. P = NPC doesn't imply anything about factorisation. Since factorisation is in NP we haven't shown that P = NP

kd0amg> NP-complete problems ... are, in essence, the hardest problems in class NP.

From what I understand they a 'thought to be' the toughest but this isn't proven. If this article turned out to be true then they are reduced to being as hard as P. So who is still standing as a contender for the hardest problem in NP? - factorization of course as it has never been demonstrated to be polynomially reducible to NPC.

I believe you to be mistaken. Let me explain.

Proving that any single NPC problem is in P will be enough to prove that every NP problem is in P, and not just the NPC ones. Suppose A is is NP, B is in NPC, and further suppose that solving B is polynomial. Reduce A to B (a polynomial operation because B is in NPC), solve B (a polynomial operation by assumption), and convert the solution back to a solution of A (a polynomial operation because B is in NPC), and that gives a polynomial solution of A.

Proving that any single NPC problem is not in P is enough to prove that all NPC problems are not in P. It would will leave in question those problems in NP, but not NPC. Currently it is generally believed, but not known, that factoring is such a problem.

Added in edit, to reply to your edit:

    RoG> It would will leave in question those problems
    RoG> in NP, but not NPC. Currently it is generally 
    RoG> believed, but not known, that factoring is such
    RoG> a problem.

    dejb> This is exactly my point. P = NPC doesn't imply
    dejb> anything about factorisation. Since factorisation
    dejb> is in NP we haven't shown that P = NP

Read my entire comment again. In particular, the second paragraph. In particular:

    Proving that any single NPC problem is in P will be
    enough to prove that every NP problem is in P.

More specifically, proving 3-SAT is in P will prove that every NP problem, not just the NPC problems, but every NP problem, is in P. Including factoring.

Let me add a little more.

   1. Suppose 3-SAT is in P.
   2. Let A be any problem in NP.
   3. 3-SAT is in NPC.
   4. Therefore A can be converted to A', an instance of 3-SAT.
   5. By (1), A', as an instance of 3-SAT, can be solved in polynomial time
   6. Hence A has been solved in polynomial time.

Replace "A" with factoring, and thus we've shown that P=NPC implies that factorisation is in P.

Can you supply a link to the proof that all NPC problems are equivalent? I remember learning it, but I can't remember how it worked.

This in the definition of NPC. What you have to prove is that a language is in NPC.

This was proved for SAT first: http://en.wikipedia.org/wiki/Cook%E2%80%93Levin_theorem

http://en.wikipedia.org/wiki/NP_complete

By definition, a problem P is NPC if:

a. P is in NP, and

b. Every problem in NP can be converted to an instance of P.

Consider any two problems in NPC, P and Q. Then each is in NP, and each can be converted to the other. They are therefore equivalent.

QED.

The NP-complete problems are a subset of NP ("nondeterministic polynomial") problems, specifically those to which all NP problems are polynomial-time reducible. They are, in essence, the hardest problems in class NP. It's pretty trivial to show that integer factoring is in NP; what's not known is whether it's NP-complete. If any NP-complete problem is in P, then via polynomial-time reduction, all problems in NP are in P.

factorization of course as it has never been demonstrated to be polynomially reducible to NPC.

Every NP problem is polynomial-time reducible to SAT. I do not recall the title of the paper off the top of my head, but it has been proven that the definition of an NP problem (a question that can be answered given some additional piece of information, a "certificate") is polynomial-time reducible to SAT.

The methodology was basically an algorithm taking as input a description of such a solution, and producing a boolean expression on the certificate and some other values needed to maintain integrity. The expression is satisfiable if and only if the answer is affirmative.

The reason that factorization is not known to be NP-complete is that the reverse is not known. That is, no NP-complete problem is known to be polynomial-time reducible to factorization.

From what I understand they a 'thought to be' the toughest but this isn't proven.

Yes, it is. Any NP problem can be many-one reduced to SAT, which means that there's a function that transforms an instance of the NP problem to an instance of SAT, and the answer to whether that formula is satisfiable is the same as whether that instance is a member of the NP problem (in its decision version).

So who is still standing as a contender for the hardest problem in NP?

If P = NP, then all problems in NP are as easy as each other, so this question is meaningless.

To be pedantic, not all problems in P are equally hard. Sorting for example is harder than finding the median.

The provable lower bound for the worst-case performance of searching is O(n log n). Finding the median takes linear time i.e. O(n).

Sorting and finding a median reduce to each other polynomially, of course.

Interesting subsets of polynamial problems are e.g. linear problems, or highly parallelizeable problems whose runtime tends to O(log n) as the number of processors tends to infinity. Adding a list of numbers is not only linear but also highly parallelizeable. Proving a problem to be not parallelizeable like that, is also interesting.

There's also the question whether randomness helps. It does in practice, but we don't know whether access to random bits helps in theory.

By "as easy as each other" I meant reducible to each other with a polynomial factor, as is standard in complexity theory.

Yes, that why I prefaced with "To be pedantic". I just felt like pointing out that there are meaningful differences between polynomial problems.

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

Actually, 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.

Cperciva 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).

You're right. I've got the brain hiccups.

> Also, there are problems in NP that are neither in P, nor are they NP- or co-NP-complete.

Err, it seems to me you've got a very serious statement there. I think you mean “that are not known to be …”.

No, there actually are problems in "NP-intermediate" class (if P!=NP) although they are artificial. :) And, of course you are right, for many other problems researchers suspect they might be in NPI. See http://cstheory.stackexchange.com/questions/79/problems-betw...

It's been proven that if P != NP, then there are problems in NP, which are neither in P nor NP-complete. We don't know what those problems are, because identifying such a problem would prove P != NP. There are candidates, such as factoring, for which there are neither polynomial algorithms nor proofs of NP-completeness, but definitively identifying them is at least as hard as proving P != NP, and possibly harder.

Yep. I should just stop posting today. :)

The point I was trying to make (badly) was that the actual claim doesn't imply P = NP, only that P = NP-complete. Given that factoring isn't known to be NP-complete (or co-NP-complete) this paper doesn't imply that factoring is in P.

If a single NP-Complete problem is in P, then P=NP. This is what NP-Complete means. In particular, factoring would be in P. Conversely, factoring is not NP-complete, so if factoring were in P, we could not draw any conclusions about P=?NP.

Actually, 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.

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

OTOH, 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).

Don'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.

Thanks for the summary with your level of competence (already a good one ;)).

Colin, no offense, and you are certainly a good coder & cryptographer, but that doesn't make know about everything in mathematics.

Err, what? I won the Putnam, but that's a mathematics competition, not a computational complexity competition.

Edit: If the above comment doesn't make sense, it's because the comment I was replying to was "you won the Neumann" and has since been edited.