Re: Could P = NP be true?
tc...@lsa.umich.edu
RussellE <reas...@gmail.com> wrote:
>Assume I create every 3SAT instance with 10 variables and
>run all of them through a commercial SAT solver.
>I find the hardest instance required 293,142 steps.
>Would this prove P=NP because the worst case
>instance required O(10^5) steps?
That question is not even wrong.
I don't know if Joshua Cranmer is still tracking this thread, but if you
are, what do you think of Russell's understanding of P = NP versus Phil's
understanding, given what Russell says here?
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
tc...@lsa.umich.edu
RussellE <reas...@gmail.com> wrote:
>If my algorithm is O(n^10), there is a big difference between
>307^10 and 4096^10. Of course, I can always hope the
>computers keep getting faster.
>
>
>Russell
>- 2 many 2 count
"2 many 2 count" must refer to the number of your non sequiturs.
RussellE
> In article <bde98507-fb9f-4a37-8d0f-7d95aa57e...@u16g2000pru.googlegroups.com>,
>
> RussellE <reaste...@gmail.com> wrote:
> >Assume I create every 3SAT instance with 10 variables and
> >run all of them through a commercial SAT solver.
> >I find the hardest instance required 293,142 steps.
> >Would this prove P=NP because the worst case
> >instance required O(10^5) steps?
>
> That question is not even wrong.
The OP asked why I put "polynomial" in quotes.
Assume I have a solver that simply tries every
possible assignment.
This algorithm solves any 10 variable instance
in, at most, 1024 steps or O(n^4).
It solves any 11 variable instance in O(n^4) steps.
In fact, for any fixed number of variables, my
algorithm solves any instance with that many
variables in "polynomial" time.
Of course, the "polynomial" grows as the
number of variables grows. Even so,
this simple algorithm proves P=NP for
any fixed number of variables.
Joshua Cranmer
> I don't know if Joshua Cranmer is still tracking this thread, but if you
> are, what do you think of Russell's understanding of P = NP versus Phil's
> understanding, given what Russell says here?
I said 'perhaps.' I tend not to dwell too much in this newsgroup, so I
have a very poor sense of recurring posters. Extrapolation is always
fraught with problems.
--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth
tc...@lsa.umich.edu
RussellE <reas...@gmail.com> wrote:
>this simple algorithm proves P=NP for
>any fixed number of variables.
And that answer is not even wrong.
RussellE
> In article <2989ba22-9721-4cfd-82de-30dd4dd2f...@x25g2000prf.googlegroups.com>,
>
> RussellE <reaste...@gmail.com> wrote:
> >this simple algorithm proves P=NP for
> >any fixed number of variables.
>
> And that answer is not even wrong.
The original poster asked if there was any evidence
P = NP might be true. I know most people
think P =/= NP. I am not one of those people.
I won't be too surprised if someone does prove
P =/= NP, but history is full examples where
most people were wrong about some proof.
Reasons P = NP might be true:
1) We can prove P=NP for any fixed number
of variables.
2) Some classes of NP problems, like 2SAT
and Horn clauses, have polynomial algorithms.
3) We can pretty much prove P=NP for
AVERAGE case complexity.
The best upper bounds we currently have
on complexity may be exponential,
but they are still quite low.
It would be nice if we could find a
polynomial bound, but a proof of P=NP
might not give us much of an improvement
over existing methods.
Theorist are always interested in worst case.
The people that actually use this stuff are
usually more interested in average case.
(except cryptographers).
Right at the moment, I think the speed of
our computers is more of a limiting factor
on the size of problems we can solve than
the lack of "good" algorithms.
Patricia Shanahan
> On Dec 18, 7:50 pm, tc...@lsa.umich.edu wrote:
>> In article <2989ba22-9721-4cfd-82de-30dd4dd2f...@x25g2000prf.googlegroups.com>,
>>
>> RussellE <reaste...@gmail.com> wrote:
>>> this simple algorithm proves P=NP for
>>> any fixed number of variables.
>> And that answer is not even wrong.
>
> The original poster asked if there was any evidence
> P = NP might be true. I know most people
> think P =/= NP. I am not one of those people.
> I won't be too surprised if someone does prove
> P =/= NP, but history is full examples where
> most people were wrong about some proof.
>
> Reasons P = NP might be true:
>
> 1) We can prove P=NP for any fixed number
> of variables.
I have a lot of trouble with understanding what you mean by this.
Many problems in NP do not involve variables at all. You cannot depend
on the normal proof that SAT is NP-complete because it depends on the
lack of an upper bound on the number of variables in a SAT instance.
> 2) Some classes of NP problems, like 2SAT
> and Horn clauses, have polynomial algorithms.
P is definitely a non-empty subset of NP. That seems equally consistent
with "P is a non-empty proper subset of NP" and "P is equal to NP".
Patricia
tc...@lsa.umich.edu
No, we can't. It's a little tricky to define average-case complexity
correctly, because one has to specify a probability distribution over
instances. However, people have figured out the right definitions and
proved that there exist complete problems.
http://www-cse.ucsd.edu/~russell/average.ps
The complete problems are unsatisfactory, however, in that they are not
very "natural." It remains a major open problem to prove the completeness
of any "natural" problem with a "natural" probability distribution.
And of course, whether the complete problems can be solved in polynomial
time on average remains wide open.
Note, of course, that by carefully constructing a probability distribution
that avoids all the "hard" instances, we can easily contrive to solve an
NP-complete problem quickly on average. But this doesn't prove that *all*
NP problems with arbitrary (non-contrived) probability distributions can
be solved quickly on average, which is what "P = NP for average-case
complexity" means.
>The best upper bounds we currently have
>on complexity may be exponential,
>but they are still quite low.
>It would be nice if we could find a
>polynomial bound
It would be nice if we could find any *subexponential* bound for SAT, e.g.,
2^(sqrt(n)).
Tim Little
> Assume I create every 3SAT instance with 10 variables and run all of
> them through a commercial SAT solver. I find the hardest instance
> required 293,142 steps. Would this prove P=NP because the worst
> case instance required O(10^5) steps?
No, and if you had the slightest clue what you were talking about you
wouldn't need to ask.
- Tim
Tim Little
>
> 1) We can prove P=NP for any fixed number of variables.
That is not correct; it is not even wrong. It makes no sense.
> 2) Some classes of NP problems, like 2SAT and Horn clauses, have
> polynomial algorithms.
Again, showing you have no clue what P=NP means. All problems in P
are in NP, by definition. Showing that P is not empty is not any sort
of evidence that P=NP!
> 3) We can pretty much prove P=NP for AVERAGE case complexity.
No, we cannot. For example, consider the problem of factoring
semiprimes. Is there an algorithm with average polynomial running
time?
(Technically the P=NP question concerns decision problems. To be
pickier, consider the decision problem of whether a semiprime S has a
factor less than k for k^2 <= S)
- Tim
cplxphil
Most people seem to think that P = NP is almost certainly false. I
was wondering about a possible scenario where P = NP might be true.
Generally speaking, it seems that in order to prove that a decision
problem belongs to a certain complexity class, one has to find an
algorithm to solve it. For example, I would imagine it would be
difficult to prove that the shortest path problem can be solved in
polynomial time without demonstrating an algorithm (or the equivalent,
such as a query) to solve it.
What if P = NP is true, but every algorithm that solves an NP-
complete in polynomial time is a) really bad (e.g., O(n^1000000000)
or something), and b) impossible to prove correct--that is, for every
machine M that decides SAT in polynomial time, there does not exist a
proof that M solves SAT in polynomial time?
Then, the reason that P = NP is so hard to resolve would be not that
there are diagonalization and natural proof barriers to proving it
false, but rather that there is a barrier to proving it true.
Does this seem plausible?
-Phil
(I am aware of the multi-tasking algorithm that provably accepts SAT
iff P = NP, but I don't think it's definitely possible to prove that
any algorithm actually *decides* SAT without proving that ZFC is
consistent, which cannot be done.)
tc...@lsa.umich.edu
cplxphil <cplx...@gmail.com> wrote:
>Then, the reason that P = NP is so hard to resolve would be not that
>there are diagonalization and natural proof barriers to proving it
>false, but rather that there is a barrier to proving it true.
>
>Does this seem plausible?
Possible, yes. Plausible, not so much.
By the way, there do exist cases where we know that a polynomial-time
algorithm exists but have not exhibited an algorithm. The most notable
examples come from graph minor theory. From Robertson and Seymour's
graph minor theorem, plus the fact that testing for the presence of a
given minor is solvable in polynomial time, we know that any hereditary
graph property is checkable in polynomial time. But to exhibit the
algorithm, we have to exhibit the finite list of forbidden minors, and
there is no general method of computing that list.
cplxphil
> In article <e3f7a638-85cd-4cca-bc16-30aacb3a6...@j14g2000yqm.googlegroups.com>,
>
> cplxphil <cplxp...@gmail.com> wrote:
> >Then, the reason that P = NP is so hard to resolve would be not that
> >there are diagonalization and natural proof barriers to proving it
> >false, but rather that there is a barrier to proving it true.
>
> >Does this seem plausible?
>
> Possible, yes. Plausible, not so much.
Why not?
>
> By the way, there do exist cases where we know that a polynomial-time
> algorithm exists but have not exhibited an algorithm. The most notable
> examples come from graph minor theory. From Robertson and Seymour's
> graph minor theorem, plus the fact that testing for the presence of a
> given minor is solvable in polynomial time, we know that any hereditary
> graph property is checkable in polynomial time. But to exhibit the
> algorithm, we have to exhibit the finite list of forbidden minors, and
> there is no general method of computing that list.
That is interesting, I'll look into that. Thanks.
-Phil
Casey Hawthorne
<cplx...@gmail.com> wrote:
>
>Most people seem to think that P = NP is almost certainly false. I
>was wondering about a possible scenario where P = NP might be true.
>
>Generally speaking, it seems that in order to prove that a decision
>problem belongs to a certain complexity class, one has to find an
>algorithm to solve it. For example, I would imagine it would be
>difficult to prove that the shortest path problem can be solved in
>polynomial time without demonstrating an algorithm (or the equivalent,
>such as a query) to solve it.
>
>What if P = NP is true, but every algorithm that solves an NP-
>complete in polynomial time is a) really bad (e.g., O(n^1000000000)
>or something), and b) impossible to prove correct--that is, for every
>machine M that decides SAT in polynomial time, there does not exist a
>proof that M solves SAT in polynomial time?
>
>Then, the reason that P = NP is so hard to resolve would be not that
>there are diagonalization and natural proof barriers to proving it
>false, but rather that there is a barrier to proving it true.
>
>Does this seem plausible?
>
>-Phil
>
There is a major gap between computabiltiy theory and complexity
theory. We have a good grasp of the separation between what is and
what is not computable; however, for complexity theory, we are missing
provable good lower bounds on the NP problem class.
>(I am aware of the multi-tasking algorithm that provably accepts SAT
>iff P = NP, but I don't think it's definitely possible to prove that
>any algorithm actually *decides* SAT without proving that ZFC is
>consistent, which cannot be done.)
--
Regards,
Casey
tc...@lsa.umich.edu
cplxphil <cplx...@gmail.com> wrote:
>On Dec 14, 12:51�pm, tc...@lsa.umich.edu wrote:
>> In article
>> <e3f7a638-85cd-4cca-bc16-30aacb3a6...@j14g2000yqm.googlegroups.com>,
>>
>> cplxphil �<cplxp...@gmail.com> wrote:
>> >Then, the reason that P = NP is so hard to resolve would be not that
>> >there are diagonalization and natural proof barriers to proving it
>> >false, but rather that there is a barrier to proving it true.
>>
>> >Does this seem plausible?
>>
>> Possible, yes. �Plausible, not so much.
>
>Why not?
For me to label something "plausible," I need some positive evidence in that
direction. I see very little positive evidence that P = NP. Furthermore,
I see no positive evidence that P = NP is unprovable. I often see people
confusing the *psychological difficulty* of resolving a mathematical question
with the *logical strength* of the axiomatic system needed to resolve it.
There is plenty of evidence that P = NP is a challenging problem for human
minds, but I do not regard this as evidence that the logical strength of the
axiomatic system needed to resolve P = NP is high.
RussellE
> In article <8bec1657-039e-4c80-b153-a025e0182...@v30g2000yqm.googlegroups.com>,
>
> cplxphil <cplxp...@gmail.com> wrote:
> >On Dec 14, 12:51 pm, tc...@lsa.umich.edu wrote:
> >> In article
> >> <e3f7a638-85cd-4cca-bc16-30aacb3a6...@j14g2000yqm.googlegroups.com>,
>
> >> cplxphil <cplxp...@gmail.com> wrote:
> >> >Then, the reason that P = NP is so hard to resolve would be not that
> >> >there are diagonalization and natural proof barriers to proving it
> >> >false, but rather that there is a barrier to proving it true.
>
> >> >Does this seem plausible?
>
> >> Possible, yes. Plausible, not so much.
>
> >Why not?
>
> For me to label something "plausible," I need some positive evidence in that
> direction. I see very little positive evidence that P = NP.
I think there is a lot of positive evidence that P = NP might be true.
Many NP problems, like 2SAT, have known polynomial algorithms.
Even most NP-Complete instances, like 3SAT, can be solved in polytime.
Most solvable 3SAT instances can be solved in polytime by a random
guessing algorithm. Only a small class of 3SAT instances are "hard".
If all NP-Complete problems were "hard", we wouldn't have commercial
SAT solvers.
Last, but not least, no one has proven P =/= NP.
So far, I see no reason why P = NP can't be true.
tc...@lsa.umich.edu
RussellE <reas...@gmail.com> wrote:
>I think there is a lot of positive evidence that P = NP might be true.
I'm afraid I don't find your arguments convincing.
>Many NP problems, like 2SAT, have known polynomial algorithms.
Many problems in EXPTIME, like 2SAT, have known polynomial algorithms.
>Even most NP-Complete instances, like 3SAT, can be solved in polytime.
>Most solvable 3SAT instances can be solved in polytime by a random
>guessing algorithm. Only a small class of 3SAT instances are "hard".
Average-case complexity doesn't say much about worst-case complexity,
which is what the P = NP question is about.
>If all NP-Complete problems were "hard", we wouldn't have commercial
>SAT solvers.
That's absurd. If a problem is hard but important, then people will do the
best they can. Perhaps you just mean that if all NP-complete problems were
hard on average then commercial SAT solvers would do poorly all the time.
That might be true, but it's irrelevant to the question of worst-case
complexity.
>Last, but not least, no one has proven P =/= NP.
True enough. But nobody has proven P = NP either, so I don't see this fact
as positive evidence for either direction.
>So far, I see no reason why P = NP can't be true.
Neither can I. That wasn't the question. The question was not whether
P = NP *could* be true, but whether there was any *positive evidence* for
it. You haven't presented any.
RussellE
> In article <0a2491d0-d80f-49fa-98f2-f4fcd152a...@e4g2000prn.googlegroups.com>,
>
> RussellE <reaste...@gmail.com> wrote:
> >I think there is a lot of positive evidence that P = NP might be true.
>
> I'm afraid I don't find your arguments convincing.
>
> >Many NP problems, like 2SAT, have known polynomial algorithms.
>
> Many problems in EXPTIME, like 2SAT, have known polynomial algorithms.
>
> >Even most NP-Complete instances, like 3SAT, can be solved in polytime.
> >Most solvable 3SAT instances can be solved in polytime by a random
> >guessing algorithm. Only a small class of 3SAT instances are "hard".
>
> Average-case complexity doesn't say much about worst-case complexity,
> which is what the P = NP question is about.
We can't even define "worst case complexity" for 3SAT.
A 3SAT instance that is hard for one solver might be easily solved
by a different solver. We do know that instances with a certain
variable to clause ratio tend to be more difficult, but even this
tells us nothing about how "hard" a specific instance might be.
This inability to even define "worst case" is one reason I
find the P=NP problem interesting.
> >If all NP-Complete problems were "hard", we wouldn't have commercial
> >SAT solvers.
>
> That's absurd. If a problem is hard but important, then people will do the
> best they can.
"The best they can" turns out to be pretty good. Modern SAT solvers
can find satisfying assignments very quickly for most instances.
> Perhaps you just mean that if all NP-complete problems were
> hard on average then commercial SAT solvers would do poorly all the time.
> That might be true, but it's irrelevant to the question of worst-case
> complexity.
I would say we have already proven P=NP for all practical purposes.
Yes, there are "small" 3SAT instance (300 variables) that can't be
solved by modern SAT solvers in a "reasonable" time.
But, such instances are the exception, not the rule. SAT solvers can
and have solved instances with 10,000 variables.
Even the "hard" 300 variable instances can be solved if we are
willing
to wait long enough. Polynomial doesn't necessarily mean efficient.
N^10 is polynomial, but I wouldn't want to wait for a solver to do
300^10
operations.
> >Last, but not least, no one has proven P =/= NP.
>
> True enough. But nobody has proven P = NP either, so I don't see this fact
> as positive evidence for either direction.
I agree. The lack of a proof ether way doesn't tell us much.
And I agree there are reasons to suspect P=/=NP. Like you,
I have read a number of "proofs" of P=/=NP. I even have one myself.
I think I can prove 3SAT can't be converted to 2SAT. Some 3SAT
instances can't even be converted to a polynomial number of 2SAT
instances.
This still doesn't rule out the possibility of finding one satisfying
assignment in polynomial time.
As for positive evidence for P=NP, I would look at the published lower
bounds.
These bounds are already quite low (but still exponential) and new
lower bounds are being published all the time.
cplxphil
> On Dec 16, 6:42 pm, tc...@lsa.umich.edu wrote:
>
>
>
>
>
> > In article <0a2491d0-d80f-49fa-98f2-f4fcd152a...@e4g2000prn.googlegroups.com>,
>
> > RussellE <reaste...@gmail.com> wrote:
> > >I think there is a lot of positive evidence that P = NP might be true.
>
> > I'm afraid I don't find your arguments convincing.
>
> > >Many NP problems, like 2SAT, have known polynomial algorithms.
>
> > Many problems in EXPTIME, like 2SAT, have known polynomial algorithms.
>
> > >Even most NP-Complete instances, like 3SAT, can be solved in polytime.
> > >Most solvable 3SAT instances can be solved in polytime by a random
> > >guessing algorithm. Only a small class of 3SAT instances are "hard".
>
> > Average-case complexity doesn't say much about worst-case complexity,
> > which is what the P = NP question is about.
>
> We can't even define "worst case complexity" for 3SAT.
> A 3SAT instance that is hard for one solver might be easily solved
> by a different solver. We do know that instances with a certain
> variable to clause ratio tend to be more difficult, but even this
> tells us nothing about how "hard" a specific instance might be.
>
> This inability to even define "worst case" is one reason I
> find the P=NP problem interesting.
>
Worst-case complexity is definitely defined. The fact that we don't
know what it is is the reason why P = NP remains unresolved.
> > >If all NP-Complete problems were "hard", we wouldn't have commercial
> > >SAT solvers.
>
> > That's absurd. If a problem is hard but important, then people will do the
> > best they can.
>
> "The best they can" turns out to be pretty good. Modern SAT solvers
> can find satisfying assignments very quickly for most instances.
>
That is irrelevant. The problem is that most of the SAT instances
people really care about--e.g., the ones generated for cryptographic
purposes--cannot be solved. "Most instances" is essentially
meaningless. The P = NP problem is to find a single algorithm that
decides *all* SAT instances in polynomial time.
> > Perhaps you just mean that if all NP-complete problems were
> > hard on average then commercial SAT solvers would do poorly all the time.
> > That might be true, but it's irrelevant to the question of worst-case
> > complexity.
>
> I would say we have already proven P=NP for all practical purposes.
> Yes, there are "small" 3SAT instance (300 variables) that can't be
> solved by modern SAT solvers in a "reasonable" time.
> But, such instances are the exception, not the rule. SAT solvers can
> and have solved instances with 10,000 variables.
>
> Even the "hard" 300 variable instances can be solved if we are
> willing
> to wait long enough. Polynomial doesn't necessarily mean efficient.
...if we are willing to wait long enough? What?
No, polynomial-bounded doesn't necessarily mean efficient; but it does
have a definition.
> N^10 is polynomial, but I wouldn't want to wait for a solver to do
> 300^10
> operations.
>
> > >Last, but not least, no one has proven P =/= NP.
>
> > True enough. But nobody has proven P = NP either, so I don't see this fact
> > as positive evidence for either direction.
>
> I agree. The lack of a proof ether way doesn't tell us much.
> And I agree there are reasons to suspect P=/=NP. Like you,
> I have read a number of "proofs" of P=/=NP. I even have one myself.
> I think I can prove 3SAT can't be converted to 2SAT. Some 3SAT
> instances can't even be converted to a polynomial number of 2SAT
> instances.
>
> This still doesn't rule out the possibility of finding one satisfying
> assignment in polynomial time.
As you said above, polynomial doesn't mean efficient.
>
> As for positive evidence for P=NP, I would look at the published lower
> bounds.
> These bounds are already quite low (but still exponential) and new
> lower bounds are being published all the time.
You mean upper bounds, right?
>
> Russell
> - 2 many 2 count
Have you read and understood Stephen Cook's paper on the P vs. NP
problem? If not, it's a good first step. That is how I first got
introduced to the problem.
Here is a link:
http://www.claymath.org/millennium/P_vs_NP/
It's not my intent to insult you, but you don't sound like you
understand even the basics of the P vs. NP problem. You would
probably benefit greatly from doing some more reading and keeping an
open mind. It is a very fascinating problem.
-Phil
Joshua Cranmer
>> "The best they can" turns out to be pretty good. Modern SAT solvers
>> can find satisfying assignments very quickly for most instances.
>>
>
> That is irrelevant. The problem is that most of the SAT instances
> people really care about--e.g., the ones generated for cryptographic
> purposes--cannot be solved. "Most instances" is essentially
> meaningless. The P = NP problem is to find a single algorithm that
> decides *all* SAT instances in polynomial time.
Cryptography purposefully tries to find hard instances of problems. I
can find a factor of 2/3 of all numbers in two steps: try dividing by 2
and then try dividing by 3. The problem space of "hard" numbers to
factors is relatively tiny compared to the general scope of integers.
Many NP-complete problems filter down to common practical applications:
traveling salesman (circuit board design), graph coloring (compiling
code), etc. For these applications, the pathological cases are much
rarer. So, "most" is generally good enough for practical purposes. I'm
specifically excluding the choice of cryptography when I'm referring to
"practical" in this case.
> It's not my intent to insult you, but you don't sound like you
> understand even the basics of the P vs. NP problem. You would
> probably benefit greatly from doing some more reading and keeping an
> open mind. It is a very fascinating problem.
I suspect he understands it, perhaps in greater detail than you do. He's
just pointing out that there exists sufficiently fast and correct
algorithms for many problems for most uses. Theoretically optimal isn't
always the practically most efficient (the exponential-time algorithms
for primality testing work better than the polynomial-time, IIRC).
tc...@lsa.umich.edu
Joshua Cranmer <Pidg...@verizon.invalid> wrote:
>I suspect he understands it, perhaps in greater detail than you do.
Just my opinion, but based on my readings of Phil's posts and Russell's
posts over the years, I would give Phil the edge.
>He's just pointing out that there exists sufficiently fast and correct
>algorithms for many problems for most uses.
The context was whether we have evidence that P = NP. Pointing out the
above fact in that context is a non sequitur.
cplxphil
> On 12/17/2009 04:36 PM, cplxphil wrote:
>
> >> "The best they can" turns out to be pretty good. Modern SAT solvers
> >> can find satisfying assignments very quickly for most instances.
>
> > That is irrelevant. The problem is that most of the SAT instances
> > people really care about--e.g., the ones generated for cryptographic
> > purposes--cannot be solved. "Most instances" is essentially
> > meaningless. The P = NP problem is to find a single algorithm that
> > decides *all* SAT instances in polynomial time.
>
> Cryptography purposefully tries to find hard instances of problems. I
> can find a factor of 2/3 of all numbers in two steps: try dividing by 2
> and then try dividing by 3. The problem space of "hard" numbers to
> factors is relatively tiny compared to the general scope of integers.
>
> Many NP-complete problems filter down to common practical applications:
> traveling salesman (circuit board design), graph coloring (compiling
> code), etc. For these applications, the pathological cases are much
> rarer. So, "most" is generally good enough for practical purposes. I'm
> specifically excluding the choice of cryptography when I'm referring to
> "practical" in this case.
>
Yes...I realize this. Perhaps I am not as much of a moron as you seem
to think. My point is that P = NP has nothing to do with whether or
not most instances can be solved. P = NP is related to whether or not
all instances can be solved with a single algorithm.
In particular, saying that "most is generally good enough for
practical purposes" and excluding cryptography from "practical
purposes" is stupid. Cryptography is at least a portion of the reason
why people care about P = NP in the first place. Also, if "most is
generally good enough," why hasn't someone mapped the problem of
finding a proof of reasonable length of the Riemann Hypothesis to one
of your easy instances of SAT and resolved it?
> > It's not my intent to insult you, but you don't sound like you
> > understand even the basics of the P vs. NP problem. You would
> > probably benefit greatly from doing some more reading and keeping an
> > open mind. It is a very fascinating problem.
>
> I suspect he understands it, perhaps in greater detail than you do.
I don't appreciate that comparison. I'm not as brilliant as others on
this forum, and I may not be an expert on the subject, but my post was
at least not wildly inaccurate, whereas I believe that yours is at the
very least misleading. You seem to be presenting yourself as some
sort of expert, and proceed to insult me by claiming that whatever
little knowledge I have accumulated about the problem is inaccurate.
I might accuse you of being a bit lacking in understanding of the
problem yourself.
> just pointing out that there exists sufficiently fast and correct
> algorithms for many problems for most uses. Theoretically optimal isn't
> always the practically most efficient (the exponential-time algorithms
> for primality testing work better than the polynomial-time, IIRC).
>
Yes, I know that. I wasn't born yesterday. The point is, the
existence of SAT solvers that work on "most instances" has nothing to
do with whether or not P = NP is true.
> --
> Beware of bugs in the above code; I have only proved it correct, not
> tried it. -- Donald E. Knuth
-Phil
RussellE
> On Dec 17, 3:21 pm, RussellE <reaste...@gmail.com> wrote:
> > We can't even define "worst case complexity" for 3SAT.
> > A 3SAT instance that is hard for one solver might be easily solved
> > by a different solver. We do know that instances with a certain
> > variable to clause ratio tend to be more difficult, but even this
> > tells us nothing about how "hard" a specific instance might be.
>
> > This inability to even define "worst case" is one reason I
> > find the P=NP problem interesting.
>
> Worst-case complexity is definitely defined. The fact that we don't
> know what it is is the reason why P = NP remains unresolved.
We can define the words "worst case complexity".
But, there is no "worst case complexity" 3SAT instance.
Any solvable 3SAT instance can be solved in polytime
using the right solver.
> > > >If all NP-Complete problems were "hard", we wouldn't have commercial
> > > >SAT solvers.
>
> > > That's absurd. If a problem is hard but important, then people will do the
> > > best they can.
>
> > "The best they can" turns out to be pretty good. Modern SAT solvers
> > can find satisfying assignments very quickly for most instances.
>
> That is irrelevant. The problem is that most of the SAT instances
> people really care about--e.g., the ones generated for cryptographic
> purposes--cannot be solved.
307-digit key crack endangers 1024-bit RSA
http://arstechnica.com/old/content/2007/05/researchers-307-digit-key-crack-endangers-1024-bit-rsa.ars
> "Most instances" is essentially
> meaningless. The P = NP problem is to find a single algorithm that
> decides *all* SAT instances in polynomial time.
We might already have such an algorithm.
The P=NP problem is to PROVE the algorithm decides all
3SAT instances in a polynomial number of steps.
This could easily be much harder than finding an
efficient algorithm.
In fact, I am curious if anyone has done any research
in this area. For example, has someone generated
every possible 3SAT instance with, say, 12 variables,
and run them through a commercial SAT solver to see
if any of the instances required more than a "polynomial"
number of steps to solve?
> > As for positive evidence for P=NP, I would look at the published lower
> > bounds.
> > These bounds are already quite low (but still exponential) and new
> > lower bounds are being published all the time.
>
> You mean upper bounds, right?
Yes, I meant upper bounds.
> Have you read and understood Stephen Cook's paper on the P vs. NP
> problem?
I hadn't read that particular paper.
I noticed he mentions the Composite problem.
I think the state of the P=NP problem is in a similar state
as the Composite problem was before a poynomial algorithm
was found. There were efficient, probablistic, "exponential"
algorithms, but no one had proven there exists a deterministic,
polynomial algorithm.
I am not sure what you would consider "evidence".
I consider polynomial alogrithms for NP problems like 2SAT
to be evidence that P=NP may be possible.
History tells us that many probelems that were once
considered unsolvable have been solved.
Ben Bacarisse
> On Dec 17, 1:36 pm, cplxphil <cplxp...@gmail.com> wrote:
>> On Dec 17, 3:21 pm, RussellE <reaste...@gmail.com> wrote:
>
>> > We can't even define "worst case complexity" for 3SAT.
>> > A 3SAT instance that is hard for one solver might be easily solved
>> > by a different solver. We do know that instances with a certain
>> > variable to clause ratio tend to be more difficult, but even this
>> > tells us nothing about how "hard" a specific instance might be.
>>
>> > This inability to even define "worst case" is one reason I
>> > find the P=NP problem interesting.
>>
>> Worst-case complexity is definitely defined. The fact that we don't
>> know what it is is the reason why P = NP remains unresolved.
>
> We can define the words "worst case complexity".
> But, there is no "worst case complexity" 3SAT instance.
> Any solvable 3SAT instance can be solved in polytime
> using the right solver.
What does that mean? How do you ascribe what is usually an asymptotic
bound ("polytime") to a single instance? Unless the algorithm is
probabilistic, a solver for a particular instance simply takes a fixed
number of steps.
>> > > >If all NP-Complete problems were "hard", we wouldn't have commercial
>> > > >SAT solvers.
>>
>> > > That's absurd. If a problem is hard but important, then people will do the
>> > > best they can.
>>
>> > "The best they can" turns out to be pretty good. Modern SAT solvers
>> > can find satisfying assignments very quickly for most instances.
>>
>> That is irrelevant. The problem is that most of the SAT instances
>> people really care about--e.g., the ones generated for cryptographic
>> purposes--cannot be solved.
>
> 307-digit key crack endangers 1024-bit RSA
> http://arstechnica.com/old/content/2007/05/researchers-307-digit-key-crack-endangers-1024-bit-rsa.ars
>
>> "Most instances" is essentially
>> meaningless. The P = NP problem is to find a single algorithm that
>> decides *all* SAT instances in polynomial time.
>
> We might already have such an algorithm.
> The P=NP problem is to PROVE the algorithm decides all
> 3SAT instances in a polynomial number of steps.
> This could easily be much harder than finding an
> efficient algorithm.
If there is no need to prove that the algorithm works in polynomial
time then, yes, finding candidate algorithms is trivial. If you can
prove that any one candidate does, in fact, work (in polynomial time)
then P = NP.
> In fact, I am curious if anyone has done any research
> in this area. For example, has someone generated
> every possible 3SAT instance with, say, 12 variables,
> and run them through a commercial SAT solver to see
> if any of the instances required more than a "polynomial"
> number of steps to solve?
Again, what does this mean. I see now the "quotes" have come in to it
so maybe you don't know exactly what you mean either.
<snip>
--
Ben.
tc...@lsa.umich.edu
RussellE <reas...@gmail.com> wrote:
>We can define the words "worst case complexity".
>But, there is no "worst case complexity" 3SAT instance.
True; so what?
>Any solvable 3SAT instance can be solved in polytime
>using the right solver.
In fact, it can be solved in constant time.
>In fact, I am curious if anyone has done any research
>in this area. For example, has someone generated
>every possible 3SAT instance with, say, 12 variables,
>and run them through a commercial SAT solver to see
>if any of the instances required more than a "polynomial"
>number of steps to solve?
It's not clear what you mean by "polynomial" here.
Certainly, one can construct instances on which DPLL provably takes
exponential time. DPLL forms the basis for most branching solvers.
Of course, modern SAT solvers have complicated refinements to the
basic DPLL algorithm, including clause learning, so it is not so easy
to construct provably hard instances for them, simply because the
algorithm is so complicated. But commercial SAT solvers don't seem
to do so well on cryptographic problems.
>I am not sure what you would consider "evidence".
I'll tell you what I would consider evidence. Come up with an algorithm that
appears to break all known cryptographic instances rapidly. Even if you can't
prove that your algorithm runs in polynomial time, I would consider that to
be pretty good evidence that P = NP.
tc...@lsa.umich.edu
In article <01f90c21-0546-4ba3...@u36g2000prn.googlegroups.com>,
RussellE <reas...@gmail.com> wrote:
>307-digit key crack endangers 1024-bit RSA
>http://arstechnica.com/old/content/2007/05/researchers-307-digit-key-crack-endangers-1024-bit-rsa.ars
So just bump the size up to 2048 bits or 4096 bits. What does that do?
A factor of two or four in the size of the instance shouldn't be a
problem for a polynomial-time algorithm.
Tim Little
> We can define the words "worst case complexity". But, there is no
> "worst case complexity" 3SAT instance.
You have a severe misunderstanding. "Worst case complexity" is
defined relative to an algorithm, not an instance.
> Any solvable 3SAT instance can be solved in polytime using the right
> solver.
Any instance of 3SAT whatsoever can be decided in a single step. Once
again, complexity is *not* a property that applies to an instance.
> We might already have such an algorithm.
We do not. All known algorithms have cases where the runtime is not
polynomial.
> The P=NP problem is to PROVE the algorithm decides all 3SAT
> instances in a polynomial number of steps.
No, it is to prove that *there exists* such an algorithm, whether we
actually find one or not.
> In fact, I am curious if anyone has done any research in this area.
Of course they have!
- Tim
tc...@lsa.umich.edu
Tim Little <t...@little-possums.net> wrote:
>On 2009-12-18, RussellE <reas...@gmail.com> wrote:
>> We might already have such an algorithm.
>
>We do not. All known algorithms have cases where the runtime is not
>polynomial.
Technically, we don't *know* this. There are algorithms that are so
complicated that we can't actually prove that they don't run in polynomial
time on all instances. And as Phil mentioned, we can even construct an
artificial algorithm with the property that proving that it doesn't solve
SAT in polynomial time would prove that P != NP.
RussellE
> RussellE <reaste...@gmail.com> writes:
> > On Dec 17, 1:36 pm, cplxphil <cplxp...@gmail.com> wrote:
> >> On Dec 17, 3:21 pm, RussellE <reaste...@gmail.com> wrote:
>
> >> > We can't even define "worst case complexity" for 3SAT.
> >> > A 3SAT instance that is hard for one solver might be easily solved
> >> > by a different solver. We do know that instances with a certain
> >> > variable to clause ratio tend to be more difficult, but even this
> >> > tells us nothing about how "hard" a specific instance might be.
>
> >> > This inability to even define "worst case" is one reason I
> >> > find the P=NP problem interesting.
>
> >> Worst-case complexity is definitely defined. The fact that we don't
> >> know what it is is the reason why P = NP remains unresolved.
>
> > We can define the words "worst case complexity".
> > But, there is no "worst case complexity" 3SAT instance.
> > Any solvable 3SAT instance can be solved in polytime
> > using the right solver.
>
> What does that mean? How do you ascribe what is usually an asymptotic
> bound ("polytime") to a single instance? Unless the algorithm is
> probabilistic, a solver for a particular instance simply takes a fixed
> number of steps.
Yes, worst case complexity refers to an algorithm, not an instance.
Even so, many proofs of bounds on complexity create
particular instances that requires an exponential number of steps
for a specific algorithm to solve.
If someons does prove P=NP it will probably be several algorithms
with a "master" algorithm that determines which other algorithms
to use based of the particular instance. There are already algorithms
that use case by case analysis of the instance to come up with a
more efficient algorithm.
> >> "Most instances" is essentially
> >> meaningless. The P = NP problem is to find a single algorithm that
> >> decides *all* SAT instances in polynomial time.
>
> > We might already have such an algorithm.
> > The P=NP problem is to PROVE the algorithm decides all
> > 3SAT instances in a polynomial number of steps.
> > This could easily be much harder than finding an
> > efficient algorithm.
>
> If there is no need to prove that the algorithm works in polynomial
> time then, yes, finding candidate algorithms is trivial. If you can
> prove that any one candidate does, in fact, work (in polynomial time)
> then P = NP.
My point is it is harder to prove bounds for a algorithm than it is
to come up with an algorithm that works well in practice.
One example would be restarts. Many commercial SAT solvers
use restarts, yet, I haven't read any papers that put bounds
on DPLL solvers using restarts.
> > In fact, I am curious if anyone has done any research
> > in this area. For example, has someone generated
> > every possible 3SAT instance with, say, 12 variables,
> > and run them through a commercial SAT solver to see
> > if any of the instances required more than a "polynomial"
> > number of steps to solve?
>
> Again, what does this mean. I see now the "quotes" have come in to it
> so maybe you don't know exactly what you mean either.
Assume I create every 3SAT instance with 10 variables and
run all of them through a commercial SAT solver.
I find the hardest instance required 293,142 steps.
Would this prove P=NP because the worst case
instance required O(10^5) steps?
RussellE
>
> So just bump the size up to 2048 bits or 4096 bits. What does that do?
> A factor of two or four in the size of the instance shouldn't be a
> problem for a polynomial-time algorithm.
If my algorithm is O(n^10), there is a big difference between
307^10 and 4096^10. Of course, I can always hope the
computers keep getting faster.