scientific article; zbMATH DE number 4007728

MaRDI QIDQ3758245zbMATH OpenFDO

Authors Uwe Schöning

Publication date 1987

zbMATH Keywords

NP-completenessgraph isomorphismlownessinteractive proof systemslow hierarchy

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Graph isomorphism is in the low hierarchy
• Graph isomorphism is low for PP
• scientific article; zbMATH DE number 512806
• Graph isomorphism is low for PP
• scientific article; zbMATH DE number 1500534

Cited in

(15)

• Reductions to graph isomorphism
• Confronting intractability via parameters
• scientific article; zbMATH DE number 477971 (Why is no real title available?)
• Isomorphic unordered labeled trees up to substitution ciphering
• Representing Groups on Graphs
• Search problems with a promise and graph isomorphism
• Structure in approximation classes
• Probabilistic complexity classes and lowness
• On hardness of one-way functions
• Graph isomorphism is in the low hierarchy
• Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes
• On computational complexity and honest polynomial degrees
• Computational complexity of computing symmetries in finite-domain planning
• Separating the low and high hierarchies by oracles
• Graph isomorphism is low for PP

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3758245)