Next Big Future on quantum computation

Robert J. Hansen rjh at
Tue Jul 28 00:01:26 CEST 2015

> Point blank: quantum computers cannot solve NP-Hard problems.  Period,
> end of sentence.  NP-Hard is where the ridiculously difficult problems
> live.

For those who like pedantry: NP-Hard is the name given to any problem
that is as hard, or harder, than any problem in NP.  The Traveling
Salesman Problem is NP, and is known to be as hard as any problem in NP,
therefore it's NP-Hard.

But it's also the *easiest* NP-Hard.

Because remember, NP-Hard is anything as hard *or harder* than anything
in NP.  Playing a perfect game of Go isn't in NP, ergo playing a perfect
game of Go is NP-Hard.  NP-Hard is a collective term that covers a truly
staggering amount of terrain, going from the "easy" problems like
traveling salesman all the way up to the "are you kidding me?" like
reversing entropy.

Few computer scientists like talking about NP-Hard.  It's simply too big
of a space.  And if anyone seriously talks about a general technique
that works on NP-Hard problems, they get laughed at.  Lots.  Because
there isn't one, and we've formally proven there isn't one.  This was
the proof that made Alan Turing famous.

More information about the Gnupg-users mailing list