{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,18]],"date-time":"2025-05-18T06:10:04Z","timestamp":1747548604662,"version":"3.40.5"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"1-4","license":[{"start":{"date-parts":[[1999,2,1]],"date-time":"1999-02-01T00:00:00Z","timestamp":917827200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1999,2,1]],"date-time":"1999-02-01T00:00:00Z","timestamp":917827200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Annals of Mathematics and Artificial Intelligence"],"published-print":{"date-parts":[[1999,2]]},"DOI":"10.1023\/a:1018954827926","type":"journal-article","created":{"date-parts":[[2003,2,19]],"date-time":"2003-02-19T22:07:13Z","timestamp":1045692433000},"page":"133-147","source":"Crossref","is-referenced-by-count":1,"title":["Strong bounds on the approximability of two Pspace-hard problems in propositional planning"],"prefix":"10.1007","volume":"26","author":[{"given":"Peter","family":"Jonsson","sequence":"first","affiliation":[]}],"member":"297","reference":[{"volume-title":"Readings in Planning","year":"1990","key":"325537_CR1","unstructured":"J. Allen, J. Hendler and A. Tate, eds., Readings in Planning (Morgan Kaufmann, San Mateo, CA, 1990)."},{"key":"325537_CR2","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1613\/jair.477","volume":"9","author":"C. B\u00e4ckstr\u00f6m","year":"1998","unstructured":"C. B\u00e4ckstr\u00f6m, Computational aspects of reordering plans, J. Artif. Intell. Res. 9 (1998) 99-137.","journal-title":"J. Artif. Intell. Res."},{"issue":"1\u20132","key":"325537_CR3","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/0004-3702(94)00081-B","volume":"76","author":"C. B\u00e4ckstr\u00f6m","year":"1995","unstructured":"C. B\u00e4ckstr\u00f6m, Expressive equivalence of planning formalisms, Artif. Intell. 76(1\u20132) (1995) 17-34.","journal-title":"Artif. Intell."},{"key":"325537_CR4","first-page":"1599","volume-title":"Proc. IJCAI '95","author":"C. B\u00e4ckstr\u00f6m","year":"1995","unstructured":"C. B\u00e4ckstr\u00f6m and P. Jonsson, Planning with abstraction hierarchies can be exponentially less efficient, in: Proc. IJCAI '95 (Morgan Kaufmann, San Mateo, CA, 1995) pp. 1599-1604."},{"issue":"3","key":"325537_CR5","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1111\/j.1467-8640.1991.tb00393.x","volume":"7","author":"C. B\u00e4ckstr\u00f6m","year":"1991","unstructured":"C. B\u00e4ckstr\u00f6m and I. Klein, Planning in polynomial time: The SAS-PUBS class, Comput. Intell. 7(3) (1991) 181-197.","journal-title":"Comput. Intell."},{"key":"325537_CR6","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0004-3702(94)90081-7","volume":"69","author":"T. Bylander","year":"1994","unstructured":"T. Bylander, The computational complexity of propositional STRIPS planning, Artif. Intell. 69 (1994) 165-204.","journal-title":"Artif. Intell."},{"key":"325537_CR7","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1016\/0004-3702(87)90092-0","volume":"32","author":"D. Chapman","year":"1987","unstructured":"D. Chapman, Planning for conjunctive goals, Artif. Intell. 32 (1987) 333-377.","journal-title":"Artif. Intell."},{"key":"325537_CR8","unstructured":"A. Condon, J. Feigenbaum, C. Lund and P.W. Shor, Probabilistically checkable debate systems and non-approximability of PSPACE-hard functions, Chicago J. Theoret. Comput. Sci. (1995) article 4."},{"issue":"2","key":"325537_CR9","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1137\/S0097539793260738","volume":"26","author":"A. Condon","year":"1997","unstructured":"A. Condon, J. Feigenbaum, C. Lund and P.W. Shor, Random debaters and the hardness of approximating stochastic functions, SIAM J. Comput. 26(2) (1997) 369-400.","journal-title":"SIAM J. Comput."},{"key":"325537_CR10","unstructured":"P. Crescenzi and V. Kann, A compendium of NP optimization problems, Technical Report SI\/RR-95\/02, Dipartimento di Scienze dell'Informazione, Universit\u00e1 di Roma \u201cLa Sapienza\u201d (1995)."},{"issue":"2","key":"325537_CR11","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/0890-5401(91)90025-W","volume":"93","author":"P. Crescenzi","year":"1991","unstructured":"P. Crescenzi and A. Panconesi, Completeness in approximation classes, Inform. Comput. 93(2) (1991) 241-262.","journal-title":"Inform. Comput."},{"key":"325537_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"330","DOI":"10.1007\/3-540-58715-2_135","volume-title":"Proc. STACS '94","author":"P. Crescenzi","year":"1994","unstructured":"P. Crescenzi and L. Trevisan, On approximation scheme preserving reducibility and its applications, in: Proc. STACS '94, Lecture Notes in Computer Science, Vol. 880 (Springer, Berlin, 1994) pp. 330-341."},{"key":"325537_CR13","unstructured":"K. Erol, D.S. Nau and V.S. Subrahmanian, On the complexity of domain-independent planning, in: Proc. AAAI '92 (AAAI Press\/MIT Press, 1992) pp. 381-386."},{"key":"325537_CR14","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0004-3702(71)90010-5","volume":"2","author":"R.E. Fikes","year":"1971","unstructured":"R.E. Fikes and N.J. Nilsson, STRIPS: A new approach to the application of theorem proving to problem solving, Artif. Intell. 2 (1971) 189-208.","journal-title":"Artif. Intell."},{"issue":"1\u20132","key":"325537_CR15","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/0004-3702(94)00077-E","volume":"76","author":"M.L. Ginsberg","year":"1995","unstructured":"M.L. Ginsberg, Approximate planning, Artif. Intell. 76(1\u20132) (1995) 89-123.","journal-title":"Artif. Intell."},{"key":"325537_CR16","doi-asserted-by":"crossref","first-page":"356","DOI":"10.1109\/SCT.1994.315789","volume-title":"Proc. 9th Conference on Structure in Complexity Theory","author":"H. Hunt III","year":"1994","unstructured":"H. Hunt III, M. Marathe and R. Stearns, Generalized CNF satisfiability problems and non-efficient approximability, in: Proc. 9th Conference on Structure in Complexity Theory (IEEE Computer Society Press, Los Alamitos, CA, 1994) pp. 356-366."},{"key":"325537_CR17","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/S0020-0190(97)00112-9","volume":"63","author":"P. Jonsson","year":"1997","unstructured":"P. Jonsson, A non-approximability result for finite function generation, Inform. Process. Lett. 63 (1997) 143-145.","journal-title":"Inform. Process. Lett."},{"key":"325537_CR18","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/0004-3702(87)90051-8","volume":"33","author":"R.E. Korf","year":"1987","unstructured":"R.E. Korf, Planning as search: A quantitative approach, Artif. Intell. 33 (1987) 65-88.","journal-title":"Artif. Intell."},{"key":"325537_CR19","first-page":"275","volume":"1","author":"M. Marathe","year":"1994","unstructured":"M. Marathe, H. Hunt III and S. Ravi, The complexity of approximating PSPACE-complete problems for hierarchical specifications, Nordic J. Comput. 1 (1994) 275-316.","journal-title":"Nordic J. Comput."},{"key":"325537_CR20","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1145\/800076.802475","volume-title":"Proc. STOC '81","author":"J. Orlin","year":"1981","unstructured":"J. Orlin, The complexity of dynamic languages and dynamic optimization problems, in: Proc. STOC '81 (ACM Press, New York, 1981) pp. 218-227."},{"issue":"2","key":"325537_CR21","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"W.J. Savitch","year":"1970","unstructured":"W.J. Savitch, Relationships between nondeterministic and deterministic tape complexities, J. Comput. Syst. Sci. 4(2) (1970) 177-192.","journal-title":"J. Comput. Syst. Sci."},{"key":"325537_CR22","first-page":"521","volume-title":"Proc. KR '94","author":"B. Selman","year":"1994","unstructured":"B. Selman, Near-optimal plans, tractability, and reactivity, in: Proc. KR '94 (Morgan Kaufmann, San Mateo, CA, 1994) pp. 521-529."}],"container-title":["Annals of Mathematics and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1018954827926.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1018954827926\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1018954827926.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,18]],"date-time":"2025-05-18T05:35:26Z","timestamp":1747546526000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1018954827926"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999,2]]},"references-count":22,"journal-issue":{"issue":"1-4","published-print":{"date-parts":[[1999,2]]}},"alternative-id":["325537"],"URL":"https:\/\/doi.org\/10.1023\/a:1018954827926","relation":{},"ISSN":["1012-2443","1573-7470"],"issn-type":[{"type":"print","value":"1012-2443"},{"type":"electronic","value":"1573-7470"}],"subject":[],"published":{"date-parts":[[1999,2]]}}}