{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T19:44:33Z","timestamp":1760298273658},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540208518"},{"type":"electronic","value":"9783540246053"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-24605-3_11","type":"book-chapter","created":{"date-parts":[[2010,7,29]],"date-time":"2010-07-29T08:50:35Z","timestamp":1280393435000},"page":"135-149","source":"Crossref","is-referenced-by-count":2,"title":["Hidden Threshold Phenomena for Fixed-Density SAT-formulae"],"prefix":"10.1007","author":[{"given":"Hans","family":"van Maaren","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Linda","family":"van Norden","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"11_CR1","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0020-0190(79)90002-4","volume":"8","author":"B. Aspvall","year":"1979","unstructured":"Aspvall, B., Plass, M.F., Tarjan, R.E.: A linear time algorithm for testing the truth of certain quantified boolean formulas. Information Processing Letters\u00a08, 121\u2013123 (1979)","journal-title":"Information Processing Letters"},{"key":"11_CR2","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1016\/S0378-4371(02)00516-2","volume":"306","author":"G. Biroli","year":"2002","unstructured":"Biroli, G., Cocco, S., Monasson, R.: Phase transitions and complexity in computer science: an overview of the statistical physics approach to the random satisfiability problem. Physica A\u00a0306, 381\u2013394 (2002)","journal-title":"Physica A"},{"key":"11_CR3","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/S0166-218X(99)00031-1","volume":"96","author":"E. Boros","year":"1999","unstructured":"Boros, E.: Maximum renable horn sub-CNFs. Discrete Applied Mathematics\u00a096-97, 29\u201340 (1999)","journal-title":"Discrete Applied Mathematics"},{"key":"11_CR4","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0020-0190(92)90098-G","volume":"42","author":"V. Chandru","year":"1992","unstructured":"Chandru, V., Hooker, J.N.: Detecting embedded horn structure in propositional logic. Information Processing Letters\u00a042, 109\u2013111 (1992)","journal-title":"Information Processing Letters"},{"doi-asserted-by":"crossref","unstructured":"Cook, S.A.: The complexity of theorem proving procedures. In: Proceedings of the 3rd annual ACM symposium on the Theory of Computing, pp. 151\u2013158 (1971)","key":"11_CR5","DOI":"10.1145\/800157.805047"},{"key":"11_CR6","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/S0166-218X(96)00028-5","volume":"75","author":"Y. Crama","year":"1997","unstructured":"Crama, Y., Ekin, O., Hammer, P.L.: Variable and term removal from boolean formulae. Discrete Applied Mathematics\u00a075, 217\u2013230 (1997)","journal-title":"Discrete Applied Mathematics"},{"key":"11_CR7","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/0743-1066(84)90014-1","volume":"1","author":"W.F. Dowling","year":"1984","unstructured":"Dowling, W.F., Gallier, J.H.: Linear-time algorithms for testing the satisfiability of propositional horn formulae. Journal of Logic Programming\u00a01, 267\u2013284 (1984)","journal-title":"Journal of Logic Programming"},{"unstructured":"Dubois, O., Dequen, G.: A backbone-search heuristic for efficient solving of hard 3-sat formulae. In: IJCAI 2001 (2001)","key":"11_CR8"},{"key":"11_CR9","series-title":"DIMACS Series Discrete Math. Theoret. Computer Science","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1090\/dimacs\/035\/04","volume-title":"Relative size of certain polynomial time solvable subclasses of satisfiability","author":"J. Franco","year":"1997","unstructured":"Franco, J.: Relative size of certain polynomial time solvable subclasses of satisfiability. DIMACS Series Discrete Math. Theoret. Computer Science, vol.\u00a035, pp. 211\u2013233. Amer. Math. Soc., Piscataway (1997)"},{"issue":"4","key":"11_CR10","doi-asserted-by":"publisher","first-page":"1017","DOI":"10.1090\/S0894-0347-99-00305-7","volume":"12","author":"E. Friedgut","year":"1999","unstructured":"Friedgut, E.: Sharp thresholds of graph proporties and the k-sat problem. Journal of the American Mathematical Society\u00a012(4), 1017\u20131054 (1999)","journal-title":"Journal of the American Mathematical Society"},{"unstructured":"Kullmann, O.: First report on an adaptive density based branching rule for DLLlike SAT-solvers, using a database of mixed random conjunctive normal forms created using the advanced encryption standard (aes). Technical Report CSR 19-2002, University of Wales Swansea, Computer Science Report Series (2002)","key":"11_CR11"},{"unstructured":"Kullmann, O.: Investigating the behaviour of a sat solver on random formulas. Submitted to Annals of Mathematics and Artificial Intelligence (2002)","key":"11_CR12"},{"key":"11_CR13","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1038\/22055","volume":"400","author":"R. Monasson","year":"1999","unstructured":"Monasson, R., Zecchina, R., Kirkpatrick, S., Selman, B., Troyansky, L.: Determining computational complexity from characteristic \u2019phase transitions\u2019. Nature\u00a0400, 133\u2013137 (1999)","journal-title":"Nature"},{"key":"11_CR14","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1023\/A:1013847510365","volume":"6","author":"H. Maaren Van","year":"2002","unstructured":"Van Maaren, H., Dang, C.: Simplicial pivoting algorithms for a tractable class of integer programs. Journal of Combinatorial Optimization\u00a06, 133\u2013142 (2002)","journal-title":"Journal of Combinatorial Optimization"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Satisfiability Testing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-24605-3_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,1,25]],"date-time":"2019-01-25T19:28:26Z","timestamp":1548444506000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-24605-3_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540208518","9783540246053"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-24605-3_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}