{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:17:32Z","timestamp":1759637852383,"version":"3.28.0"},"reference-count":28,"publisher":"IEEE","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1109\/ccc.2004.1313795","type":"proceedings-article","created":{"date-parts":[[2004,11,13]],"date-time":"2004-11-13T00:14:14Z","timestamp":1100304854000},"page":"54-67","source":"Crossref","is-referenced-by-count":13,"title":["Relativized NP search problems and propositional proof systems"],"prefix":"10.1109","author":[{"given":"J.","family":"Buresh-Oppenheim","sequence":"first","affiliation":[]},{"given":"T.","family":"Morioka","sequence":"additional","affiliation":[]}],"member":"263","reference":[{"key":"ref10","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1145\/237814.237860","article-title":"Using the Gröbner basis algorithm to find proofs of unsatisfiability","author":"clegg","year":"1996","journal-title":"Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2646"},{"key":"ref12","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/0020-0190(88)90199-8","article-title":"Are there interactive proofs for coNP languages","volume":"28","author":"fortnow","year":"1988","journal-title":"Information Processing Letters"},{"key":"ref13","article-title":"Relativization: A revisionistic retrospective","author":"chang","year":"1992","journal-title":"Bulletin of the European Association for Theoretical Computer Science"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90046-3"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511529948"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240070103"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335348"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90200-L"},{"key":"ref19","article-title":"Classification of Search Problems and Their Definability in Bounded Arithmetic","author":"morioka","year":"2001","journal-title":"ECCC technical report TR01–82"},{"key":"ref28","first-page":"19","article-title":"Computational complexity","author":"yannakakis","year":"1997","journal-title":"Local Search in Combinatorial Opti-mization"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1987.30"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1305\/ndjfl\/1093635419"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(96)83747-X"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(98)80017-7"},{"journal-title":"Bounded Arithmetic Bibliopolis","year":"1986","author":"buss","key":"ref5"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-69.1.1"},{"key":"ref7","first-page":"59","article-title":"Lower bounds on Nullstellensatz proofs via de-signs","author":"buss","year":"1998","journal-title":"Proof Complexity and Feasible Arithmetics volume 39 of DIMACS Series in Discrete Mathematics and Theoretical Computer Sci-ence"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1575"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.2307\/2586729"},{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1137\/0204037"},{"journal-title":"Computational Complexity","year":"1994","author":"papadimitriou","key":"ref20"},{"key":"ref22","first-page":"317","article-title":"Counting problems in bounded arith-metic","author":"paris","year":"1985","journal-title":"Methods in Mathematical Logic Proceedings of the 6th Latin American Symposium on Mathematical Logic 1983 Volume 1130 of Lecture Notes in Mathematics"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80063-7"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.2307\/2275583"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200117"},{"key":"ref26","first-page":"289","article-title":"Making infinite structures finite in models of second order bounded arithmetic","author":"riis","year":"1993","journal-title":"Arithmetic Proof Theory and Computational Com-plexity"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1007\/s000370050013"}],"event":{"name":"Proceedings. 19th IEEE Annual Conference on Computational Complexity, 2004.","location":"Amherst, MA, USA"},"container-title":["Proceedings. 19th IEEE Annual Conference on Computational Complexity, 2004."],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx5\/9188\/29139\/01313795.pdf?arnumber=1313795","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,16]],"date-time":"2017-06-16T11:52:46Z","timestamp":1497613966000},"score":1,"resource":{"primary":{"URL":"http:\/\/ieeexplore.ieee.org\/document\/1313795\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"references-count":28,"URL":"https:\/\/doi.org\/10.1109\/ccc.2004.1313795","relation":{},"subject":[]}}