Hacker News Reader

Comment by Epa095 | Hacker News Reader

This is a cool article! And it lead me down the path to another cool factorio compsci paper called 'The steady-states of splitter networks' where they really go into the theoretical properties of the belts and splitters.

But I can't help to feel that the following paragraph should be removed, since it really seems to be a bit confused about the concepts of both Np-complete and NP-hard.

> Finding a feasible solution is NP-hard because we can't do any better than start placing the components on a 2D grid and check if the properties are respected. Furthermore, finding the optimal solution (i.e., minimum number of components) is NP-complete because it will require enumerating all the possible solutions in order to find the best one.

View on HN

It's a classic undergraduate student mistake when learning computational complexity: "this problem is really hard, but I can represent it as SAT - well, it is NP-hard!". Whereas what you need is to represent SAT as an instance of your problem! Otherwise computing XOR of two bits would be NP-hard, as I can write a SAT formula to express it.

> we can't do any better than start placing the components on a 2D grid and check if the properties are respected

That specifically seems to be the bit where the explanation goes wrong. Proving that there's no easier method than brute forcing is a hard problem, not something to wave away as an exercise for the reader.

Actually, you can wave it away as an exercise to the reader, you just need to be careful how you formulate it.

Something like 'Frobbing the fnutz might be NP-hard. The proof via reduction of SAT is left as an exercise for the reader.'

Not very reader friendly, but at least you haven't said anything wrong.

For anyone curious (and testing my recall), this should just mean: Solve a SAT problem using fnutz that are Frobbed correctly.

e.g., "Just set up a belt sequence that would solve a 3-SAT problem" to show that belt sequencing is at least as hard as 3-SAT.

(The reverse, setting up a SAT solver to solve belt sequencing only shows that SAT is at least as hard as belt sequencing, which is true for any problem that's not hard hard).

> [...] which is true for any problem that's not hard hard.

Yes, basically true for any problem where you can verify a correct answer in polynomial time (especially if someone gives you extra hints to help your verification).

You can also think of these 'hints' as 'extremely lucky guesses'.

Eg you can verify that a number is composite, and not prime, by 'guessing' its prime factors.

Or you can guess the solution to a Sudoku and then just verify it.

The traveling salesman problem is interesting: it's trivial to verify that any given candidate solution has a specific cost (and that cost can be very low), but it's not trivial to verify that the candidate is minimal. (I'm not even sure it's possible in polynomial time.)

Even when you get the direction correct-- e.g. that you could encode an arbitrary SAT problem as an instance of your problem... that doesn't mean that in practice most instances of your problem can't be solved to an arbitrarily good approximation quickly or even solved optimally in a reasonable amount of time. It only means that in the worst case there is no efficient optimal solution or good approximation.

I've repeatedly encountered people using crappy solutions to problems because they read some result from complexity theory that made them think they couldn't do better. .. when in reality a slightly smarter algorithm does much better on average.

Consider for example the min cover problem: You have a set of bit vectors and you want to find the minimum collection where at least one vector is true for every bit. (e.g. optimizing a collection of tests). There is a simple greedy algorithm-- include the vector that covers the most yet-uncovered bits. There is a proof that this algorithm achieves the best possible worst case approximation error.

But in practice this is a useless result. Worst case approximation error is driven by pathological inputs. It's easy to come up with modifications of the greedy algorithm that significantly improve the quality of the solutions on average (or at least do in the sorts of real problems I've applied it to).

Yes, "NP-complete" is not correct on the author's part and neither is "NP-hard." "NP-hard" is the author's intent since the problem is solvable using a SAT solver but presumably has no polynomial algorithm (so it is harder than P but not as hard as NP), but NP-hardness actually requires the other direction to be true: for a problem to be NP-hard, an oracle for the problem needs to be able to solve everything in NP. NP-complete is a stricter condition that requires NP-hardness but also requires that the problem be in NP.

The author was missing the words "in NP" if they are talking about complexity.

Thanks for the feedback, I fixed the claims about complexity. Let me know if you find other incorrect parts.

Reply on news.ycombinator.com