scientific article; zbMATH DE number 4007728

zbMATH Open0621.68034MaRDI QIDQ3758245FDOQ3758245

Uwe Schöning

Publication date: 1987

Title of this publication is not available (Why is that?)

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

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)

Cited In (13)

• Isomorphic unordered labeled trees up to substitution ciphering
• Computational Complexity of Computing Symmetries in Finite-Domain Planning
• On computational complexity and honest polynomial degrees
• On hardness of one-way functions
• Confronting intractability via parameters
• Separating the low and high hierarchies by oracles
• Title not available (Why is that?)
• Structure in approximation classes
• Representing Groups on Graphs
• Graph isomorphism is in the low hierarchy
• Probabilistic complexity classes and lowness
• Graph isomorphism is low for PP
• Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes

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)