scientific article; zbMATH DE number 7378368

DOI10.4230/LIPIcs.MFCS.2018.51MaRDI QIDQ5005153

Osamu Watanabe, Edith Hemaspaandra, Holger Spakowski, Hemaspaandra, Lane A.

Publication date: 4 August 2021

Full work available at URL: https://arxiv.org/abs/1711.01250

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

structural complexity theoryPP-lownessrobustness of counting classesthe legitimate deck problemthe reconstruction conjecture

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items

The robustness of LWPP and WPP, with an application to graph reconstruction

Cites Work

• Complexity results in graph reconstruction
• A low and a high hierarchy within NP
• Strong nondeterministic polynomial-time reducibilities
• The complexity of combinatorial problems with succinct input representation
• A uniform approach to define complexity classes
• Graph isomorphism is low for PP
• Complete sets and the polynomial-time hierarchy
• Gap-definable counting classes
• A complexity theory for feasible closure properties
• Quantum and classical complexity classes: Separations, collapses, and closure properties
• Parity, circuits, and the polynomial-time hierarchy
• The Boolean Hierarchy II: Applications
• THE RELATIONSHIP BETWEEN THE COMPUTATIONAL COMPLEXITIES OF THE LEGITIMATE DECK AND ISOMORPHISM PROBLEMS
• Graph reconstruction—a survey
• On the complexity of graph reconstruction
• Relativized Polynomial Time Hierarchies Having Exactly K Levels
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item