{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:28:21Z","timestamp":1761611301083},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540569923"},{"type":"electronic","value":"9783540478904"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-56992-8_9","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T12:01:25Z","timestamp":1330257685000},"page":"115-133","source":"Crossref","is-referenced-by-count":5,"title":["The class of problems that are linearly equivalent to satisfiability or a uniform method for proving NP-completeness"],"prefix":"10.1007","author":[{"given":"Nadia","family":"Creignou","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"9_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0168-0072(90)90080-L","volume":"48","author":"K. J. Compton","year":"1990","unstructured":"K. J. Compton and C. W. Henson, A uniform method for proving lower bounds on the computational complexity of logical theories, Annals of Pure and Applied Logic 48 (1990), 1\u201379.","journal-title":"Annals of Pure and Applied Logic"},{"key":"9_CR2","first-page":"151","volume-title":"The complexity of theorem-proving procedures","author":"S. A. Cook","year":"1971","unstructured":"S. A. Cook, The complexity of theorem-proving procedures, Proc. 3rd Ann. ACM Symp. on Theory of Computing, Association for Computing Machinery, New York (1971), 151\u2013158."},{"key":"9_CR3","unstructured":"N. Creignou, Exact complexity of problems of incompletely specified automata, T. R. Univ. de Caen, France, Cahiers du LIUC 92-9 (1992),, submitted to Annals of Mathematics and Artificial Intelligence, J. C. Baltzer Scientific Publishing Co. (Suisse), Special issue ed. M. Nivat and S. Grigorieff, (1993)."},{"key":"9_CR4","volume-title":"Th\u00e8se de doctorat","author":"N. Creignou","year":"1993","unstructured":"N. Creignou, Temps lin\u00e9aire et probl\u00e8mes NP-complets, Th\u00e8se de doctorat, Univ. de Caen, France (1993)."},{"key":"9_CR5","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1080\/00207168208803302","volume":"11","author":"A. K. Dewdney","year":"1982","unstructured":"A. K. Dewdney, Linear transformations between combinatorial problems, Intern. J. Computer Math. 11 (1982), 91\u2013110.","journal-title":"Intern. J. Computer Math."},{"key":"9_CR6","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and G. S. Johnson, Computers and intractability: a guide to the theory of NP-completeness, W. H. Freeman and Co, San Franscisco (1979)."},{"key":"9_CR7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0219028","volume":"19","author":"E. Grandjean","year":"1990","unstructured":"E. Grandjean, Nontrivial lower bound for a NP problem on automata, SIAM J. Comput., 19, (1990), 1\u201314.","journal-title":"SIAM J. Comput."},{"key":"9_CR8","unstructured":"E. Grandjean, Linear time algorithms and NP-complete problems, T. R. Univ. de Caen, France, Cahiers du LIUC 91-9 (1991), to appear in Lect. Notes in Comput. Sci. CSL'92 (San Miniato) (1993)."},{"key":"9_CR9","unstructured":"E. Grandjean, Sorting, linear time and Satisfiability problem, preprint (1992), submitted to Annals of Mathematics and Artificial Intelligence, J. C. Baltzer Scientific Publishing Co. (Suisse), Special issue ed. M. Nivat and S. Grigorieff, (1993)."},{"key":"9_CR10","volume-title":"Languages and Computation","author":"J. Hopcroft","year":"1979","unstructured":"J. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, MA (1979)."},{"key":"9_CR11","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R. M. Karp","year":"1972","unstructured":"R. M. Karp, Reducibility among combinatorial problems, in R. E. Miller and J. W. Thatcher (eds), Complexity of Computer Computations, Plenum Press, New York (1972), 85\u2013103."},{"key":"9_CR12","first-page":"240","volume-title":"On the complexity of a general matching problem","author":"D. G. Kirkpatrick","year":"1978","unstructured":"D. G. Kirkpatrick and P. Hell, On the complexity of a general matching problem, Proc. 10th Ann. ACM Symp. of Theory of Computing, Association for Computing Machinery, New York (1978), 240\u2013245."},{"key":"9_CR13","unstructured":"D. E. Knuth, Axioms and Hulls, Lect. Notes in Comput. Sci. 606, Springer-Verlag."},{"key":"9_CR14","first-page":"216","volume-title":"The complexity of satisfiability problems","author":"T. J. Schaefer","year":"1978","unstructured":"T. J. Schaefer, The complexity of satisfiability problems, Proc. 10th Ann. ACM Symp. of Theory of Computing, Association for Computing Machinery, New York, (1978), 216\u2013226."}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56992-8_9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T00:58:05Z","timestamp":1619571485000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56992-8_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540569923","9783540478904"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-56992-8_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}