2 ms·

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 sequen

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