On fast heuristic non-deterministic algorithms and short heuristic proofs
DOI10.3233/FI-2014-1036zbMATH Open1318.68086OpenAlexW2124759116MaRDI QIDQ2934878FDOQ2934878
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
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
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cited In (2)
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)
