On Fast Heuristic Non-deterministic Algorithms and Short Heuristic Proofs

• Autorzy: Itsykson D. , Sokolov D.

Identyfikatory

DOI

10.3233/FI-2014-1036

• Języki publikacji: EN

Abstrakty

EN

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 pad_q (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}^∞_n=1 is an ensemble of distributions on strings, let D × U^q be a distribution on pairs (x, r), where x is distributed according to D_n 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 (pad_q (L), D × U^q) has a polynomially bounded heuristic proof system. Since graph non-isomorphism (GNI) is in AM, the above result is applicable to GNI.

Słowa kluczowe

EN

heuristic computation; proof systems; non-deterministic algorithm; Arthur-Merlin games

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 132, nr 1
• Strony: 113--129
• Opis fizyczny: Bibliogr. 18 poz.

Twórcy

autor

Itsykson D.

• Steklov Institute of Mathematics at St. Petersburg, 27 Fontanka, St. Petersburg, 191023, Russia

autor

Sokolov D.

• Steklov Institute of Mathematics at St. Petersburg, 27 Fontanka, St. Petersburg, 191023, Russia

Bibliografia

• [1] Bogdanov, A., Trevisan, L.: Average-Case Complexity, Foundation and Trends in Theoretical Computer Science, 2(1), 2006, 1–106.
• [2] van Dama, E., Muzychuk,M.: Some implications on amorphic association schemes, Journal of Combinatorial Theory, Series A, 117, 2010, 111–127.
• [3] Fortnow, L., Santhanam, R.: Hierarchy theorems for probabilistic polynomial time, Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, 2004.
• [4] Goldreich, O.: A Sample of Samplers: A Computational Perspective on Sampling, Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 6650, 2011.
• [5] Harnik, D., Kilian, J., Naor, M., Reingold, O., Rosen, A.: On Robust Combiners for Oblivious Transfer and other Primitives, Proc. of EUROCRYPT-2005, 2005.
• [6] Hirsch, E. A., Itsykson, D., Monakhov, I., Smal, A.: On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography, Theory of Computing Systems, 51(2), 2012, 179–195, Extended abstract appeared in the proceedings of STACS-2010. Preliminary version is available as ECCC TR10-193.
• [7] Hirsch, E. A., Itsykson, D. M., Nikolaenko, V. O., Smal, A. V.: Optimal heuristic algorithms for the image of an injective function, Journal of Mathematical Sciences, 188(1), 2013, 7–16.
• [8] Impagliazzo, R., Levin, L.: No better ways to generate hard NP instances than picking uniformly at random, Proceedings of the 31st IEEE Symposium on Foundations of Computer Science, 1990.
• [9] Impagliazzo, R., Zuckerman, D.: How to recycle random bits, Proceedings of the 30th Annual Symposium on Foundations of Computer Science, SFCS ’89, IEEE Computer Society, Washington, DC, USA, 1989, ISBN 0-8186-1982-1.
• [10] Itsykson, D. M.: Structural complexity of AvgBPP, Annals of Pure and Applied Logic, 162(3), 2010, 213–223.
• [11] Klivans, A. R., van Melkebeek, D.: Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses, Proceedings of the thirty-first annual ACM symposium on Theory of computing, STOC ’99, 1999, ISBN 1-58113-067-8.
• [12] Krajıček, J., Pudlák, P.: Propositional proof systems, the consistency of first order theories and the complexity of computations, The Journal of Symbolic Logic, 54(3), September 1989, 1063–1079.
• [13] Messner, J.: On Optimal Algorithms and Optimal Proof Systems, Proceedings of the 16th Symposium on Theoretical Aspects of Computer Science, 1563, 1999.
• [14] Papadimitriou, C., Zachos, S.: Two remarks on the power of counting, Proceedings of the 6th GI Conference on Theoretical Computer Science, 145, Springer-Verlag, Berlin, 1983.
• [15] Pervyshev, K.: On Heuristic Time Hierarchies, Proceedings of the IEEE Conference on Computational Complexity, 2007.
• [16] Schöning, U.: Probabilistic complexity classes and lowness, Journal of Computer and System Sciences, 39(1), 1989, 84–100.
• [17] Toda, S.: PP is as hard as the polynomial-time hierarchy, SIAM J. Comput., 20(5), October 1991, 865–877, ISSN 0097-5397.
• [18] Wagner, K. W.: The complexity of combinatorial problems with succinct input representation, Acta Inf., 23(3), June 1986, 325–356, ISSN 0001-5903.