{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T04:05:42Z","timestamp":1772424342389,"version":"3.50.1"},"reference-count":13,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2018,9]]},"abstract":"<jats:p> The prominent Boolean formula satisfiability problem SAT is known to be [Formula: see text]-complete even for very restricted variants such as 3-SAT, Monotone 3-SAT, or Planar 3-SAT, or instances with bounded variable appearance. We settle the computational complexity status for two variants with bounded variable appearance: We show that Planar Monotone Sat \u2014 the variant of Monotone Sat in which the incidence graph is required to be planar \u2014 is [Formula: see text]-complete even if each clause consists of at most three distinct literals and each variable appears exactly three times, and that Monotone Sat is [Formula: see text]-complete even if each clause consists of three distinct literals and each variable appears exactly four times in the formula. The latter confirms a conjecture stated in scribe notes [7] of an MIT lecture by Eric Demaine. In addition, we provide hardness results with respect to bounded variable appearances for two variants of Planar Monotone Sat. <\/jats:p>","DOI":"10.1142\/s0129054118500168","type":"journal-article","created":{"date-parts":[[2018,10,5]],"date-time":"2018-10-05T04:02:35Z","timestamp":1538712155000},"page":"979-993","source":"Crossref","is-referenced-by-count":10,"title":["The Monotone Satisfiability Problem with Bounded Variable Appearances"],"prefix":"10.1142","volume":"29","author":[{"given":"Andreas","family":"Darmann","sequence":"first","affiliation":[{"name":"Institute of Public Economics, University of Graz, Universitaetsstr. 15, 8010 Graz, Austria"}]},{"given":"Janosch","family":"D\u00f6cker","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Tuebingen, Sand 12, 72076 Tuebingen, Germany"}]},{"given":"Britta","family":"Dorn","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Tuebingen, Sand 12, 72076 Tuebingen, Germany"}]}],"member":"219","published-online":{"date-parts":[[2018,10,5]]},"reference":[{"key":"S0129054118500168BIB001","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(97)00026-6"},{"key":"S0129054118500168BIB002","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84628-970-5"},{"key":"S0129054118500168BIB003","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792225297"},{"key":"S0129054118500168BIB004","author":"Darmann A.","year":"2016","journal-title":"CoRR"},{"key":"S0129054118500168BIB005","author":"Darmann A.","year":"2016","journal-title":"CoRR"},{"key":"S0129054118500168BIB006","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195912500045"},{"key":"S0129054118500168BIB008","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979"},{"key":"S0129054118500168BIB009","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(78)90562-4"},{"key":"S0129054118500168BIB010","doi-asserted-by":"publisher","DOI":"10.1137\/0405033"},{"key":"S0129054118500168BIB011","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)90143-0"},{"issue":"1","key":"S0129054118500168BIB012","volume":"78","author":"Li W. N.","year":"1997","journal-title":"Discrete Applied Mathematics"},{"key":"S0129054118500168BIB013","doi-asserted-by":"publisher","DOI":"10.1137\/0211025"},{"key":"S0129054118500168BIB014","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90081-7"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054118500168","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T20:46:02Z","timestamp":1565124362000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054118500168"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9]]},"references-count":13,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2018,10,5]]},"published-print":{"date-parts":[[2018,9]]}},"alternative-id":["10.1142\/S0129054118500168"],"URL":"https:\/\/doi.org\/10.1142\/s0129054118500168","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,9]]}}}