Graph Isomorphism is in the Low Hierarchy

By Uwe Schöning. 1987

Subfields: Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Algorithms & Complexity

1. B. Douglas
2. Josep Díaz
3. Joaquim Gabarró
4. Vikraman Arvind
5. Piyush P. Kurur

Citations in the corpus

• The Weisfeiler-Lehman Method and Graph Isomorphism Testing (2011, background): “Further supporting evidence is provided by Schöning [30], who demonstrates that GI is not NP-”
• Structural Complexity II (2012, methodology): “In 1974 the concept of random access machine was extended to include the processing of huge data (Pratt, Rabin, and Stockmeyer (1974), Hartmanis and Simon (1974».”
• Graph isomorphism is in SPP (2002, background): “It follows that GI cannot be NPcomplete unless the polynomial hierarchy collapses to p2 [6, 18].”