QED

Scott Aaronson wijst op een leuke easter egg op de homepage van de universiteit van Bristol. Daar staat namelijk een foto van een schoolbord met het volgende op geschreven:

NP ⊂ BQP, but the proof is too small to fit on this blackboard.

Weer een mooie parodie op Fermat, en op de wikipagina van Complexity Zoo over NP staat er nog eentje:

NP contains P. I’ve discovered a marvelous proof that NP and P are unequal, but this web page is too small to contain it. Too bad, since otherwise I’d be eligible for $1,000,000 [CMI00].

NP is de klasse van beslisproblemen die door een niet-deterministische polynomiale Turingmachine kunnen opgelost worden, terwijl BQP de klasse van beslisproblemen is die in polynomiale tijd kunnen opgelost worden door een kwantum Turingmachine met een maximale foutkans van 1/3. De relatie tussen NP en BQP is een onopgelost probleem, net zoals de P = NP vraag waarvoor het Clay Mathematics Institute een miljoen dollar heeft uitgeloofd.