{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,10,23]],"date-time":"2024-10-23T09:03:43Z","timestamp":1729674223021,"version":"3.28.0"},"reference-count":24,"publisher":"IEEE Comput. Soc","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1109\/ismvl.2004.1319950","type":"proceedings-article","created":{"date-parts":[[2004,9,28]],"date-time":"2004-09-28T13:50:22Z","timestamp":1096379422000},"page":"251-256","source":"Crossref","is-referenced-by-count":0,"title":["The interface between P and NP in signed CNF formulas"],"prefix":"10.1109","author":[{"given":"C.","family":"Ansotegui","sequence":"first","affiliation":[]},{"given":"R.","family":"Bejar","sequence":"additional","affiliation":[]},{"given":"A.","family":"Cabiscol","sequence":"additional","affiliation":[]},{"given":"F.","family":"Manya","sequence":"additional","affiliation":[]}],"member":"263","reference":[{"key":"19","first-page":"459","article-title":"Hard and easy distributions of SAT problems","author":"mitchell","year":"1992","journal-title":"Proceedings of the 10th National Conference on Artificial Intelligence AAAI'92 San Jose\/CA USA"},{"key":"22","first-page":"290","article-title":"Domain-independent extensions of GSAT: Solving large structured satisfiability problems","author":"selman","year":"1993","journal-title":"Proceedings of the International Joint Conference on Artificial Intelligence IJCAI'93 Chambery France"},{"key":"17","first-page":"307","article-title":"The 2-SAT problem in signed CNF formulas","volume":"5","author":"manya?","year":"2000","journal-title":"Multiple-Valued Logic An International Journal"},{"key":"23","doi-asserted-by":"publisher","DOI":"10.1109\/DAC.2001.935509"},{"key":"18","doi-asserted-by":"crossref","DOI":"10.1109\/SBCCI.1999.803118","article-title":"Algorithms for satisfiability in combinational circuits based on back-track search and recursive learning","author":"marques-silva","year":"1999","journal-title":"Proc Symp Integrated Circuits and Systems Design (SBCCI)"},{"key":"24","first-page":"695","article-title":"The interface between P and NP: COL, XOR, NAE, 1-in-k, and Horn-SAT","author":"walsh","year":"2002","journal-title":"Proceedings of the AAAI National Conference on Artificial Intelligence Edmonton Canada 2002"},{"journal-title":"Proof Procedures for Multiple-valued Prepositional Logics","year":"1996","author":"manya?","key":"15"},{"journal-title":"Proof Procedures for Multiple-valued Propositional Logics","year":"1999","author":"manya?","key":"16"},{"key":"13","first-page":"366","article-title":"Heuristics based on unit propagation for satisfiability problems","author":"li","year":"1997","journal-title":"Proceedings of the International Joint Conference on Artificial Intelligence IJCAI'97 Nagoya Japan"},{"key":"14","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1007\/BFb0017450","article-title":"Look-ahead versus look-back for satisfiability problems","author":"li","year":"1997","journal-title":"Proceedings of the 3rd International Conference on Principles of Constraint Programming CP'97 Linz Austria"},{"key":"11","doi-asserted-by":"publisher","DOI":"10.1080\/11663081.1996.10510866"},{"key":"12","first-page":"1194","article-title":"Pushing the envelope: Planning, prepositional logic, and stochastic search","author":"kautz","year":"1996","journal-title":"Proceedings of the 14th National Conference on Artificial Intelligence AAAI'96 Portland\/OR USA"},{"key":"21","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G"},{"key":"3","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1007\/978-3-540-45193-8_7","article-title":"Boosting Chaff's performance by incorporating CSP heuristics","author":"anso?tegui","year":"2003","journal-title":"9th International Conference on Principles and Practice of Constraint Programming CP-2003 Kinsale Ireland"},{"key":"20","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1038\/22055","article-title":"Determining computational complexity for characteristic 'phase transitions'","volume":"400","author":"monasson","year":"1998","journal-title":"Nature"},{"key":"2","article-title":"Mv-Satz: A SAT solver for many-valued clausal forms","author":"anso?tegui","year":"2003","journal-title":"4th International Conference Journe?es de L'Informatique Messine JIM-2003 Metz France"},{"key":"1","first-page":"156","article-title":"Resolution methods for many-valued CNF formulas","author":"anso?tegui","year":"2002","journal-title":"Fifth International Symposium on the Theory and Applications of Satisfiability Testing SAT-2002 Cincinnati USA"},{"key":"10","first-page":"221","article-title":"Problem structure in the presence of perturbations","author":"gomes","year":"1997","journal-title":"Proceedings of the 14th National Conference on Artificial Intelligence AAAI'97 Providence\/RI USA"},{"key":"7","first-page":"262","article-title":"Solving the round robin problem using prepositional logic","author":"be?jar","year":"2000","journal-title":"Proceedings of the 17th National Conference on Artificial Intelligence AAAI-2000 Austin\/TX USA"},{"key":"6","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45578-7_10"},{"journal-title":"Systematic and Local Search Algorithms for Regular-SAT","year":"2000","author":"be?jar","key":"5"},{"key":"4","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-011-4040-9_3"},{"key":"9","doi-asserted-by":"publisher","DOI":"10.1145\/368273.368557"},{"key":"8","first-page":"331","article-title":"Where the really hard problems are","author":"cheeseman","year":"1991","journal-title":"Proceedings of the 12th International Joint Conference on Artificial Intelligence IJCAI'91 Sydney Australia"}],"event":{"name":"Proceedings. 34th International Symposium on Multiple-Valued Logic","acronym":"ISMVL-04","location":"Toronto, Ont., Canada"},"container-title":["Proceedings. 34th International Symposium on Multiple-Valued Logic"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx5\/9226\/29244\/01319950.pdf?arnumber=1319950","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,8,8]],"date-time":"2018-08-08T10:14:54Z","timestamp":1533723294000},"score":1,"resource":{"primary":{"URL":"http:\/\/ieeexplore.ieee.org\/document\/1319950\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"references-count":24,"URL":"https:\/\/doi.org\/10.1109\/ismvl.2004.1319950","relation":{},"subject":[]}}