A New Map Traces the Limits of Computation(quantamagazine.org)
quantamagazine.org
A New Map Traces the Limits of Computation
https://www.quantamagazine.org/20150929-edit-distance-computational-complexity/
4 comments
Pack it up folks. The webdevs have solved P=NP.
What do you mean?
The problem outlined, and the parent->parent->parent poster postulated is the Boolean Satisfiability Problem [1]. The Cook-Levin Theorem [2] more or less founded the idea that P and NP problems are different classes of problems. It also hinted that a generalized solution to any NP problem could be a solution to ANY NP class problem, by showing that several NP problems can be reduced to the Boolean Satisfiability Problem.
This discovery earned a Turing Award and started the whole P vs NP debate [3].
:.:.:
The joke.
>Pack it up folks. The webdevs have solved P=NP.
Either implies somebody accidentally solved the greatest problem in computer science... OR that web developers are as naive as their stereotype implies.
[1] https://en.wikipedia.org/wiki/Boolean_satisfiability_problem
[2] https://en.wikipedia.org/wiki/Cook%E2%80%93Levin_theorem
[3] https://en.wikipedia.org/wiki/P_versus_NP_problem
This discovery earned a Turing Award and started the whole P vs NP debate [3].
:.:.:
The joke.
>Pack it up folks. The webdevs have solved P=NP.
Either implies somebody accidentally solved the greatest problem in computer science... OR that web developers are as naive as their stereotype implies.
[1] https://en.wikipedia.org/wiki/Boolean_satisfiability_problem
[2] https://en.wikipedia.org/wiki/Cook%E2%80%93Levin_theorem
[3] https://en.wikipedia.org/wiki/P_versus_NP_problem
The joke ignores the obvious though: many instances of NP problems can be solved completely with our current machines in very short time periods.
By the way, I was reading an old comment of yours[0] and although I can't answer there because it's too old, I do have an answer for you ...
You question was:
Email me if you want more details.
[0] https://news.ycombinator.com/item?id=8750542
You question was:
If it were possible to efficiently
solve a large NP-complete problem,
the solution to which real-world
problem would have the largest
positive impact?
Email me if you want more details.
[0] https://news.ycombinator.com/item?id=8750542
Thanks for responding here. I probably would have never seen the comment otherwise. (Perhaps why commenting on old threads is disabled?)
Certainly cryptosystems could be broken, but I'm not sure of the immediate positive impact of that. It would seem that it could be dangerously disruptive to drop such an algorithm.
I'm more interested in the "We know there are all these really hard problems and how to solve them, but we just don't have the computational power to solve them" aspect that typically comes along with P v. NP discussions.
I understand many of the theoretical problems (3-coloring, subset sum, subgraph isomorphism, etc), but I want to know what practical problems do we have that we don't have good solutions to, simply because NP problems are too hard for us to compute.
Certainly cryptosystems could be broken, but I'm not sure of the immediate positive impact of that. It would seem that it could be dangerously disruptive to drop such an algorithm.
I'm more interested in the "We know there are all these really hard problems and how to solve them, but we just don't have the computational power to solve them" aspect that typically comes along with P v. NP discussions.
I understand many of the theoretical problems (3-coloring, subset sum, subgraph isomorphism, etc), but I want to know what practical problems do we have that we don't have good solutions to, simply because NP problems are too hard for us to compute.
> I probably would have never seen
> the comment otherwise.
> I'm more interested in the "We know
> there are all these really hard
> problems and how to solve them, but
> we just don't have the computational
> power to solve them" aspect that
> typically comes along with P v. NP
> discussions.
> I understand many of the theoretical
> problems (3-coloring, subset sum,
> subgraph isomorphism, etc), but I want
> to know what practical problems do we
> have that we don't have good solutions
> to, simply because NP problems are too
> hard for us to compute.
What do you mean when you say these are theoretical? If we can 3-color then we can perform better packing, better scheduling, better layouts for processors, we can break crypto-systems, in what sense are these not practical?
Can you give me any example of anything you would call a practical problem?
[0] http://hnnotify.com/
>OK, that makes it clear that I really don't know what you're asking for. The point is that there are all these problems such that the algorithms we have are exponential, which makes them infeasible. In that sense we don't know how to solve them. Why do you claim we do know how to solve them?
I claim we can solve them, because we know the basic algorithm that will solve any particular problem given enough time and space: brute-force search and verify.
>What do you mean when you say these are theoretical?
There is the theoretical, "This entire class of problems is hard.", NP problem and there is the, "Provide me with a 3-coloring of this specific graph", NP problem.
I claim that while it is widely believed that we cannot solve the entire class of NP problems, we may be able to solve particular, realized instances of problems from that class.
Yes, the algorithms are exponential, but if you choose your parameter space appropriately, you may be able to run an exponential algorithm in a reasonable amount of time and space.
So, there are parameters for algorithms that we can compute solutions for, but we are still limited to the amount of physical computational ability that we can control. This puts limits on which particular problems we can solve.
>If we can 3-color then we can perform better packing, better scheduling, better layouts for processors, we can break crypto-systems, in what sense are these not practical?
Only in the sense that I'm looking for a specific packing problem. For example, here are the dimensions and locations of UPS's fleet. Here are the dimensions, locations, and destinations of the packages. Give me the optimal routes. Practically, you'd probably want to model and solve failure modes as well to find the most "robust" route.
>better packing, better scheduling, better layouts for processors
What you are referring to here, I have been referring to as "theoretical".
Optimizing UPS may or may not have much tangible benefit, depending on how close their current solutions are to the optimal. My question is asking: solving which particular problem would provide the most benefit?
>Can you give me any example of anything you would call a practical problem?
That is my question. :)
But, a toy example would be roughly (though could could possibly be attacked another way):
Provide a subset of [-12,30,7,9,-84,24,1,8,3,-5,2] that sums to 0.
Edit: Thanks for the link. I'm not sure if I want an email from every reply that I get here...but I'll think about it.
I claim we can solve them, because we know the basic algorithm that will solve any particular problem given enough time and space: brute-force search and verify.
>What do you mean when you say these are theoretical?
There is the theoretical, "This entire class of problems is hard.", NP problem and there is the, "Provide me with a 3-coloring of this specific graph", NP problem.
I claim that while it is widely believed that we cannot solve the entire class of NP problems, we may be able to solve particular, realized instances of problems from that class.
Yes, the algorithms are exponential, but if you choose your parameter space appropriately, you may be able to run an exponential algorithm in a reasonable amount of time and space.
So, there are parameters for algorithms that we can compute solutions for, but we are still limited to the amount of physical computational ability that we can control. This puts limits on which particular problems we can solve.
>If we can 3-color then we can perform better packing, better scheduling, better layouts for processors, we can break crypto-systems, in what sense are these not practical?
Only in the sense that I'm looking for a specific packing problem. For example, here are the dimensions and locations of UPS's fleet. Here are the dimensions, locations, and destinations of the packages. Give me the optimal routes. Practically, you'd probably want to model and solve failure modes as well to find the most "robust" route.
>better packing, better scheduling, better layouts for processors
What you are referring to here, I have been referring to as "theoretical".
Optimizing UPS may or may not have much tangible benefit, depending on how close their current solutions are to the optimal. My question is asking: solving which particular problem would provide the most benefit?
>Can you give me any example of anything you would call a practical problem?
That is my question. :)
But, a toy example would be roughly (though could could possibly be attacked another way):
Provide a subset of [-12,30,7,9,-84,24,1,8,3,-5,2] that sums to 0.
Edit: Thanks for the link. I'm not sure if I want an email from every reply that I get here...but I'll think about it.
>> ... there are all these problems such that
>> the algorithms we have are exponential,
>> which makes them infeasible. In that
>> sense we don't know how to solve them.
>> Why do you claim we do know how to solve
>> them?
> I claim we can solve them, because we know
> the basic algorithm that will solve any
> particular problem given enough time and
> space: brute-force search and verify.
>> What do you mean when you say these are
>> theoretical?
> There is the theoretical,
> "This entire class of problems is hard.",
> NP problem and there is the,
> "Provide me with a 3-coloring of this
> specific graph", NP problem.
> I claim that while it is widely believed
> that we cannot solve the entire class of
> NP problems, we may be able to solve
> particular, realized instances of problems
> from that class.
> Yes, the algorithms are exponential,
> but if you choose your parameter space
> appropriately, you may be able to run
> an exponential algorithm in a reasonable
> amount of time and space.
> So, there are parameters for algorithms
> that we can compute solutions for, but
> we are still limited to the amount of
> physical computational ability that we
> can control. This puts limits on which
> particular problems we can solve.
>> If we can 3-color then we can perform
>> better packing, better scheduling,
>> better layouts for processors, we can
>> break crypto-systems, in what sense are
>> these not practical?
> Only in the sense that I'm looking for
> a specific packing problem. For example,
> here are the dimensions and locations
> of UPS's fleet. Here are the dimensions,
> locations, and destinations of the packages.
> Give me the optimal routes. " Practically,
> you'd probably want to model and solve
> failure modes as well to find the most
> "robust" route."
Are you just looking for a specific instance of a problem?
>> better packing, better scheduling, better
>> layouts for processors
> What you are referring to here, I have been
> referring to as "theoretical".
> Optimizing UPS may or may not have much
> tangible benefit, depending on how close
> their current solutions are to the optimal.
> My question is asking: solving which
> particular problem would provide the most
> benefit?
>> Can you give me any example of anything
>> you would call a practical problem?
> That is my question. :)
> But, a toy example would be roughly
> ...
> Provide a subset of
> [-12,30,7,9,-84,24,1,8,3,-5,2]
> that sums to 0.
I can provide for you a specific instance of a three-coloring problem.
I admit that I may be using terms in non-standard ways and that my implied definitions may not be fully consistent. I apologize for any confusion it may cause.
If you have a standard glossary of terms I could probably reformulate the statements in those terms.
>I still don't understand what you mean by the word "theoretical". These are practical problems, instances of which turn up all over the world every day. Given that we want to solve these instances of these problems, in what sense are the problems "theoretical"?
I probably shouldn't have used the word. It's not very good. To answer your question, though, they are theoretical in the sense that "better packing" is not an actual driven route that used less resources than the route chosen by another algorithm would have; rather, it is just a description, or template, of the result you (or someone) desire.
>What do you mean by "solving", "problem", and "benefit"? These are genuine questions - you seem to be using these words in ways I don't recognise.
Roughly:
problem = complete data/parameters that can be fed to an NP solver (either search and verify every permutation of the solution space or (hypothetical) specialized solver)
solving = the process of computing the solution to the problem and outputting the answer
benefit = resources saved by applying an optimal solution instead of the sub-optimal solution that would have been used otherwise
>So you don't know what a practical problem is?
I was being a bit facetious, but the statement is still true, I believe (depending on what you meant by your question).
I know what a practical problem is, I just do not have have an actual instance whose solution would be beneficial. My question is to be provided with such a problem.
>Is that what you're calling a practical problem? Is what you're calling a "practical problem" simply a specific instance?
I believe we'd call it an instance of some form of the subset sum problem (I believe it can be formulated more formally).
>I can provide for you a specific instance of a three-coloring problem.
Sure. But, please don't be expecting me to solve it :)
If you have a standard glossary of terms I could probably reformulate the statements in those terms.
>I still don't understand what you mean by the word "theoretical". These are practical problems, instances of which turn up all over the world every day. Given that we want to solve these instances of these problems, in what sense are the problems "theoretical"?
I probably shouldn't have used the word. It's not very good. To answer your question, though, they are theoretical in the sense that "better packing" is not an actual driven route that used less resources than the route chosen by another algorithm would have; rather, it is just a description, or template, of the result you (or someone) desire.
>What do you mean by "solving", "problem", and "benefit"? These are genuine questions - you seem to be using these words in ways I don't recognise.
Roughly:
problem = complete data/parameters that can be fed to an NP solver (either search and verify every permutation of the solution space or (hypothetical) specialized solver)
solving = the process of computing the solution to the problem and outputting the answer
benefit = resources saved by applying an optimal solution instead of the sub-optimal solution that would have been used otherwise
>So you don't know what a practical problem is?
I was being a bit facetious, but the statement is still true, I believe (depending on what you meant by your question).
I know what a practical problem is, I just do not have have an actual instance whose solution would be beneficial. My question is to be provided with such a problem.
>Is that what you're calling a practical problem? Is what you're calling a "practical problem" simply a specific instance?
I believe we'd call it an instance of some form of the subset sum problem (I believe it can be formulated more formally).
>I can provide for you a specific instance of a three-coloring problem.
Sure. But, please don't be expecting me to solve it :)
> ... I may be using terms in non-standard
> ways ...
Problem: A collection of instances
Instance: A specific question to answer
>> Given that we want to solve these
>> instances of these problems, in
>> what sense are the problems
>> "theoretical"?
> ... they are theoretical in the sense
> that "better packing" is not an actual
> driven route that used less resources
> than the route chosen by another
> algorithm would have; rather, it is
> just a description, or template, of
> the result you (or someone) desire.
For some instances of that, real instances that turn up in the real world, the best known algorithms are exponential in performance. I would not call that "theoretical". I would call that "practical". If you call it "theoretical" then I don't understand what you mean. Are you simply saying that the general definition of the problem is "theoretical", as opposed to an actual instance? That would seem perverse.
>> What do you mean by "solving", "problem",
>> and "benefit"? These are genuine questions
>> - you seem to be using these words in ways
>> I don't recognise.
> Roughly:
> problem = complete data/parameters that can
> be fed to an NP solver (either
> search and verify every permutation
> of the solution space or (hypothetical)
> specialized solver)
> solving = the process of computing the solution
> to the problem and outputting the answer
> benefit = resources saved by applying an optimal
> solution instead of the sub-optimal
> solution that would have been used
> otherwise
>> So you don't know what a practical problem is?
> I know what a practical problem is, I just do
> not have have an actual instance whose solution
> would be beneficial. My question is to be provided
> with such a problem.
>> Is that what you're calling a practical problem?
>> Is what you're calling a "practical problem"
>> simply a specific instance?
> I believe we'd call it an instance of some form
> of the subset sum problem (I believe it can be
> formulated more formally).
>> I can provide for you a specific instance of
>> a three-coloring problem.
> Sure. But, please don't be expecting me to solve it :)
The joke also ignores that most limited BSP are solvable in P space. But then nearly all jokes temporarily suspend reality for several sentences, or paragraphs. In fact one theory postulates that humor is the human reaction when we're confronted by facts that lie outside of our present psychological scheme's ability to comprehend as possible.
Generally speaking in depth analysis of jokes is a futile affair. This sentiment is often expressed via the phrase, "I'm only joking."
Generally speaking in depth analysis of jokes is a futile affair. This sentiment is often expressed via the phrase, "I'm only joking."
Anybody can solve a SAT problem, the issue is how easily they can do it.
You can bet your life this web app doesn't use an algorithm that is both always correct and scales efficiently with the size of the formula.
I daresay it's always correct but the cost grows somewhat exponentially with the number of variables. Constructs like `(a or b) xor (c or d) ...` are especially obnoxious. XOR explodes exquisitely.
Great science writing, explaining concepts in an accessible way without homeopathic dilutions of the substance.
Cool, I did not know that SETH and PvNP were different
Basically:
- If you can solve k-sat in time (2-eps)^n, you've refuted SETH.
- If you can solve 3-sat in time (1+o(1))^n, you've refuted ETH.
- If you can solve 3-sat in time n^O(1), you've refuted P!=NP.
Since general k-sat is at least as hard as 3-sat, it follows that SETH is the strongest hypothesis (hence the name) and thus the most likely to fall. P!=NP is the weakest hypothesis and thus the most likely of the three to be true.
- If you can solve k-sat in time (2-eps)^n, you've refuted SETH.
- If you can solve 3-sat in time (1+o(1))^n, you've refuted ETH.
- If you can solve 3-sat in time n^O(1), you've refuted P!=NP.
Since general k-sat is at least as hard as 3-sat, it follows that SETH is the strongest hypothesis (hence the name) and thus the most likely to fall. P!=NP is the weakest hypothesis and thus the most likely of the three to be true.
is (1+o(1)) essentially anything subexponential but hyperpolynomial?
Yeah anything subexponential. We can also write it as `2^o(n)`.
It doesn't have to by hyperpolynomial, if you solve ETH in linear time, you also refute it :-)
It doesn't have to by hyperpolynomial, if you solve ETH in linear time, you also refute it :-)
[deleted]
>jsprogrammer
oh my god your really not helping
oh my god your really not helping
We detached this comment from https://news.ycombinator.com/item?id=10305170 and marked it off-topic.
I don't often wade into exchanges like this, but here we go.
Firstly, you mean "you're" and not "your".
Secondly, I know many fantastically talented and productive JS programmers who really, really know what they're doing. They use JS either because they have to, or because it suits their problem domain. Your remark is snide, unhelpful, and out of keeping.
Thirdly, jsprogrammer was right. For many problems only a vanishingly small proportion of instances are hard. In my own area - graph three coloring - it's actually quite difficult to produce graphs that are known to be three-colorable, and yet are hard to color. Most of the time, in the technical sense, graph three coloring is easy, even though it is known to be NP-Complete.
So I believe your remark to be unwarranted.
Firstly, you mean "you're" and not "your".
Secondly, I know many fantastically talented and productive JS programmers who really, really know what they're doing. They use JS either because they have to, or because it suits their problem domain. Your remark is snide, unhelpful, and out of keeping.
Thirdly, jsprogrammer was right. For many problems only a vanishingly small proportion of instances are hard. In my own area - graph three coloring - it's actually quite difficult to produce graphs that are known to be three-colorable, and yet are hard to color. Most of the time, in the technical sense, graph three coloring is easy, even though it is known to be NP-Complete.
So I believe your remark to be unwarranted.
Haters gonna hate, I actually enjoyed quite a laugh from this comment. Just because some people can't take a joke doesn't mean they're opinions count for everyone.
Neither is your lack of appropriate grammatical structure.
There is a minimalistic web app that answers this question: http://symbolabs.de/symboole
Enter a Boolean expression and chose the Solve or Shrink functionality from the pop-up menu.