3 ms·

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 N

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.

wtallis 2y ago
> 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.
- eru 2y ago
  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.
  - deleted 2y ago
    [deleted]
  - jvanderbot 2y ago
    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).
    - eru 2y ago
      > [...] 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.)
nullc 2y ago
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).

wtallis 2y ago

> 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.

eru 2y ago
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.
- deleted 2y ago
  [deleted]
- jvanderbot 2y ago
  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).
  - eru 2y ago
    > [...] 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.)

nullc 2y ago

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).