TY - JOUR

T1 - On fast heuristic non-deterministic algorithms and short heuristic proofs

AU - Itsykson, Dmitry

AU - Sokolov, Dmitry

PY - 2014

Y1 - 2014

N2 - 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) 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 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.

AB - 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) 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 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.

KW - Arthur-Merlin games

KW - heuristic computation

KW - non-deterministic algorithm

KW - proof systems

UR - http://www.scopus.com/inward/record.url?scp=84901808352&partnerID=8YFLogxK

U2 - 10.3233/FI-2014-1036

DO - 10.3233/FI-2014-1036

M3 - Article

AN - SCOPUS:84901808352

VL - 132

SP - 113

EP - 129

JO - Fundamenta Informaticae

JF - Fundamenta Informaticae

SN - 0169-2968

IS - 1

ER -