caa a22 4500 469033967 CHVBK 20180323132751.0 cr unu---uuuuu 170328e19921201xx s 000 0 eng 10.1007/BF01200427 doi (NATIONALLICENCE)springer-10.1007/BF01200427 Graph isomorphism is low for PP [Elektronische Daten] [Johannes Köbler, Uwe Schöning, Jacobo Torán] We show that the graph isomorphism problem, is low for PP and for C=P, i.e., it does not provide a PP or C=P computation with any additional power when used as an oracle. Furthermore, we show that graph isomorphism belongs to the class LWPP (see Fenner, Fortnow, Kurtz [12]). A similar result holds for the (apparently more difficult) problem Group Factorization. The problem of determining whether a given graph has a nontrivial automorphism, Graph Automorphism, is shown to be in SPP, and is therefore low for PP, C=P, and Mod k P,k≥2. Birkhäuser Verlag, 1992 graph isomorphism nationallicence complexity classes nationallicence lowness nationallicence counting properties nationallicence 68Q15 nationallicence 68Q25 nationallicence 05C60 nationallicence 68R10 nationallicence Köbler Johannes Theoretische Informatik, Universität Ulm Oberer Eselsberg, D-W-7900, Ulm, Germany aut Schöning Uwe Theoretische Informatik, Universität Ulm Oberer Eselsberg, D-W-7900, Ulm, Germany aut Torán Jacobo Departamento L.S.I., Universitat Politècnica de Catalunya, Pau Gargallo 5, E-08028, Barcelona, Spain aut computational complexity Birkhäuser-Verlag 2/4(1992-12-01), 301-330 1016-3328 2:4<301 1992 2 37 https://doi.org/10.1007/BF01200427 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF01200427 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Köbler Johannes Theoretische Informatik, Universität Ulm Oberer Eselsberg, D-W-7900, Ulm, Germany aut NATIONALLICENCE 700 1- Schöning Uwe Theoretische Informatik, Universität Ulm Oberer Eselsberg, D-W-7900, Ulm, Germany aut NATIONALLICENCE 700 1- Torán Jacobo Departamento L.S.I., Universitat Politècnica de Catalunya, Pau Gargallo 5, E-08028, Barcelona, Spain aut NATIONALLICENCE 773 0- computational complexity Birkhäuser-Verlag 2/4(1992-12-01), 301-330 1016-3328 2:4<301 1992 2 37 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer