Graph isomorphism is low for PP

DOI10.1007/3-540-55210-3_200zbMath1494.68200MaRDI QIDQ5096798

Johannes Köbler, Uwe Schoening, Jacobo Toran

Publication date: 18 August 2022

Published in: STACS 92 (Search for Journal in Brave)

Full work available at URL: http://nbn-resolving.de/urn:nbn:de:bsz:289-vts-69537

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

Related Items

Gap-definable counting classes, Realizability and uniqueness in graphs