{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T17:21:36Z","timestamp":1740158496625,"version":"3.37.3"},"reference-count":10,"publisher":"Walter de Gruyter GmbH","issue":"0","funder":[{"DOI":"10.13039\/501100006769","name":"Russian Science Foundation","doi-asserted-by":"publisher","award":["17-11-01117"],"award-info":[{"award-number":["17-11-01117"]}],"id":[{"id":"10.13039\/501100006769","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017,1,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>It follows from the famous result of Cook about the NP-completeness of the Boolean satisfiability problem that there is no polynomial algorithm for this problem if<\/jats:p>","DOI":"10.1515\/gcc-2017-0008","type":"journal-article","created":{"date-parts":[[2017,10,12]],"date-time":"2017-10-12T10:01:05Z","timestamp":1507802465000},"source":"Crossref","is-referenced-by-count":0,"title":["Generic hardness of the Boolean satisfiability problem"],"prefix":"10.1515","volume":"0","author":[{"given":"Alexander","family":"Rybalov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"374","reference":[{"key":"ref31","doi-asserted-by":"crossref","first-page":"665","DOI":"10.1016\/S0021-8693(03)00167-4","article-title":"Generic-case complexity, decision problems in group theory and random walks","volume":"264","year":"2003","journal-title":"J. Algebra"},{"journal-title":"The Art of Computer Programming","year":"1998","key":"ref41"},{"key":"ref51","first-page":"151","article-title":"The complexity of theorem proving procedures","year":"1971","journal-title":"Proceedings of the Third Annual ACM Symposium on Theory of Computing"},{"key":"ref21","first-page":"220","article-title":"P=BPP unless E has Subexponential Circuits: Derandomizing the XOR Lemma","year":"1997","journal-title":"Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing"},{"key":"ref71","first-page":"220","article-title":"P=BPP unless E has Subexponential Circuits: Derandomizing the XOR Lemma","year":"1997","journal-title":"Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing"},{"key":"ref01","first-page":"151","article-title":"The complexity of theorem proving procedures","year":"1971","journal-title":"Proceedings of the Third Annual ACM Symposium on Theory of Computing"},{"key":"ref11","first-page":"359","article-title":"Worst-case upper bounds","year":"2008","journal-title":"Handbook of Satisfiability"},{"key":"ref81","doi-asserted-by":"crossref","first-page":"665","DOI":"10.1016\/S0021-8693(03)00167-4","article-title":"Generic-case complexity, decision problems in group theory and random walks","volume":"264","year":"2003","journal-title":"J. Algebra"},{"key":"ref61","first-page":"359","article-title":"Worst-case upper bounds","year":"2008","journal-title":"Handbook of Satisfiability"},{"journal-title":"The Art of Computer Programming","year":"1998","key":"ref91"}],"container-title":["Groups Complexity Cryptology"],"original-title":[],"link":[{"URL":"http:\/\/www.degruyter.com\/view\/j\/gcc.ahead-of-print\/gcc-2017-0008\/gcc-2017-0008.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/www.degruyter.com\/view\/j\/gcc.ahead-of-print\/gcc-2017-0008\/gcc-2017-0008.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,27]],"date-time":"2021-02-27T03:08:44Z","timestamp":1614395324000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/gcc-2017-0008\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1,12]]},"references-count":10,"journal-issue":{"issue":"0"},"URL":"https:\/\/doi.org\/10.1515\/gcc-2017-0008","relation":{},"ISSN":["1867-1144","1869-6104"],"issn-type":[{"type":"print","value":"1867-1144"},{"type":"electronic","value":"1869-6104"}],"subject":[],"published":{"date-parts":[[2017,1,12]]}}}