Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Ivan Monakhov:

TR10-193 | 5th December 2010
Edward Hirsch, Dmitry Itsykson, Ivan Monakhov, Alexander Smal

On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography

The existence of an optimal propositional proof system is a major open question in proof complexity; many people conjecture that such systems do not exist. Krajicek and Pudlak (1989) show that this question is equivalent to the existence of an algorithm that is optimal on all propositional tautologies. Monroe (2009) ... more >>>

ISSN 1433-8092 | Imprint