Affiliations: Steklov Institute of Mathematics at St. Petersburg, 27 Fontanka, St.Petersburg, 191023, Russia. dmitrits@pdmi.ras.ru, sokolov.dmt@gmail.com
Note: [] The work is partially supported by the Ministry of education and science of Russian Federation, project 8216, the president grants MK-4108.2012.1, by RFBR grants 12-01-31239 mol_a and by RAS Program for Fundamental Research. Address for correspondence: Steklov Institute of Mathematics at St. Petersburg, 27 Fontanka, St.Petersburg, 191023, Russia
Note: [] The work is partially supported by the Ministry of education and science of Russian Federation, project 8216, the president grants MK-4108.2012.1, by RFBR grants 12-01-31239 mol a and by RAS Program for Fundamental Research.
Abstract: 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 HeurNP but Y ∉ NP if NP ≠ coNP, and (Y, D) ∉ HeurBPP if (NP,PSamp) $\nsubseteq$ HeurBPP. For a language L and a polynomial q we define the language padq(L) composed of pairs (x, r) where x is an element of L and r is an arbitrary binary string of length at least q(|x|). If $D = \{D_n\}^\infty_{n=1}$ is an ensemble of distributions on strings, let D × Uq be a distribution on pairs (x, r), where x is distributed according to Dn and r is uniformly distributed on strings of length q(n). We show that for every language L in AM there is a polynomial q such that for every distribution D concentrated on the complement of L the distributional problem (padq(L), D × Uq) has a polynomially bounded heuristic proof system. Since graph non-isomorphism (GNI) is in AM, the above result is applicable to GNI.
Keywords: heuristic computation, proof systems, non-deterministic algorithm, Arthur-Merlin games
