Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

How NP-hard can you get‽‽!!?

Name: Anonymous 2017-02-01 10:44

I'm reading http://www.scottaaronson.com/papers/pnp.pdf and I'm NP-hard right now! My 3-SAT scores are off the chart. I've counted my Hamilton cycles twice in an hour.

Please help, I'm so NP-hard but I need to P!

Name: Anonymous 2017-02-01 14:29

>>9
it's a setup for proof by contradiction, which is very common in mathematics, and it's the very same way of reasoning that gave us proof of undecidability of halting problem (the same proof that required the creation of turing machines).

an oracle means just 'assume we can solve X in P', which may be false. then we look for the consequences of such assumption - if it allows solving Y in P then it means X is as hard as Y. how is that different from, say, a proof of irrationality of pi which starts from the assumption that pi is rational and then decides that it actually isn't?

Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List