Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > OPTIMAL ALGORITHM:
Reports tagged with Optimal Algorithm:
TR05-054 | 19th May 2005
Konstantin Pervyshev

#### Time Hierarchies for Computations with a Bit of Advice

A polynomial time hierarchy for ZPTime with one bit of advice is proved. That is for any constants a and b such that 1 < a < b, ZPTime[n^a]/1 \subsetneq ZPTime[n^b]/1.

The technique introduced in this paper is very general and gives the same hierarchy for NTime \cap coNTime, UTime, ... more >>>

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