Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > HEURISTIC COMPUTATIONS:
Reports tagged with heuristic computations:
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 >>>


TR11-091 | 20th May 2011
Edward Hirsch, Dmitry Itsykson, Valeria Nikolaenko, Alexander Smal

Optimal heuristic algorithms for the image of an injective function

The existence of optimal algorithms is not known for any decision problem in NP$\setminus$P. We consider the problem of testing the membership in the image of an injective function. We construct optimal heuristic algorithms for this problem in both randomized and deterministic settings (a heuristic algorithm can err on a ... more >>>




ISSN 1433-8092 | Imprint