On fast heuristic non-deterministic algorithms and short heuristic proofs

DOI10.3233/FI-2014-1036MaRDI QIDQ2934878zbMATH OpenOpenAlexFDO

Authors Dmitry Itsykson, Dmitry Sokolov

Publication date 22 December 2014

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3233/fi-2014-1036

zbMATH Keywords

Arthur-Merlin gamesheuristic computationnon-deterministic algorithmproof systems

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• 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
• Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
• Probabilistic checking of proofs

Cited in

(2)

• scientific article; zbMATH DE number 5999718 (Why is no real title available?)
• Circuit lower bounds for average-case MA

This page was built for publication: On fast heuristic non-deterministic algorithms and short heuristic proofs

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