{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,12,29]],"date-time":"2022-12-29T19:28:21Z","timestamp":1672342101210},"reference-count":10,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2010,6]]},"abstract":"<jats:p> We examine the complexity of the model checking problem for Boolean formulas, which is the following decision problem: Given a Boolean formula without variables, does it evaluate to true? We show that the complexity of this problem is determined by certain closure properties of the connectives allowed to build the formula, and achieve a complete classification: The formula model checking problem is either complete for NC<jats:sup>1<\/jats:sup>, equivalent to counting modulo 2, or complete for a level of the logarithmic time hierarchy under very strict reductions. <\/jats:p>","DOI":"10.1142\/s0129054110007258","type":"journal-article","created":{"date-parts":[[2010,6,7]],"date-time":"2010-06-07T06:40:55Z","timestamp":1275892855000},"page":"289-309","source":"Crossref","is-referenced-by-count":5,"title":["THE COMPLEXITY OF MODEL CHECKING FOR BOOLEAN FORMULAS"],"prefix":"10.1142","volume":"21","author":[{"given":"HENNING","family":"SCHNOOR","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Informatik, Christian-Albrechts-Universit\u00e4t Kiel, Christian-Albrechts-Platz 4, D-24118 Kiel, Germany"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf2","first-page":"1","volume":"5","author":"BAULAND M.","journal-title":"Logical Methods in Computer Science"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1035"},{"key":"rf4","first-page":"38","volume":"34","author":"B\u00d6HLER E.","journal-title":"SIGACT News"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-006-1301-3"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1145\/321864.321877"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1007\/BF01744287"},{"key":"rf11","first-page":"1","volume":"5","author":"POST E.","journal-title":"Annals of Mathematical Studies"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00288-5"},{"key":"rf16","first-page":"365","volume":"21","author":"RUZZO W. L.","journal-title":"Journal of Computer and Systems Sciences"},{"key":"rf18","series-title":"Introduction to Circuit Complexity \u2013 A Uniform Approach","volume-title":"Texts in Theoretical Computer Science","author":"VOLLMER H.","year":"1999"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054110007258","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T11:22:44Z","timestamp":1565176964000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054110007258"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,6]]},"references-count":10,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2010,6]]}},"alternative-id":["10.1142\/S0129054110007258"],"URL":"https:\/\/doi.org\/10.1142\/s0129054110007258","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,6]]}}}