{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T18:17:08Z","timestamp":1781893028348,"version":"3.54.5"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2012,8,1]],"date-time":"2012-08-01T00:00:00Z","timestamp":1343779200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2012,8]]},"abstract":"<jats:p>\n            Let C denote one of the complexity classes \u201cpolynomial time,\u201d \u201clogspace,\u201d or \u201cnondeterministic logspace.\u201d We introduce a logic\n            <jats:italic>L<\/jats:italic>\n            (C)\n            <jats:sub>inv<\/jats:sub>\n            and show generalizations and variants of the equivalence (\n            <jats:italic>L<\/jats:italic>\n            (C)\n            <jats:sub>inv<\/jats:sub>\n            captures C if and only if there is an almost C-optimal algorithm in C for the set\n            <jats:sc>Taut<\/jats:sc>\n            of tautologies of propositional logic). These statements are also equivalent to the existence of a listing of subsets in C of\n            <jats:sc>Taut<\/jats:sc>\n            by corresponding Turing machines and equivalent to the fact that a certain parameterized halting problem is in the parameterized complexity class XC\n            <jats:sub>uni<\/jats:sub>\n            .\n          <\/jats:p>","DOI":"10.1145\/2339123.2339124","type":"journal-article","created":{"date-parts":[[2012,9,4]],"date-time":"2012-09-04T12:50:47Z","timestamp":1346763047000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["From Almost Optimal Algorithms to Logics for Complexity Classes via Listings and a Halting Problem"],"prefix":"10.1145","volume":"59","author":[{"given":"Yijia","family":"Chen","sequence":"first","affiliation":[{"name":"Shanghai Jiaotong University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"J\u00f6rg","family":"Flum","sequence":"additional","affiliation":[{"name":"Albert-Ludwigs-Universit\u00e4t Freiburg"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2012,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90012-5"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Chen Y. and Flum J. 2010a. A logic for PTIME and a parameterized halting problem. In Fields of Logic and Computation. Springer 251--276. Chen Y. and Flum J. 2010a. A logic for PTIME and a parameterized halting problem. In Fields of Logic and Computation . Springer 251--276.","DOI":"10.1007\/978-3-642-15025-8_14"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1880999.1881034"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1887459.1887479"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1264433918"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2011.17"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.2307\/2273702"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Downey R. and Fellows M. 1999. Parameterized Complexity. Springer-Verlag. Downey R. and Fellows M. 1999. Parameterized Complexity . Springer-Verlag.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the Conference on Complexity of Computation. R. M. Karp Ed., SIAM","volume":"7","author":"Fagin R.","year":"1974"},{"key":"e_1_2_1_10_1","unstructured":"Flum J. and Grohe M. 2006. Parameterized Complexity Theory. Springer. Flum J. and Grohe M. 2006. Parameterized Complexity Theory . Springer."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1807662.1807667"},{"key":"e_1_2_1_12_1","volume-title":"Current Trends in Theoretical Computer Science","author":"Gurevich Y."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(88)90022-9"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30538-5_28"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(86)80029-8"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216051"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217058"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(03)00058-0"},{"key":"e_1_2_1_19_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of Mathematical Foundations of Computer Science 1984 (MFCS\u201984)","author":"Kowalczyk K."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.2307\/2274765"},{"key":"e_1_2_1_21_1","first-page":"265","article-title":"Universal search problems","volume":"9","author":"Levin L.","year":"1973","journal-title":"Problems Inf. Transmission"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/646513.695503"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30570-5_19"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00155-4"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802186"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2339123.2339124","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2339123.2339124","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:21:08Z","timestamp":1750238468000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2339123.2339124"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,8]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,8]]}},"alternative-id":["10.1145\/2339123.2339124"],"URL":"https:\/\/doi.org\/10.1145\/2339123.2339124","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,8]]},"assertion":[{"value":"2011-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-08-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}