by

Ciro Santilli (@cirosantilli, 36)

NP-intermediate

This is the most interesting class of problems for BQP as we haven't proven that they are neither:

P: would be boring on quantum computer
NP-complete: would likely be impossible on a quantum computer

Big list: cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/460#460

Table of contents
- BQP NP-intermediate

BQP

 1  0 

P for quantum computing!

Heck, we know nothing about this class yet related to non quantum classes!

conjectured not to intersect with NP-complete, because if it were, all NP-complete problems could be solved efficiently on quantum computers, and none has been found so far as of 2020.
conjectured to be larger than P, but we don't have a single algorithm provenly there:
- it is believed that the NP complete ones can't be solved
- if they were neither NP-complete nor P, it would imply P != NP
we just don't know if it is even contained inside NP!

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic + Create my own version