[[NP]] $\cap$ [[coNP]]. Settet av problemer hvor både ja- og nei-innstanser tillater vitner. Inneholder problemer som faktorisering, diskrete logaritmer, og elliptiske kurver—generelt [[Hidden subgroup problem]] (løst i kvantepolynom tid av [[Shors algoritme]]), [[Graph Isomorphism]] (løst av pseudopolynom klassisk algoritme, samt en algoritme i superposisjon av spacetimes? (Speaking of, hva er *den* kompleksitetsklassen for noe, og hvilken egenskaper har den? Spør Scott?) Men uvisst om i [[BQP]] eller ikke), [[Learning with errors]] og Approximate [[Shortest Vector Problem]] (muligens løst i kvantepolynom tid av [[Chens algoritme]]). [[Isogenies]]? Man antar at denne klassen *ikke* har noen komplette problemer. Formodning 1: [[NP snitt coNP]] $\subseteq$ [[BQP]]. Standard hypotese blant folk som utvikler [[Kvantealgoritmer]]? - Kanskje ikke. Fra [[BQP]], Complexity Zoo: «[NP](https://complexityzoo.net/Complexity_Zoo:N#np), and indeed [NP ∩ coNP](https://complexityzoo.net/Complexity_Zoo:N#npiconp), are not contained in BQP with probability 1 relative to a random oracle and a random permutation oracle, respectively ([BBB+97](https://complexityzoo.net/Zooref#bbb97)).» Formodning 2: Alle problemer i [[NP snitt coNP]] tillater pseudopolynome klassiske algoritmer. - Inspirert av Nadias talk ved [[PKC'24]], se [[12024-04-15]].