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:52

>>12
but if you don't know whether a problem X is NP-hard, literally the easiest way to prove it is by assuming you have an oracle that solves it in P and check if it allows you to solve an NP-hard problem in P. if it does, X is NP-hard. and proving that X is NP-hard has its practical uses, i.e. in designing public-key encryption schemes.

also, science doesn't have to be directly applicable in practice to be useful. the fact that pi is irrational also doesn't affect your life, but it is a basis of other things in mathematics which in turn are a basis of other things in physics, engineering etc. and those things do affect your life.

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