I trying to understand where, as a programmer in situations where it can be good to do a NP-complete reduction to prove that a problem is NP-complete, why is it good to do that as a programmer? I don't understand.
$\begingroup$
$\endgroup$
3
-
9$\begingroup$ It is always useful to obtain lower bounds on problem complexity to avoid searching fast solutions in vain. $\endgroup$– user16034Nov 2, 2022 at 12:38
-
$\begingroup$ Why isn't this closed as either too broad or as a duplicate? $\endgroup$– Peter MortensenNov 3, 2022 at 1:04
-
$\begingroup$ @PeterMortensen, If you think it should be closed as "too broad", I suggest the most fruitful path would be to make the case for why it is too broad, or flag it for closure. If you think it should be closed as a duplicate, I suggest the best way you could help would be to identify what question you think it is a duplicate of, and then flag it for closure as a dup of that question. $\endgroup$– D.W. ♦Nov 5, 2022 at 21:44
Add a comment
|
9 Answers
$\begingroup$
$\endgroup$
8
When dealing with a problem, knowing how to recognize a $\mathsf{NP}$-hard problem can prevent you from hair loss trying to find an efficient solution (as it is thought that $\mathsf{P}\neq \mathsf{NP}$).
Reductions can also be seen in a "If I know how to solve $A$, then I know how to solve $B$" way.
When confronted to a $\mathsf{NP}$-hard problem, you can then think of ways to deal with intractability.
-
8$\begingroup$ It does not mean that there is no efficient solution, but that it is very likely that there is no deterministic efficient solution on every input. That is not necessarily completely out of the question to solve the problem. For example, SAT solvers are known to be very efficient on a lot of boolean formulas (even if there are some formulas where they fails). $\endgroup$ Nov 1, 2022 at 15:23
-
1$\begingroup$ @JonteYH Efficient algorithms for specific cases of NP-complete problems rely on something that is specific to those sets of inputs, that you may not be able to apply to other inputs (e.g. running something over finite-ranged integers instead of floating points or unbounded integers). If you have an algorithm, you should also have the complexity, which would tell you how the running time would change for other input parameters. (It may also be that e.g. an exponential-time algorithm runs in linear time for some inputs, which is basically just getting lucky). $\endgroup$ Nov 2, 2022 at 10:53
-
9$\begingroup$ It is not so much "it is thought that P $\neq$ NP" but rather "it is thought that a programmer will not accidentally prove P = NP by writing code". $\endgroup$– StefNov 2, 2022 at 15:48
-
6$\begingroup$ @Stef It's definitely thought/believed that P ≠ NP, it's just that no-one has figured out how to prove that yet. $\endgroup$ Nov 3, 2022 at 10:03
-
1$\begingroup$ @Stef And if they do, accidentally, they get an offer from the Laundry that they cannot refuse ;-). $\endgroup$ Nov 4, 2022 at 16:39
$\begingroup$
$\endgroup$
5
If a problem is NP-complete that means that lots and lots of great mathematicians, computer scientists, and very clever software developers have not been able to find an efficient solution for the problem. And that means nobody can blame you if you can't find one. If you could find one, they'd introduce a Nobel prize for computer science just for you. (Roughly quoted from memory from Garey-Johnson, Computers and Intractability, 1979).
-
2$\begingroup$ Nitpick: You not only have to find an algorithm, you also have to prove it is efficient. We do have existing algorithms which are known to solve NP-complete problems in polynomial time iff P=NP. $\endgroup$ Nov 2, 2022 at 15:02
-
1$\begingroup$ @SriotchilismO'Zaic That sounds interesting. Any search terms or links you can recommend? $\endgroup$– MayaNov 2, 2022 at 20:17
-
2$\begingroup$ @Maya Making such an algorithm can be implemented via dovetailing, and is at the level for which (with the right context) an undergraduate might be expected to do so as part of coursework. I can't find any published sources describing such algorithms, but there is a post on code-golf which implements such an algorithm on the subset sum problem. $\endgroup$ Nov 2, 2022 at 20:31
-
$\begingroup$ @SriotchilismO'Zaic of course, the algorithm in that Code Golf is a rather extreme example demonstrating that just because a problem is in P, it does not at all mean we can efficiently solve it in practice. $\endgroup$ Nov 3, 2022 at 10:27
-
$\begingroup$ If there was an algorithm that solves an NP-complete problem in p(n) time (even if I have not the slightest idea what the algorithm is), then I can write a program that generates algorithms, runs 1 step on the first, then 2 steps on the first and one step on the second, ..., then n steps on the first, n-1 steps on the second, ... 2 steps on the n-1st, 1 step on the n-th algorithm and so on, and I find an algorithm that works in fixed time c, and solve the problem in p(n) * max (p(n), c) time = polynomial time. (Better check it). $\endgroup$ Nov 4, 2022 at 17:04
$\begingroup$
$\endgroup$
Knowing about NP-complete problems is part of the cultural baggage of every computer scientist, as is the case for other core results (such as the non-computability of the halting problem). NP-complete problems arise in practice. The maximal independent set problem for graphs is aimed at simultaneously exploiting a maximal amount of resources that are not dependent on one another.
Theoretical computer science focuses on extremes: problems that are not computable, problems that are too hard to compute (for larger sized instances), limits of computational speed up, limits of compressibility etc. You can interpret these results (from a practical point of view) as guard rails you need to know about in order to make reasonable decisions about new problems. Some of these problems turn up in practice in different guises. The reduction process helps to show that a new problem is NP-complete by linking it (in the chain of NP-complete problems) to a known NP-complete problem. As pointed out in the first answer: when this happens it is reasonable to stop searching for an efficient solution (unless the aim is to resolve the long standing open problems related to NP-completeness).
Theoretical results may appear at times to stay far from practice. They do impact application areas: the halting problem indicated the need to develop real-time programming languages by restricting higher level constructs. The limits of compressibility and running-time speed-up support decisions on when it is reasonable to give up on trying to optimise code for certain applications.
$\begingroup$
$\endgroup$
4
As a working programmer, you need to recognize when you are being asked by the business to do the literally impossible.
Assuming 𝑃 ≠ 𝑁𝑃 (you don't need to understand what that means, just know that most of us do), then when you are being asked to solve a problem that falls into NP the solution is going to necessarily be slow (although it may be fast enough in practice).
But if you are told that your map direction calculations for the shortest route that visits cities A, B, C, D, E, and F is too slow, you need to understand that there is a hard bound on how fast it can be.
That's why it's important to understand broadly the sorts of problems in the NP space and why people ask about them (sometimes in disguise) in interviews: you need to be able to recognize immediately that the objective is unachievable and start brainstorming workarounds or trade-offs to hopefully still achieve the business goals.
-
4$\begingroup$ Then of course, you can push back and say "we won't find the shortest route, but we'll find one that's reasonably short". IIRC the traveling salesman problem does have algorithms that find "reasonably short" routes efficiently. $\endgroup$ Nov 2, 2022 at 16:01
-
1$\begingroup$ @user253751 pretty sure it does, my point is just more that business people are even less likely than programmers to know what's hard/easy and part of the job is to explain it to them and then help solve the problem anyway. $\endgroup$ Nov 2, 2022 at 16:04
-
$\begingroup$ There are many instances of NP-hard problems that are routinely solved. There is nothing "literally impossible" in writing a program to solve a 0-1 integer programming problem. Such things are solved all the time in operations research, frequently with fairly large problem sizes. You allude to the Traveling Salesman Problem. The state of the art in TSP is capable of doing things like finding real-world optimal tours through tens of thousands of locations. $\endgroup$ Nov 3, 2022 at 19:37
-
$\begingroup$ As a programmer, over the years I've been asked to do multiple things which are impossible to solve, but I don't recall ever having asked to do something which is NP-complete. (Note also that NP-complete problems are not literally impossible to solve -- they are possible to solve, it just means they may take a long time to solve for specific inputs). $\endgroup$– AbigailNov 4, 2022 at 18:25
$\begingroup$
$\endgroup$
2
As a programmer, you likely do not need to pay much attention to the class of NP-complete problems. The class of NP problems is much more useful. Obviously, if your problem is NP, it cannot be solved for all inputs in polynomial time (by a deterministic Turing machine, and assuming $P\ne NP$... which is currently considered a pretty darn reasonable assumption)
The easiest way to prove that your problem is NP is to demonstrate that, were you to be able to solve your problem in polynomial time, you could also solve an existing NP problem in polynomial time as well. This is what they mean by a "reduction".
For mathematicians, the idea of NP-completeness is very useful. Completeness says that you can reduce any NP problem to any NP-complete problem. This is very useful for the topic of $P=NP$. If you could find a polynomial time solution to any NP-complete problem, it is trivial to show that you found a solution to every NP problem, thus demonstrating that $P=NP$ without having to mechanically exhaust every last NP problem, one by one, demonstrating that every one of them was infact P.
As a programmer, the best use for NP-complete I have found is to take advantage of the raw amount of effort people have put into exploring good algorithms for dealing with them. I may be working on a problem that's totally unique to my domain, but if I can transform it into another NP problem that people have indeed worked hard on, I may be able to leverage their work. This is especially true for the SAT problems, for which a tremendous amount of work has been done.
As a simple example, in SAT problems, there is often a particularly difficult class of problems that take the form (a|b|c)&(d|e|f)&...&(x|y|z), where a, b, c, ... z are literals (possibly negated), and they aren't all unique (i.e. d may be the same as ~a). In many cases, it is easy to show that the complexity of satisfying that expression explodes as the expression gets longer. But sometimes my problem doesn't call for such expressions. Maybe mine has a limit in how many terms it uses, bounding the exponential growth to something palatable. Maybe each term has no more than one negated term (which makes those Horn clauses -- satisfiability of Horn clauses is in P. In fact, it's linear!).
Sometimes you get lucky and find that, when you do the transformation, you get something really easy (like the Horn clauses mentioned above). In those cases, you might simply figure out what the analog for Horn clauses is in your problem, and just code it up yourself. Other times there's some amazing math behind it, and the easiest way to solve your problem is to actually reduce it to SAT, and solve that.
If I have a problem that is NP, it is NP. I can't leverage other mathematicians to magically make it P. However, often I don't actually have a NP problem. I really have a hard-to-describe subset of a NP problem that I called NP out of laziness or ignorance. If I transform my problem into another, I can also tranform my real inputs. There's a decent chance that my real problem fell within the range of a previously explored P region of a NP problem. SAT, for instance, has been mightily explored. We're actually pretty darn good at finding ways to satisfy many boolean expressions. Maybe an existing SAT solver has a polynomial time solution for all of the reductions of my problem within the limited inputs I need. It's easy to prove they can't solve them all (because SAT is NP), but dang if we haven't made great advancements on many cases!
It's also helpful for demonstrating when I'm not so lucky. If I can take a "hard" problem from SAT, and show that solving my problem requires solving my problem too, then I show one of the following:
- My problem is NP-complete
- My problem requires exploring a P sub-problem of a NP-complete problem like SAT which the state of the art from hundreds of mathematicians hasn't solved yet, or.
- I need to come up with a more clever reduction to sidestep the issue
This does a good job of focusing my attention. Should I really be trying to solve this problem? Is this problem perhaps NP? (even if I haven't proven it formally). Am I capable of finding the more clever reduction? (which, if I can find, shows how I may be able to use the existing proofs for SAT to solve my problem)
Other than that, NP is far more useful for programmers than NP-complete.
Well, maybe. I have found that, when explaining why we shouldn't do something, the term "NP-complete" rings really nicely in people's ears. There's something about the word "complete" that suggest finality, even when your audience doesn't really grasp P vs NP. NP-hard is another useful word, but I find NP-complete does the job really well.
-
$\begingroup$ English is not my mother-tongue so i wonder what do you mean by " I may be able to leverage their work" is there another advantage when you show that a problem is NP-Complete besides it may not exist a effecient algorithm so solve the problem? $\endgroup$– Jonte YHNov 3, 2022 at 8:08
-
4$\begingroup$ Your answer seems to use "NP" to mean "Not P" (for example, when you claim that "Obviously, if your problem is NP, it cannot be solved for all inputs in polynomial time"). P is part of NP. Checking if a list is sorted is in NP, but can obviously be solved in polynomial time. $\endgroup$ Nov 3, 2022 at 19:09
$\begingroup$
$\endgroup$
1
To argue in front of your boss.
Source: https://www.ac.tuwien.ac.at/people/szeider/cartoon/
This cartoon is originally from the famous textbook Computers and Intractability by Garey & Johnson, but adapted to the current Zeitgeist.
PS: Concerning the adaption, I would prefer to see real parity here, i.e., having one Alice and one Bob and not Alice two times, but I am not sufficiently talented to modify the cartoon.
-
1$\begingroup$ That's Alice and Bob. Don't let the manbun fool you. $\endgroup$– AbigailNov 4, 2022 at 18:27
$\begingroup$
$\endgroup$
2
I once was working as a consulting company where we were writing software for a warehouse management system. One of the requirements was to generate pick lists that would optimize the loading of trucks. My manager came up with an algorithm that he thought would work. It turns out that what he came up with was really just the Bin-Packing Problem, which is known to be NP. He was not familiar with the concept of P and NP, but I was, and I was able to convince him that his solution would not scale, no matter how powerful the computer was that ran the algorithm. This probably save us several weeks of development time. We ended up implementing a heuristic based algorithm that was not optimal, but which worked well in practice.
-
$\begingroup$ It would be great to have more of those examples for courses covering this topic. Thanks for sharing. $\endgroup$– MichelNov 4, 2022 at 23:03
-
$\begingroup$ One problem was posted here that looked as if it had a greedy algorithm that worked quite well. It turned out the greedy algorithm worked in 99% of the cases, and would cut out a ton of work and leave a (usually much much smaller) NP complete problem. You really had to work hard to create instances that were "fully" NP complete. (What do I mean by that? Imagine something like the Travelling Salesman Problem, but with so many restrictions so that you can very often reduce a problem of size 1000 to a Travelling Salesman Problem of size 10). $\endgroup$ Nov 5, 2022 at 11:16
$\begingroup$
$\endgroup$
In my sens, Proving NP-Completeness of a problem, can let you try general solutions.
There are some general or maybe efficient (easy to implement and customize, more understandable or representative, scalable, a better parallel version) solutions for any problem. By term "general solutions", i mean interpolation, modeling, approximation, meta-heuristic search algorithms and optimization, ... vice versa.
Using these general solutions is reasonable only if you don't know the true solution or algorithm. So performing a research for proving that a problem is not a NP, or its solution could be approximated by easier algorithms with acceptable result, or it is reducible to some P algorithms, is a valuable effort. This value of this research is depended on use-case (problem), i.e. in a small company it is not valuable.
$\begingroup$
$\endgroup$
1
When you decide on a cryptographic scheme you want to know that cracking it is an NP complete problem --- that is, you want the encoding/decoding scheme you want to be as hard as possible to crack. For example, RSA encryption relies on the NP-complete problem of factoring (very large) numbers into their prime factors.
-
$\begingroup$ Factoring is not known to be $\mathsf{NP}$-complete. $\endgroup$ Nov 10, 2022 at 17:39