What would you do with a solution to 3-SAT?

Alex Flint

Many experts suspect that there is no polynomial-time solution to the so-called NP-complete problems, though no-one has yet been able to rigorously prove this and there remains the possibility that a polynomial-time algorithm will one day emerge. However unlikely this is, today I would like to invite LW to play a game I played with with some colleagues called what-would-you-do-with-a-polynomial-time-solution-to-3SAT? 3SAT is, of course, one of the most famous of the NP-complete problems and a solution to 3SAT would also constitute a solution to *all* the problems in NP. This includes lots of fun planning problems (e.g. travelling salesman) as well as the problem of performing exact inference in (general) Bayesian networks. What's the most fun you could have?

Conway's game of life.

Edit: In particular it allows for perpetual motion machines.

I have this vague impression that makes me think of life as "cheating" by "running backwards".

In our own universe, quantum coin-flips make it look like one state can lead to more than one new state, and the universe "picks one". However, this "picking" operation is unnecessary and we say "they all happen" and just consider it one (larger) state evolving into one new (larger) state. This makes me wonder why you can't do the same thing for every set of laws that claims not to be a bijection between states.

I... (read more)

4SilasBarta15y

There are unreachable states ("gardens of Eden" in the lingo) which means that (per the Garden of Eden Theorem) there exist states which are the successor of more than one possible state. This is an irreversibility (you cannot infer the previous state from the present one), implying an increase of entropy. The perpetual motion machines you refer to are only that in a very metaphorical sense -- they don't allow an infinite extraction (edit: should be "increase") of some energy-like metric. They just cycle between the same states, neither increasing nor decreasing entropy because of the full reversibility of such systems.