{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2021,11,23]],"date-time":"2021-11-23T17:10:50Z","timestamp":1637687450227},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[1998,1]]},"abstract":"\n We give a new characterization of NP: the class NP contains exactly those languages\n L<\/jats:italic>\n for which membership proofs (a proof that an input\n x<\/jats:italic>\n is in\n L<\/jats:italic>\n ) can be verified probabilistically in polynomial time using\n logarithmic<\/jats:italic>\n number of random bits and by reading\n sublogarithmic<\/jats:italic>\n number of bits from the proof.\n <\/jats:p>\n We discuss implications of this characterization; specifically, we show that approximating Clique and Independent Set, even in a very weak sense, is NP-hard.<\/jats:p>","DOI":"10.1145\/273865.273901","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:25:57Z","timestamp":1027769157000},"page":"70-122","source":"Crossref","is-referenced-by-count":512,"title":["Probabilistic checking of proofs"],"prefix":"10.1145","volume":"45","author":[{"given":"Sanjeev","family":"Arora","sequence":"first","affiliation":[{"name":"Princeton Univ., Princeton, NJ"}]},{"given":"Shmuel","family":"Safra","sequence":"additional","affiliation":[{"name":"Tel-Aviv Univ., Tel-Aviv, Israel"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_1","first-page":"132","volume-title":"Proceedings of the 19th Annual ACM Symposium on Theory of Computing","author":"AJTAI M.","year":"1987"},{"issue":"3","key":"e_1_2_1_2_1","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1002\/rsa.3240030308","article-title":"Simple constructions of almost k-wise independent random variables","volume":"3","author":"ALON N.","year":"1992","journal-title":"Rand. Struct. Algor."},{"key":"e_1_2_1_3_1","first-page":"724","volume-title":"Proceedings of the 34th IEEE Symposium on Foundations of Computer Science. IEEE","author":"ARORA S.","year":"1993"},{"key":"e_1_2_1_4_1","volume-title":"Approximation Algorithms for NP-hard Problems, Dorit Hochbaum, ed","author":"ARORA S."},{"key":"e_1_2_1_5_1","first-page":"13","volume-title":"Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science. IEEE","author":"ARORA S.","year":"1992"},{"key":"e_1_2_1_6_1","unstructured":"ARORA S. MOTWANI R. SAFRA M. SUDAN M. AND SZEGEDY M. 1992b. PCP and approximation problems. Manuscript. ARORA S. MOTWANI R. SAFRA M. SUDAN M. AND SZEGEDY M. 1992b. PCP and approximation problems. Manuscript."},{"key":"e_1_2_1_7_1","first-page":"2","volume-title":"Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science. IEEE","author":"ARORA S.","year":"1992"},{"key":"e_1_2_1_8_1","first-page":"496","volume-title":"Proceedings of the 29th Annual ACM Symposium on Theory of Computing, ACM","author":"ARORA S.","year":"1997"},{"key":"e_1_2_1_9_1","first-page":"421","volume-title":"Proceedings of the 17th ACM Symposium on Theory of Computing (Providence, R.I., May 6-8). ACM","author":"BABAI L.","year":"1985"},{"key":"e_1_2_1_10_1","first-page":"21","volume-title":"Proceedings of the 23rd ACM Symposium on Theory of Computing (New Orleans, La., May 6-8). ACM","author":"BABAI L.","year":"1991"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF01200056","article-title":"Non-deterministic exponential time has two-prover interactive protocols","volume":"1","author":"BABAI L.","year":"1991","journal-title":"Comput. Comp."},{"key":"e_1_2_1_12_1","first-page":"266","volume-title":"Proceedings of the 2nd Israel Symposium on Theory and Computing Systems. IEEE Computer Press","author":"BELLARE M.","year":"1993"},{"key":"e_1_2_1_13_1","first-page":"422","volume-title":"Proceedings of the 35th IEEE Symposium on Foundations of Computer Science. IEEE","author":"BELLARE M.","year":"1995"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167174"},{"key":"e_1_2_1_15_1","volume-title":"Complexity of Numerical Optimization","author":"BELLARE M."},{"key":"e_1_2_1_16_1","first-page":"184","volume-title":"Proceedings of the 26th Annual ACM Symposium on Theory of Computing (Montreal, Que., Canada, May 23-25)","author":"BELLARE M.","year":"1994"},{"key":"e_1_2_1_17_1","first-page":"113","volume-title":"Proceedings of the 20th Annual ACM Symposium on Theory of Computing","author":"BEN-OR M.","year":"1988"},{"key":"e_1_2_1_18_1","first-page":"633","article-title":"Error correction of algebraic block codes","volume":"4","author":"BERLEKAMP E.","year":"1986","journal-title":"US Patent Number"},{"key":"e_1_2_1_19_1","first-page":"86","volume-title":"Proceedings of the 21st Annual ACM Symposium on Theory of Computing","author":"BLUM M.","year":"1989"},{"key":"e_1_2_1_20_1","first-page":"73","volume-title":"Proceedings of the 22nd Annual ACM Symposium on Theory of Computing","author":"BLUM M.","year":"1990"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01994876"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80084-4"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(89)90015-0"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01271372"},{"key":"e_1_2_1_25_1","first-page":"280","volume-title":"Proceedings of the 9th Structure in Complexity Theory Conference.","author":"CONDON A.","year":"1993"},{"key":"e_1_2_1_26_1","first-page":"462","volume-title":"Proceedings of the 30th IEEE Symposium on Foundations of Computer Science. IEEE","author":"CONDON A.","year":"1989"},{"key":"e_1_2_1_27_1","first-page":"151","volume-title":"Proceedings of the 3rd Annual ACM Symposium on Theory of Computing (Shaker Heights, Oh., May 3-5). ACM","author":"COOK S. A.","year":"1971"},{"key":"e_1_2_1_28_1","first-page":"43","volume-title":"Complexity of Computer Computations, Richard Karp, ed. AMS, Providence, R.I.","author":"FAGIN R."},{"key":"e_1_2_1_29_1","first-page":"2","volume-title":"Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science. IEEE","author":"FEIGE U.","year":"1991"},{"key":"e_1_2_1_30_1","first-page":"733","volume-title":"Proceedings of the 24th Annual ACM Symposium on Theory of Computing (Victoria, B.C., Canada, May 4-6). ACM","author":"FEIGE U.","year":"1992"},{"key":"e_1_2_1_31_1","first-page":"156","volume-title":"Proceedings of the 3rd Conference on Structure in Complexity Theory.","author":"FORTNOW L.","year":"1988"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90199-8"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218012"},{"key":"e_1_2_1_34_1","first-page":"627","volume-title":"Proceedings of the 37th IEEE Symposium on Foundations of Computer Science. IEEE","author":"HASTAD J.","year":"1996"},{"key":"e_1_2_1_35_1","first-page":"1","volume-title":"Proceedings of the 29th Annual ACM Symposium on Theory of Computing (El Paso, Tex., May 4-6). ACM","author":"HASTAD J.","year":"1997"},{"key":"e_1_2_1_36_1","first-page":"85","volume-title":"Complexity of Computer Computations, Miller and Thatcher, eds","author":"KARP R. M."},{"key":"e_1_2_1_37_1","first-page":"250","volume-title":"Proceedings of the 2nd Israel Symposium on Theory and Computing Systems, ISTCS. IEEE Computer Society Press","author":"KHANNA S.","year":"1993"},{"key":"e_1_2_1_38_1","first-page":"294","volume-title":"Proceedings of the 9th Structure in Complexity Theory Conference. IEEE Computer Press","author":"KIWI M.","year":"1994"},{"key":"e_1_2_1_39_1","first-page":"13","volume-title":"Proceedings of the 32nd IEEE Symposium on Foundations of Computer Science. IEEE","author":"LAPIDOT D.","year":"1991"},{"issue":"3","key":"e_1_2_1_40_1","first-page":"265","article-title":"Universal'nyie pereborny#e zadachi (universal search problems: in Russian)","volume":"9","author":"LEVIN L.","year":"1973","journal-title":"Prob. Per. Inf."},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of 6th STACS.","author":"LIPTON R.","year":"1989"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146605"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/185675.306789"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222053"},{"key":"e_1_2_1_45_1","unstructured":"PAPADIMITRIOU C. 1994. Computational Complexity. Addison Wesley Reading Mass. PAPADIMITRIOU C. 1994. Computational Complexity. Addison Wesley Reading Mass."},{"key":"e_1_2_1_46_1","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","article-title":"Optimization, approximation and complexity classes","volume":"43","author":"PAPADIMITRIOU C.","year":"1991","journal-title":"J. Comput. Syst. Sci."},{"key":"e_1_2_1_47_1","unstructured":"PHILLIPS S. AND SAFRA S. 1992. PCP and tighter bounds for approximating MAX-SNP. Manuscript. PHILLIPS S. AND SAFRA S. 1992. PCP and tighter bounds for approximating MAX-SNP. Manuscript."},{"key":"e_1_2_1_48_1","first-page":"194","volume-title":"Proceedings of the 26th Annual ACM Symposium on Theory of Computing (Montreal, Que., Canada, May 23-25)","author":"ISI UK, A","year":"1994"},{"key":"e_1_2_1_49_1","first-page":"475","volume-title":"Proceedings of the 29th Annual ACM Symposium on Theory of Computing (El Paso, Tex., May 4-6). ACM","author":"RAZ R.","year":"1997"},{"key":"e_1_2_1_50_1","first-page":"23","volume-title":"Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms (Orlando, Fla., Jan. 27-29)","author":"RUBINFELD R.","year":"1992"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146609"},{"key":"e_1_2_1_52_1","unstructured":"SI4EN A. 1991. Multilinearity test made easy. Manuscript. SI4EN A. 1991. Multilinearity test made easy. Manuscript."},{"key":"e_1_2_1_53_1","unstructured":"UDAN M. 1992. Efficient checking of polynomials and proofs and the hardness of approximation problems. Ph.D. dissertation. U.C. Berkeley Berkeley Calif. UDAN M. 1992. Efficient checking of polynomials and proofs and the hardness of approximation problems. Ph.D. dissertation. U.C. Berkeley Berkeley Calif."},{"key":"e_1_2_1_54_1","first-page":"79","volume-title":"Proceedings of the 32nd IEEE Symposium on Foundations of Computer Science. IEEE","author":"ZUCKERMAN D.","year":"1991"},{"key":"e_1_2_1_55_1","first-page":"305","volume-title":"Proceedings of the 8th Structure in Complexity Theory Conference","author":"ZUCKERMAN D.","year":"1993"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/273865.273901","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,2]],"date-time":"2021-03-02T00:26:57Z","timestamp":1614644817000},"score":1,"subtitle":["a new characterization of NP"],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":55,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1145\/273865.273901"],"URL":"http:\/\/dx.doi.org\/10.1145\/273865.273901","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,1]]}}}