- Er i [NP snitt coNP](https://complexityzoo.net/Complexity_Zoo:N#npiconp) - Merk: *"Is not believed to contain complete problems."* - Idé: bruke mapping fra [klassiske harmoniske oscillatorer](https://arxiv.org/pdf/2303.13012.pdf) til å finne en ny infallsvinkel til problemet. - Gitt BQP-completeness, så *eksisterer* en slik mapping, simpelthen ved å implementere klassiske grafisomorfialgoritmer. - Disse vil mest sannsynlig ikke være effektive, men å finne dem kan være et godt første steg til å se en vei videre til effektivisering—eller alternativt, oppnå en forståelse for hvorfor denne fremgangsmåten leder til en blindvei. - Beste klassiske algoritmer (src: GPT4) - GPT4: *For many practical cases, graph isomorphism can be solved efficiently. Algorithms like the Weisfeiler-Lehman test and its iterations can handle many graphs quickly.* - GPT4: *A significant development came in 2015 when László Babai introduced an algorithm that solves the graph isomorphism problem in quasipolynomial time.* - [Complexity Zoo](https://complexityzoo.net/Complexity_Garden#graph_isomorphism): *Combining Luks' algorithm with a trick due to Zemlyachenko yields a time complexity upper bound of $2^{O(\sqrt{v \log v})}$ for graphs with v vertices. However, some practical Graph Isomorphism algorithms, such as NAUTY, seem to run much faster than this rigorous upper bound.* Andre interessante problemer i NP $\cap$ coNP: - [Approximate Shortest Vector Lattice (SVP?)](https://complexityzoo.net/Complexity_Garden#approximate_shortest_lattice_vector) - [First player advantage](https://complexityzoo.net/Complexity_Garden#stochastic_games) - Denne minner jo litt om det glued-graphs-problemet som ble løst av klassiske harmoniske oscillatorer, se [paper](https://arxiv.org/pdf/2303.13012.pdf). Påstått løst i [[Superposition over spacetimes]].