{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:05:15Z","timestamp":1750694715203,"version":"3.41.0"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2014,5,1]],"date-time":"2014-05-01T00:00:00Z","timestamp":1398902400000},"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":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2014,5]]},"abstract":"<jats:p>\n            If the class TAUT of tautologies of propositional logic has no almost optimal algorithm, then every algorithm A deciding TAUT has a hard sequence, that is, a polynomial time computable sequence witnessing that A is not almost optimal. We show that this result extends to every \u03a0\n            <jats:italic>t<\/jats:italic>\n            <jats:italic>p<\/jats:italic>\n            -complete problem with\n            <jats:italic>t<\/jats:italic>\n            \u22651; however, assuming the Measure Hypothesis, there is a problem which has no almost optimal algorithm but is decided by an algorithm without hard sequences. For problems\n            <jats:italic>Q<\/jats:italic>\n            with an almost optimal algorithm, we analyze whether every algorithm deciding\n            <jats:italic>Q<\/jats:italic>\n            , which is not almost optimal, has a hard sequence.\n          <\/jats:p>","DOI":"10.1145\/2601336","type":"journal-article","created":{"date-parts":[[2014,6,10]],"date-time":"2014-06-10T12:50:17Z","timestamp":1402404617000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Hard Instances of Algorithms and Proof Systems"],"prefix":"10.1145","volume":"6","author":[{"given":"Yijia","family":"Chen","sequence":"first","affiliation":[{"name":"Shanghai Jiaotong University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00f6rg","family":"Flum","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Freiburg"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Moritz","family":"M\u00fcller","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Wien"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,5]]},"reference":[{"volume-title":"Proceedings of the Electronic Colloquium on Computational Complexity (ECCC), TR98-021","author":"Ben-David S.","key":"e_1_2_1_1_1","unstructured":"S. Ben-David and A. Gringauze . 1998. On the existence of propositional proof systems and oracle-relativized propositional logic . In Proceedings of the Electronic Colloquium on Computational Complexity (ECCC), TR98-021 . S. Ben-David and A. Gringauze. 1998. On the existence of propositional proof systems and oracle-relativized propositional logic. In Proceedings of the Electronic Colloquium on Computational Complexity (ECCC), TR98-021."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1976.22"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206023"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1002\/malq.201010021"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/646251.756781"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP\u201910","volume":"6199","author":"Chen Y.","unstructured":"Y. Chen and J. Flum . 2010. On p-optimal proof systems and logics for PTIME . In Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP\u201910 , Track B). Lecture Notes in Computer Science, 6199 , vol. 6199 , Springer, 321--332. Y. Chen and J. Flum. 2010. On p-optimal proof systems and logics for PTIME. In Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP\u201910, Track B). Lecture Notes in Computer Science, 6199, vol. 6199, Springer, 321--332."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2011.17"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Y. Chen and J. Flum. 2014. On optimal inverters. Bull. Symb. Logic. To appear.  Y. Chen and J. Flum. 2014. On optimal inverters. Bull. Symb. Logic . To appear.","DOI":"10.1017\/bsl.2013.2"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0235-8"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210061"},{"volume-title":"Proceedings of the 13th Annual IEEE Conference on Computational Complexity (CCC\u201998)","author":"K\u00f6bler J.","key":"e_1_2_1_11_1","unstructured":"J. K\u00f6bler and J. Messner . 1998. Complete problems for promise classes by optimal proof systems for test sets . In Proceedings of the 13th Annual IEEE Conference on Computational Complexity (CCC\u201998) . Springer, 132--140. J. K\u00f6bler and J. Messner. 1998. Complete problems for promise classes by optimal proof systems for test sets. In Proceedings of the 13th Annual IEEE Conference on Computational Complexity (CCC\u201998). Springer, 132--140."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(03)00058-0"},{"volume-title":"Propositional Logic, and Complexity Theory","author":"Kraj\u00ed\u010dek J.","key":"e_1_2_1_13_1","unstructured":"J. Kraj\u00ed\u010dek . 1995. Bounded Arithmetic , Propositional Logic, and Complexity Theory . Cambridge University Press . J. Kraj\u00ed\u010dek. 1995. Bounded Arithmetic, Propositional Logic, and Complexity Theory. Cambridge University Press."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2012.03.009"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1112\/blms\/bdt071"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.2307\/2274765"},{"key":"e_1_2_1_17_1","first-page":"265","article-title":"Universal sequential search problems","volume":"9","author":"Levin L.","year":"1973","unstructured":"L. Levin . 1973 . Universal sequential search problems . Prob. Inf. Transmiss. 9 , 3, 265 -- 266 . L. Levin. 1973. Universal sequential search problems. Prob. Inf. Transmiss. 9, 3, 265--266.","journal-title":"Prob. Inf. Transmiss."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02679469"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"J. H. Lutz. 1997b. The quantitative structure of exponential time. Complexity Theory Retrospective II 225--254.   J. H. Lutz. 1997b. The quantitative structure of exponential time. Complexity Theory Retrospective II 225--254.","DOI":"10.1007\/978-1-4612-1872-2_10"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00023-C"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/1764891.1764962"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.09.029"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00155-4"},{"key":"e_1_2_1_25_1","first-page":"1","article-title":"Optimal proof systems, optimal acceptors and recursive presentability","volume":"79","author":"Sadowski Z.","year":"2007","unstructured":"Z. Sadowski . 2007 . Optimal proof systems, optimal acceptors and recursive presentability . Fund. Informat. 79 , 1 -- 2 , 169--185. Z. Sadowski. 2007. Optimal proof systems, optimal acceptors and recursive presentability. Fund. Informat. 79, 1--2, 169--185.","journal-title":"Fund. Informat."},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 3rd International Colloquium on Automata, Languages and Programming (ICALP\u201976)","author":"Schnorr C. P.","year":"1976","unstructured":"C. P. Schnorr . 1976 . Optimal algorithms for self-reducible problems . In Proceedings of the 3rd International Colloquium on Automata, Languages and Programming (ICALP\u201976) . Edinburgh University Press, 322--337. C. P. Schnorr. 1976. Optimal algorithms for self-reducible problems. In Proceedings of the 3rd International Colloquium on Automata, Languages and Programming (ICALP\u201976). Edinburgh University Press, 322--337."},{"key":"e_1_2_1_28_1","unstructured":"O. V. Verbitsky. 1979. Optimal algorithms for coNP-sets and the problem EXP=NEXP. Matemat. zametki 50 2 37--46.  O. V. Verbitsky. 1979. Optimal algorithms for coNP-sets and the problem EXP=NEXP. Matemat. zametki 50 2 37--46."}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2601336","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2601336","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:00:53Z","timestamp":1750276853000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2601336"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,5]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,5]]}},"alternative-id":["10.1145\/2601336"],"URL":"https:\/\/doi.org\/10.1145\/2601336","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2014,5]]},"assertion":[{"value":"2013-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-05-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}