scientific article; zbMATH DE number 4007728

MaRDI QIDQ3758245zbMATH OpenFDO

Authors Uwe Schöning

Publication date 1987

zbMATH Keywords

graph isomorphisminteractive proof systemslow hierarchylownessNP-completeness

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

(16)

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

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)