On Fast Heuristic Non-deterministic Algorithms and Short Heuristic Proofs
Dmitry Itsykson, Dmitry Sokolov · Fundamenta Informaticae · 2014
In this paper we study heuristic proof systems and heuristic non-deterministic algorithms. We give an example of a language Y and a polynomial-time samplable distribution D such that the distributional problem (Y, D) belongs to the complexity class H