Source: cirosantilli/np-intermediate
= NP-intermediate
{c}
{wiki}
This is the most interesting class of problems for <BQP> as we haven't proven that they are neither:
* <P (complexity)>: would be boring on quantum computer
* <NP-complete>: would likely be impossible on a quantum computer
Big list: https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/460#460