On an optimal randomized acceptor for graph nonisomorphism

DOI10.1016/J.IPL.2011.11.013zbMATH Open1237.68083OpenAlexW2096321451MaRDI QIDQ413276FDOQ413276

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

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

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)

Cites Work

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

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)