On an optimal randomized acceptor for graph nonisomorphism

DOI10.1016/J.IPL.2011.11.013MaRDI QIDQ413276zbMATH OpenOpenAlexFDO

Authors 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 complexitygraph isomorphismoptimal algorithm

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1304339
• Optimal acceptors and optimal proof systems
• On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography
• Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses
• Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses

Cites work

• scientific article; zbMATH DE number 5081744 (Why is no real title available?)
• scientific article; zbMATH DE number 1342213 (Why is no real title available?)
• scientific article; zbMATH DE number 2080216 (Why is no real title available?)
• scientific article; zbMATH DE number 1929970 (Why is no real title available?)
• 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
• On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography
• Optimal acceptors and optimal proof systems
• Propositional proof systems, the consistency of first order theories and the complexity of computations

Cited in

(1)

• An algorithm for optimal isomorphism between two random graphs

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

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