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