{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2021,11,30]],"date-time":"2021-11-30T16:29:18Z","timestamp":1638289758355},"reference-count":99,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[1998,5]]},"abstract":"\n We show that every language in NP has a probablistic verifier that checks membership proofs for it using logarithmic number of random bits and by examining a\n constant<\/jats:italic>\n number of bits in the proof. If a string is in the language, then there exists a proof such that the verifier accepts with probability 1 (i.e., for every choice of its random string). For strings not in the language, the verifier rejects every provided \u201cproof\u201d with probability at least 1\/2. Our result builds upon and improves a recent result of Arora and Safra [1998] whose verifiers examine a nonconstant number of bits in the proof (though this number is a very slowly growing function of the input length).\n <\/jats:p>\n \n As a consequence, we prove that no MAX SNP-hard problem has a polynomial time approximation scheme, unless NP = P. The class MAX SNP was defined by Papadimitriou and Yannakakis [1991] and hard problems for this class include vertex cover, maximum satisfiability, maximum cut, metric TSP, Steiner trees and shortest superstring. We also improve upon the clique hardness results of Feige et al. [1996] and Arora and Safra [1998] and show that there exists a positive \u03b5 such that approximating the maximum clique size in an\n N<\/jats:italic>\n -vertex graph to within a factor of\n N<\/jats:italic>\n \u03b5<\/jats:sup>\n is NP-hard.\n <\/jats:p>","DOI":"10.1145\/278298.278306","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:25:57Z","timestamp":1027769157000},"page":"501-555","source":"Crossref","is-referenced-by-count":731,"title":["Proof verification and the hardness of approximation problems"],"prefix":"10.1145","volume":"45","author":[{"given":"Sanjeev","family":"Arora","sequence":"first","affiliation":[{"name":"Princeton Univ., Princeton, NJ"}]},{"given":"Carsten","family":"Lund","sequence":"additional","affiliation":[{"name":"AT&T Bell Labs, Murray Hill, NJ"}]},{"given":"Rajeev","family":"Motwani","sequence":"additional","affiliation":[{"name":"Stanford Univ., Stanford, CA"}]},{"given":"Madhu","family":"Sudan","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge"}]},{"given":"Mario","family":"Szegedy","sequence":"additional","affiliation":[{"name":"AT&T Bell Labs, Murray Hill, NJ"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_1","unstructured":"ARORA S. 1994. Probabilistic checking of proofs and hardness of approximation problems. Ph.D dissertation. Univ. California Berkeley Berkeley Calif. Available from http:\/\/www.cs.princeton. edu\/-arora. ARORA S. 1994. Probabilistic checking of proofs and hardness of approximation problems. Ph.D dissertation. Univ. California Berkeley Berkeley Calif. Available from http:\/\/www.cs.princeton. edu\/-arora."},{"key":"e_1_2_1_2_1","first-page":"2","volume-title":"Proceedings of the 37th IEEE Symposium on Foundations of Computer Sciences. IEEE","author":"ARORA S."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1472"},{"key":"e_1_2_1_4_1","first-page":"339","volume-title":"Approximation Algorithms for NP-Hard Problems","author":"ARORA S."},{"key":"e_1_2_1_5_1","unstructured":"ARORA S. MOTWANI R. SAFRA S. SUDAN M. AND SZEGEDY M. 1992. PCP and approximation problems. Unpublished note. ARORA S. MOTWANI R. SAFRA S. SUDAN M. AND SZEGEDY M. 1992. PCP and approximation problems. Unpublished note."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"e_1_2_1_7_1","first-page":"485","volume-title":"Proceedings of the 29th Annual ACM Symposium on Theory of Computing (El Paso, Tex., May 4-6). ACM","author":"ARORA S."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90046-X"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90006-7"},{"key":"e_1_2_1_10_1","first-page":"421","volume-title":"Proceedings of the 17th Annual ACM Symposium on Theory of Computing (Providence, R.I., May 6-8). ACM","author":"BABAI L."},{"key":"e_1_2_1_11_1","series-title":"Lecture Notes in Computer Science","first-page":"525","volume-title":"Proceedings of the lOth Annual Symposium on Theoretical Aspects of Computer Science","author":"BABAI L."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200057"},{"key":"e_1_2_1_13_1","first-page":"21","volume-title":"Proceedings of the 23rd Annual ACM Symposium on Theory of Computing (New Orleans, La., May 6-8). ACM","author":"BABAI L."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200056"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90028-1"},{"key":"e_1_2_1_17_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 7th Annual Symposium on Theoretical Aspects of Computer Science","author":"BEAVER D."},{"key":"e_1_2_1_18_1","first-page":"266","volume-title":"Proceedings of the 2nd Israel Symposium on Theory and Computing Systems. IEEE Computer Society Press, Los Alamitos, Calif.","author":"BELLARE M."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.556674"},{"key":"e_1_2_1_20_1","first-page":"422","volume-title":"IEEE","author":"BELLARE M.","year":"1995"},{"key":"e_1_2_1_21_1","first-page":"294","article-title":"\/1994. Efficient probabilistically checkable proofs and applications to approximation. In Proceedings of the 25th Annual ACM Symposium on the Theory of Computing (San Diego, Calif., May 16-18). ACM","volume":"1993","author":"BELLARE M.","year":"1993","journal-title":"New York"},{"key":"e_1_2_1_22_1","first-page":"3","article-title":"\/1995. The complexity of approximating a nonlinear program","volume":"69","author":"BELLARE M.","year":"1993","journal-title":"J. Math. Prog. B"},{"key":"e_1_2_1_23_1","first-page":"184","volume-title":"Proceedings of the 26th Annual ACM Symposium on the Theory of Computing (Montreal, Que., Canada, May 23-25)","author":"BELLARE M.","year":"1950"},{"key":"e_1_2_1_24_1","first-page":"113","volume-title":"Proceedings of the 20th Annual ACM Symposium on Theory of Computing","author":"BEN-OR M."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90056-L"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90039-2"},{"key":"e_1_2_1_27_1","series-title":"Lecture Notes in Computer Science","first-page":"1","volume-title":"Proceedings of FST&TCS","author":"BLUM M."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/179812.179818"},{"key":"e_1_2_1_29_1","first-page":"86","volume-title":"Proceedings of the 21st Annual Symposium on the Theory of Computing","author":"BLUM M."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90044-W"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80026-1"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 30th Annual Symposium on the Foundations of Computer Science. IEEE","author":"COHEN A."},{"key":"e_1_2_1_33_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 8th Annual Symposium on Theoretical Aspects of Computer Science","author":"CONDON A."},{"key":"e_1_2_1_34_1","first-page":"305","volume-title":"Proceedings of the 25th Annual ACM Symposium on the Theory of Computing","author":"CONDON A."},{"key":"e_1_2_1_35_1","first-page":"2","article-title":"Random debaters and the hardness of approximating stochastic functions","volume":"26","author":"CONDON A.","year":"1996","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_36_1","first-page":"151","volume-title":"Proceedings of the 3rd Annual ACM Symposium on Theory of Computing"},{"key":"e_1_2_1_37_1","unstructured":"CRESCENZI P. AND KANN V. 1995. A compendium of NP optimization problems. Tech. Rep. SI\/RR-95\/02 Dipartimento di Scienze dell'Informazione Uinversita di Roma \"La Sapienza\". The list is updated continuously. (The latest version is available by anonymous ftp from nada.kth.se as Theory\/Viggo-Kann\/compendium.ps.Z.) CRESCENZI P. AND KANN V. 1995. A compendium of NP optimization problems. Tech. Rep. SI\/RR-95\/02 Dipartimento di Scienze dell'Informazione Uinversita di Roma \"La Sapienza\". The list is updated continuously. (The latest version is available by anonymous ftp from nada.kth.se as Theory\/Viggo-Kann\/compendium.ps.Z.)"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792225297"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579456"},{"key":"e_1_2_1_40_1","volume-title":"Com-plexity of Computation, Richard Karp, ed","author":"FAGIN R."},{"key":"e_1_2_1_41_1","first-page":"314","volume-title":"Proceedings of the 28th Annual Symposium on the Theory of Computing","author":"FEIGE U."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/226643.226652"},{"key":"e_1_2_1_43_1","first-page":"172","volume-title":"Proceedings of the 26th Annual ACM Symposium on the Theory of Computing (Montreal, Que., Canada, May 23-25)","author":"FEIGE U.","year":"1950"},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of the llth Annual Conference on Complexity Theory. IEEE","author":"FEIGE U."},{"key":"e_1_2_1_45_1","first-page":"733","volume-title":"Proceedings of the 24th Annual Symposium on the Theory of Computing (Victoria, B.C., Canada, May 4-6). ACM","author":"FEIGE U."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90251-8"},{"key":"e_1_2_1_47_1","series-title":"Lecture Notes in Computer Science","first-page":"57","volume-title":"Proceedings of Symposium on Mathematical Foundations of Computer Science","author":"FRIEVALDS R."},{"key":"e_1_2_1_48_1","volume-title":"Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM","author":"FRIEDL K."},{"key":"e_1_2_1_49_1","first-page":"250","volume-title":"Proceedings of the 3rd Israel Symposium on Theory and Computing Systems. IEEE Computer Society Press, Los Alamitos, Calif.","author":"FRIEDL K."},{"key":"e_1_2_1_50_1","volume-title":"Proceed-ings of the 36th Annual Symposium on the Foundations of Computer Science. IEEE","author":"FURER M."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321926"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/322077.322090"},{"key":"e_1_2_1_53_1","unstructured":"GAREY M. AND JOHNSON D. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman New York. GAREY M. AND JOHNSON D. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman New York."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90059-1"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90195-2"},{"key":"e_1_2_1_56_1","first-page":"32","volume-title":"Proceedings of the 23rd Annual ACM Symposium on the Theory of Computing (New Orleans, La., May 6-8). ACM","author":"GEMMELL P."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"e_1_2_1_58_1","doi-asserted-by":"crossref","unstructured":"GOLDREICH O. 1997. A taxonomy of proof systems. In Complexity Theory Retrospective H L. A. Hemaspaandra and A. Selman eds. Springer-Verlag New York. GOLDREICH O. 1997. A taxonomy of proof systems. In Complexity Theory Retrospective H L. A. Hemaspaandra and A. Selman eds. Springer-Verlag New York.","DOI":"10.1007\/978-1-4612-1872-2_5"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218012"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1966.tb01709.x"},{"key":"e_1_2_1_61_1","first-page":"11","volume-title":"Proceedings of the 28th Annual ACM Symposium on the Theory of Computing","author":"STAD J."},{"key":"e_1_2_1_62_1","unstructured":"H\/#kSTAD J. 1996b. Clique is hard to approximate within n1-E In Proceedings of the 37th Annual Symposium on the Foundations of Computer Science. IEEE New York. H\/#kSTAD J. 1996b. Clique is hard to approximate within n1-E In Proceedings of the 37th Annual Symposium on the Foundations of Computer Science. IEEE New York."},{"key":"e_1_2_1_63_1","first-page":"1","volume-title":"Proceedings of the 29th Annual ACM Symposium on the Theory of Computing (El Paso, Tex., May 4-6). ACM","author":"STAD J."},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/321906.321909"},{"key":"e_1_2_1_65_1","volume-title":"Proceedings of the 30th Annual Symposium on the Foundations of Computer Science. IEEE","author":"IMPAGLIAZZO R."},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80044-9"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90246-E"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523689"},{"key":"e_1_2_1_69_1","volume-title":"Proceedings of the 23rd Annual Symposium on the Foundations of Computer Science. IEEE","author":"KARMAKAR N."},{"key":"e_1_2_1_70_1","first-page":"85","volume-title":"Complexity of Computer Computations","author":"KARP R."},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070013"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365712"},{"key":"e_1_2_1_73_1","first-page":"425","volume-title":"Proceedings of the 19th Annual Symposium on the Theory of Computing","author":"KOLAITIS P."},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1238"},{"issue":"3","key":"e_1_2_1_75_1","first-page":"265","article-title":"Universarnyie perebornyie zadachi (Universal Search Problems: in Russian)","volume":"9","author":"LEVIN L.","year":"1973","journal-title":"Problemy Peredachi Informatsii"},{"key":"e_1_2_1_76_1","series-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science","first-page":"191","volume-title":"Distributed Computing and Cryptography","author":"LIPTON R."},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146605"},{"key":"e_1_2_1_78_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of ICALP 93","author":"LUND C."},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1145\/185675.306789"},{"key":"e_1_2_1_80_1","unstructured":"MITCHELL J. 1998. Guillotine subdivisions approximate polygonal subdivision: Part II - A simple PTAS for geometric k-MST TSP and related problems. SIAM J. Comput. to appear. 10.1137\/S0097539796309764 MITCHELL J. 1998. Guillotine subdivisions approximate polygonal subdivision: Part II - A simple PTAS for geometric k-MST TSP and related problems. SIAM J. Comput. to appear. 10.1137\/S0097539796309764"},{"key":"e_1_2_1_81_1","volume-title":"Lecture Notes on Approximation Algorithms","author":"MOTWANI R."},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90023-X"},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.5555\/2781820.2781821"},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(81)90081-5"},{"key":"e_1_2_1_85_1","unstructured":"PHILLIPS S. AND SAFRA S. 1992. PCP and tighter bounds for approximating MAXSNP. Manuscript. Stanford Univ. Stanford Calif. PHILLIPS S. AND SAFRA S. 1992. PCP and tighter bounds for approximating MAXSNP. Manuscript. Stanford Univ. Stanford Calif."},{"key":"e_1_2_1_86_1","first-page":"194","volume-title":"Proceedings of the 26th Annual ACM Symposium on the Theory of Computing (Montreal, Que., Canada, May 23-25)","author":"POLISHCHUK A.","year":"1950"},{"key":"e_1_2_1_87_1","first-page":"447","volume-title":"Proceedings of the 27th Annual ACM Symposium on the Theory of Computing (Las Vegas, Nev., May 29-June 1). ACM","author":"RAZ R."},{"key":"e_1_2_1_88_1","first-page":"475","volume-title":"Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (El Paso, Tex., May 4-6). ACM","author":"RAZ R."},{"key":"e_1_2_1_89_1","unstructured":"RUBINFELD R. 1990. A mathematical theory of self-checking self-testing and self-correcting programs. Ph.D. dissertation. Univ. California Berkeley Berkeley Calif. RUBINFELD R. 1990. A mathematical theory of self-checking self-testing and self-correcting programs. Ph.D. dissertation. Univ. California Berkeley Berkeley Calif."},{"key":"e_1_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"e_1_2_1_91_1","doi-asserted-by":"publisher","DOI":"10.1145\/321864.321873"},{"key":"e_1_2_1_92_1","doi-asserted-by":"publisher","DOI":"10.1145\/321958.321975"},{"key":"e_1_2_1_93_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322225"},{"key":"e_1_2_1_94_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146609"},{"key":"e_1_2_1_95_1","volume-title":"Calif.","volume":"1001","author":"SUDAN M.","year":"1992"},{"key":"e_1_2_1_96_1","volume-title":"Proceedings of the 9th Annual Conference on Structure in Complexity Theory. IEEE","author":"TARDOS G."},{"key":"e_1_2_1_97_1","doi-asserted-by":"publisher","DOI":"10.1109\/MAHC.1984.10036"},{"key":"e_1_2_1_98_1","first-page":"633","article-title":"Error correction of algebraic block codes","volume":"4","author":"WELCH L.","year":"1986","journal-title":"US Patent Number"},{"key":"e_1_2_1_99_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1045"},{"key":"e_1_2_1_100_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266407"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/278298.278306","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,1]],"date-time":"2021-03-01T22:24:24Z","timestamp":1614637464000},"score":1,"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,5]]},"references-count":99,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1998,5]]}},"alternative-id":["10.1145\/278298.278306"],"URL":"http:\/\/dx.doi.org\/10.1145\/278298.278306","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[1998,5]]}}}