Graph isomorphism is low for PP
type: Item
instance of: scholarly article
title: Graph isomorphism is low for PP
zbMATH Open document ID: 0770.68055
DOI: 10.1007/BF01200427
author: Johannes Köbler
author: Uwe Schöning
author: Jacobo Torán
published in: Computational Complexity
publication date: 1993-09-16T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C60
zbMATH DE Number: 179057
zbMATH Keywords: graph isomorphism
MaRDI profile type: Publication
cites work: Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
cites work: Counting classes: Thresholds, parity, mods, and fewness
cites work: Probabilistic polynomial time is closed under parity reductions
cites work: Does co-NP have short interactive proofs ?
cites work: The complexity of promise problems with applications to public-key cryptography
cites work: Q3912839
cites work: Q4198056
cites work: Computational Complexity of Probabilistic Turing Machines
cites work: The Knowledge Complexity of Interactive Proof Systems
cites work: On the power of deterministic reductions to C=P
cites work: Q3253828
cites work: Relations among MOD-classes
cites work: Group-theoretic algorithms and graph isomorphism
cites work: Subcomplete generalizations of graph isomorphism
cites work: A compact representation for permutation groups
cites work: The NP-completeness column: an ongoing guide
cites work: Q4266533
cites work: Turing machines with few accepting computations and low sets for PP
cites work: Isomorphism of graphs of bounded valence can be tested in polynomial time
cites work: A note on the graph isomorphism counting problem
cites work: Graph isomorphism is in the low hierarchy
cites work: PP is as Hard as the Polynomial-Time Hierarchy
cites work: Complexity classes defined by counting quantifiers
cites work: Relative complexity of checking and evaluating
cites work: The complexity of computing the permanent
cites work: NP is as easy as detecting unique solutions
cites work: The complexity of combinatorial problems with succinct input representation
full work available at URL: https://doi.org/10.1007/bf01200427
OpenAlex ID: W2365765272
Recommended article: Graph isomorphism is low for PP
Recommended article: Q4501553
Recommended article: Graph isomorphism is in the low hierarchy
Recommended article: Q3758245
Recommended article: Q4302454
Recommended article: Graph Isomorphism is in SPP
Recommended article: LOWER BOUNDS FOR SUBGRAPH ISOMORPHISM
Recommended article: P3-isomorphisms for graphs
Recommended article: Reductions to graph isomorphism
Recommended article: Reductions to Graph Isomorphism
description: scientific article; zbMATH DE number 179057