On an optimal randomized acceptor for graph nonisomorphism

DOI10.1016/j.ipl.2011.11.013zbMath1237.68083OpenAlexW2096321451MaRDI QIDQ413276

Edward A. Hirsch, Dmitry Itsykson

Publication date: 4 May 2012

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2011.11.013

zbMATH Keywords

computational complexityoptimal algorithmgraph isomorphism

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Logic in computer science (03B70) Graph algorithms (graph-theoretic aspects) (05C85) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography
• Propositional proof systems, the consistency of first order theories and the complexity of computations
• Optimal Acceptors and Optimal Proof Systems
• A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
• Consequences of the provability of NP ⊆ P/poly
• Hard Instances of Algorithms and Proof Systems

This page was built for publication: On an optimal randomized acceptor for graph nonisomorphism