scientific article; zbMATH DE number 512806

MaRDI QIDQ4281499zbMATH OpenFDO

Authors Antoni Lozano, Jacobo Torán

Publication date 7 April 1994

zbMATH Keywords

complexity classesgraph automorphismgraph isomorphismnonuniform complexitypolynomial-time reducibilitiessparse setstruth-table reducible

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Reductions to Graph Isomorphism
• On the Hardness of Graph Isomorphism
• Reductions to graph isomorphism
• scientific article; zbMATH DE number 477971

Cited in

(15)

• On the reducibility of sets inside NP to sets with low information content
• Graph Isomorphism is in SPP
• On the Complexity of Matroid Isomorphism Problems
• scientific article; zbMATH DE number 3968624 (Why is no real title available?)
• scientific article; zbMATH DE number 4007728 (Why is no real title available?)
• scientific article; zbMATH DE number 1332674 (Why is no real title available?)
• scientific article; zbMATH DE number 477971 (Why is no real title available?)
• On the Hardness of Graph Isomorphism
• scientific article; zbMATH DE number 2086379 (Why is no real title available?)
• The complexity of generating test instances
• Reductions to Graph Isomorphism
• A language-dependent cryptographic primitive
• On the generic complexity of the searching graph isomorphism problem
• On the asymmetric complexity of the group-intersection problem
• 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 Q4281499)