3 ms·

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

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

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