5 ms·

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

by wnoise 16y ago

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.

RiderOfGiraffes 16y ago
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.
- wnoise 16y ago
  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&ots=4oUiYVSx92&dq=3-SAT%20critical%20density&pg=PA414#v=onepage&q=3-SAT%20critical%20density&f=false 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.
  - RiderOfGiraffes 16y ago
    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.
    - wnoise 16y ago
      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.
    - edenh 16y ago
      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.
- sbt 16y ago
  Here's a Nature article that's pretty readable http://www.cs.cornell.edu/selman/papers/pdf/99.nature.phase.pdf http://www.cs.cornell.edu/selman/papers/pdf/99.nature.phase....

by wnoise 16y ago

RiderOfGiraffes 16y ago

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.

wnoise 16y ago
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&ots=4oUiYVSx92&dq=3-SAT%20critical%20density&pg=PA414#v=onepage&q=3-SAT%20critical%20density&f=false 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.
- RiderOfGiraffes 16y ago
  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.
  - wnoise 16y ago
    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.
  - edenh 16y ago
    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.
sbt 16y ago
Here's a Nature article that's pretty readable http://www.cs.cornell.edu/selman/papers/pdf/99.nature.phase.pdf http://www.cs.cornell.edu/selman/papers/pdf/99.nature.phase....