The robustness of LWPP and WPP, with an application to graph reconstruction
From MaRDI portal
Publication:2027204
DOI10.1007/s00037-020-00197-5zbMath1503.68074MaRDI QIDQ2027204
Hemaspaandra, Lane A., Edith Hemaspaandra, Osamu Watanabe, Holger Spakowski
Publication date: 25 May 2021
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/9633/
reconstruction conjecture; structural complexity theory; legitimate deck problem; PP-lowness; robustness of counting classes
68R10: Graph theory (including graph drawing) in computer science
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)