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

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!

We’re asking whether, under the above conditions, there’s a general method to find a valid solution whenever one exists, and which is enormously faster than just trying all the possibilities one by one, from now till the end of the universe, like in Jorge Luis Borges’ Library of Babel

why do comp-sci people like this story so much? Tlon Uqbar Orbis Tertius was better

P != NP, stop wasting time in this fantasyland.

P = NP iff N = 1 or P = 0

P = NP yiff N = 1 or P = 0

P = NP lets see these guys implement diff N = 1 or P = 0

The P=NP debacle shows how even ``research'' literally about oracles and fates can actually receive funding in CS. That's as if physicists came asking for grants to study the demon of Maxwell or if NASA started a "send a spaceship to find God" program.

>>7
what is metaphor?

>>8
Unfortunately it's not metaphor, the whole nature of the P=NP idea is "what if there was an oracle that would tell us the answer in polynomial time so we wouldn't have to look for the answer ourselves".

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

prove those dubs

>>10
But no oracles exist or ever existed for any NP-hard problems anyone ever solved, and it would highly wishful thinking that they will appear and start telling our computers the answers. It's more probable that the Sun will explode or that we will all grow purple nuts than that an 'oracle' can exist. So what they are getting money for is trying to prove that the thing that in all possibility cannot exist doesn't exist... A total waste of taxpayer money. We can all go on with our lives in the belief that P != NP without their pointless ``CS research''.

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

>>12
You're right, we should be giving that taxpayer money to niggers so they can buy more crack and guns.

>>13
Proving a concrete problem is NP-hard is practical, but proving that P != NP in the general case is useless since it is so obviously true. That's what they're wasting time on, not real-world NP-hard problems.

which in turn are a basis of other things in physics, engineering etc

As far as physics and engineering are concerned, pi is rational, because it's always used with finite precision in all practical calculations. Thus, transcendentality of pi has resoundingly loudly NO implications for any of our lives, otherwise we wouldn't be able to get away with approximating it as a rational.

>>14
False dichotomy. Give it to the space exploration people so they can build asterioid mining robots.

P, NP, who cares

We have more important problems to solve than this P NP crap, for example the dubsless primes problem:

http://bbs.progrider.org/prog/read/1458399797

This thread makes my NP hard. Bend over girls.