{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:21:41Z","timestamp":1759638101218,"version":"3.41.0"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2021,1,21]],"date-time":"2021-01-21T00:00:00Z","timestamp":1611187200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004359","name":"Vetenskapsr\u00e5det","doi-asserted-by":"publisher","award":["2019-03690","2017-04112"],"award-info":[{"award-number":["2019-03690","2017-04112"]}],"id":[{"id":"10.13039\/501100004359","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2021,3,31]]},"abstract":"<jats:p>\n            We study the constraint satisfaction problem (CSP) parameterized by a constraint language \u0393 (CSP\u0393) and how the choice of \u0393 affects its worst-case time complexity. Under the exponential-time hypothesis (ETH), we rule out the existence of subexponential algorithms for finite-domain NP-complete CSP\u0393 problems. This extends to certain infinite-domain CSPs and structurally restricted problems. For CSPs with finite domain\n            <jats:italic>D<\/jats:italic>\n            and where all unary relations are available, we identify a relation\n            <jats:italic>S<\/jats:italic>\n            <jats:sub>\n              <jats:italic>D<\/jats:italic>\n            <\/jats:sub>\n            such that the time complexity of the NP-complete problem CSP({\n            <jats:italic>\n              S\n              <jats:sub>D<\/jats:sub>\n            <\/jats:italic>\n            }) is a lower bound for all NP-complete CSPs of this kind. We also prove that the time complexity of CSP({\n            <jats:italic>\n              S\n              <jats:sub>D<\/jats:sub>\n            <\/jats:italic>\n            }) strictly decreases when |D| increases (unless the ETH is false) and provide stronger complexity results in the special case when |D|=3.\n          <\/jats:p>","DOI":"10.1145\/3434387","type":"journal-article","created":{"date-parts":[[2021,1,21]],"date-time":"2021-01-21T11:11:18Z","timestamp":1611227478000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Fine-Grained Time Complexity of Constraint Satisfaction Problems"],"prefix":"10.1145","volume":"13","author":[{"given":"Peter","family":"Jonsson","sequence":"first","affiliation":[{"name":"Link\u00f6ping University, \u00d6sterg\u00f6tland, Sweden"}]},{"given":"Victor","family":"Lagerkvist","sequence":"additional","affiliation":[{"name":"Link\u00f6ping University, \u00d6sterg\u00f6tland, Sweden"}]},{"given":"Biman","family":"Roy","sequence":"additional","affiliation":[{"name":"Independent Researcher, \u00d6sterg\u00f6tland, Sweden"}]}],"member":"320","published-online":{"date-parts":[[2021,1,21]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1515\/dma.1994.4.5.401"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2677161.2677165"},{"volume-title":"Proceedings of the 31st Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS\u201916)","author":"Barto L.","key":"e_1_2_1_3_1","unstructured":"L. Barto and M. Pinsker . 2016. The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems . In Proceedings of the 31st Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS\u201916) . ACM, New York, NY, 615--622. L. Barto and M. Pinsker. 2016. The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems. In Proceedings of the 31st Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS\u201916). ACM, New York, NY, 615--622."},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1007\/s00224-018-9896-8","article-title":"Minimal distance of propositional models","volume":"63","author":"Behrisch M.","year":"2019","unstructured":"M. Behrisch , M. Hermann , S. Mengel , and G. Salzer . 2019 . Minimal distance of propositional models . Theory of Computing Systems 63 , 6 (Aug. 2019), 1131--1184. M. Behrisch, M. Hermann, S. Mengel, and G. Salzer. 2019. Minimal distance of propositional models. Theory of Computing Systems 63, 6 (Aug. 2019), 1131--1184.","journal-title":"Theory of Computing Systems"},{"key":"e_1_2_1_5_1","unstructured":"M. Bodirsky. 2012. Complexity classification in infinite-domain constraint satisfaction. M\u00e9moire d\u2019habilitation \u00e0 diriger des recherches Universit\u00e9 Diderot -- Paris 7. Available at arXiv:1201.0856.  M. Bodirsky. 2012. Complexity classification in infinite-domain constraint satisfaction. M\u00e9moire d\u2019habilitation \u00e0 diriger des recherches Universit\u00e9 Diderot -- Paris 7. Available at arXiv:1201.0856."},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","DOI":"10.1145\/3105907","article-title":"The complexity of phylogeny constraint satisfaction problems","volume":"18","author":"Bodirsky M.","year":"2017","unstructured":"M. Bodirsky , P. Jonsson , and T. V. Pham . 2017 . The complexity of phylogeny constraint satisfaction problems . ACM Transactions on Computational Logic 18 , 3 (2017), 23:1--23:42. M. Bodirsky, P. Jonsson, and T. V. Pham. 2017. The complexity of phylogeny constraint satisfaction problems. ACM Transactions on Computational Logic 18, 3 (2017), 23:1--23:42.","journal-title":"ACM Transactions on Computational Logic"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1007\/s00224-007-9083-9","article-title":"The complexity of equality constraint languages","volume":"43","author":"Bodirsky M.","year":"2008","unstructured":"M. Bodirsky and J. K\u00e1ra . 2008 . The complexity of equality constraint languages . Theory of Computing Systems 43 , 2 (Aug. 2008), 136--158. M. Bodirsky and J. K\u00e1ra. 2008. The complexity of equality constraint languages. Theory of Computing Systems 43, 2 (Aug. 2008), 136--158.","journal-title":"Theory of Computing Systems"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","DOI":"10.1145\/1667053.1667058","article-title":"The complexity of temporal constraint satisfaction problems","volume":"57","author":"Bodirsky M.","year":"2010","unstructured":"M. Bodirsky and J. K\u00e1ra . 2010 . The complexity of temporal constraint satisfaction problems . Journal of the ACM 57 , 2, Article 9 (2010), 41 pages. M. Bodirsky and J. K\u00e1ra. 2010. The complexity of temporal constraint satisfaction problems. Journal of the ACM 57, 2, Article 9 (2010), 41 pages.","journal-title":"Journal of the ACM"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","DOI":"10.1145\/2764899","article-title":"Schaefer\u2019s theorem for graphs","volume":"62","author":"Bodirsky M.","year":"2015","unstructured":"M. Bodirsky and M. Pinsker . 2015 . Schaefer\u2019s theorem for graphs . Journal of the ACM 62 , 3, Article 19 (June 2015), 52 pages. M. Bodirsky and M. Pinsker. 2015. Schaefer\u2019s theorem for graphs. Journal of the ACM 62, 3, Article 19 (June 2015), 52 pages.","journal-title":"Journal of the ACM"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01070906"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01267873"},{"volume-title":"Proceedings of the 16th International Workshop on Computer Science Logic (CSL\u201902)","author":"B\u00f6hler E.","key":"e_1_2_1_12_1","unstructured":"E. B\u00f6hler , E. Hemaspaandra , S. Reith , and H. Vollmer . 2002. Equivalence and isomorphism for Boolean constraint satisfaction . In Proceedings of the 16th International Workshop on Computer Science Logic (CSL\u201902) . Springer Berlin, Berlin, 412--426. E. B\u00f6hler, E. Hemaspaandra, S. Reith, and H. Vollmer. 2002. Equivalence and isomorphism for Boolean constraint satisfaction. In Proceedings of the 16th International Workshop on Computer Science Logic (CSL\u201902). Springer Berlin, Berlin, 412--426."},{"volume-title":"Complexity of Constraints","author":"B\u00f6rner F.","key":"e_1_2_1_13_1","unstructured":"F. B\u00f6rner . 2008. Basics of Galois connections . In Complexity of Constraints , N. Creignou, P. G. Kolaitis, and H. Vollmer (Eds.). Lecture Notes in Computer Science, Vol. 5250 . Springer Berlin , 38--67. F. B\u00f6rner. 2008. Basics of Galois connections. In Complexity of Constraints, N. Creignou, P. G. Kolaitis, and H. Vollmer (Eds.). Lecture Notes in Computer Science, Vol. 5250. Springer Berlin, 38--67."},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","DOI":"10.1145\/1970398.1970400","article-title":"Complexity of conservative constraint satisfaction problems","volume":"12","author":"Bulatov A.","year":"2011","unstructured":"A. Bulatov . 2011 . Complexity of conservative constraint satisfaction problems . ACM Transactions on Computational Logic 12 , 4, Article 24 (July 2011), 66 pages. A. Bulatov. 2011. Complexity of conservative constraint satisfaction problems. ACM Transactions on Computational Logic 12, 4, Article 24 (July 2011), 66 pages.","journal-title":"ACM Transactions on Computational Logic"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.37"},{"key":"e_1_2_1_16_1","first-page":"117","article-title":"Counting problems and clones of functions","volume":"18","author":"Bulatov A.","year":"2012","unstructured":"A. Bulatov and A. Hedayaty . 2012 . Counting problems and clones of functions . Multiple-Valued Logic and Soft Computing 18 , 2 (2012), 117 -- 138 . A. Bulatov and A. Hedayaty. 2012. Counting problems and clones of functions. Multiple-Valued Logic and Soft Computing 18, 2 (2012), 117--138.","journal-title":"Multiple-Valued Logic and Soft Computing"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376676"},{"key":"e_1_2_1_18_1","volume-title":"Lecture Notes in Computer Science","volume":"5917","author":"Calabro C.","unstructured":"C. Calabro , R. Impagliazzo , and R. Paturi . 2009. The complexity of satisfiability of small depth circuits. In Parameterized and Exact Computation, J. Chen and F. V. Fomin (Eds.) . Lecture Notes in Computer Science , Vol. 5917 . Springer Berlin, 75--85. C. Calabro, R. Impagliazzo, and R. Paturi. 2009. The complexity of satisfiability of small depth circuits. In Parameterized and Exact Computation, J. Chen and F. V. Fomin (Eds.). Lecture Notes in Computer Science, Vol. 5917. Springer Berlin, 75--85."},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1007\/s10601-015-9198-6","article-title":"Tractability in constraint satisfaction problems: a survey","volume":"21","author":"Carbonnel C.","year":"2016","unstructured":"C. Carbonnel and M. C. Cooper . 2016 . Tractability in constraint satisfaction problems: a survey . Constraints 21 , 2 (Apr. 2016), 115--144. C. Carbonnel and M. C. Cooper. 2016. Tractability in constraint satisfaction problems: a survey. Constraints 21, 2 (Apr. 2016), 115--144.","journal-title":"Constraints"},{"key":"e_1_2_1_20_1","volume-title":"Dagstuhl Follow-Ups","volume":"7","author":"Cooper M. C.","unstructured":"M. C. Cooper and S. Z\u01d0vn\u00fd . 2017. Hybrid tractable classes of constraint problems. In The Constraint Satisfaction Problem: Complexity and Approximability, Andrei Krokhin and Stanislav Z\u01d0vn\u00fd (Eds.) . Dagstuhl Follow-Ups , Vol. 7 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 113--135. M. C. Cooper and S. Z\u01d0vn\u00fd. 2017. Hybrid tractable classes of constraint problems. In The Constraint Satisfaction Problem: Complexity and Approximability, Andrei Krokhin and Stanislav Z\u01d0vn\u00fd (Eds.). Dagstuhl Follow-Ups, Vol. 7. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 113--135."},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","DOI":"10.1145\/2629421","article-title":"Complexity Classifications for Logic-Based Argumentation","volume":"15","author":"Creignou N.","year":"2014","unstructured":"N. Creignou , U. Egly , and J. Schmidt . 2014 . Complexity Classifications for Logic-Based Argumentation . ACM Transactions on Computational Logic 15 , 3 (2014), 19:1--19:20. N. Creignou, U. Egly, and J. Schmidt. 2014. Complexity Classifications for Logic-Based Argumentation. ACM Transactions on Computational Logic 15, 3 (2014), 19:1--19:20.","journal-title":"ACM Transactions on Computational Logic"},{"volume-title":"Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201916)","author":"Cygan M.","key":"e_1_2_1_22_1","unstructured":"M. Cygan , F. V. Fomin , A. Golovnev , A. S. Kulikov , I. Mihajlin , J. Pachocki , and A. Soca\u0142a . 2016. Tight bounds for graph homomorphism and subgraph isomorphism . In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201916) . Society for Industrial and Applied Mathematics, Philadelphia, PA, 1643--1649. M. Cygan, F. V. Fomin, A. Golovnev, A. S. Kulikov, I. Mihajlin, J. Pachocki, and A. Soca\u0142a. 2016. Tight bounds for graph homomorphism and subgraph isomorphism. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201916). Society for Industrial and Applied Mathematics, Philadelphia, PA, 1643--1649."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/2831407.2831411"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"e_1_2_1_25_1","volume-title":"A completeness criterion for partial functions of logic and many-valued logic algebras. Soviet Physics Doklady 11 (Oct","author":"Freivald R. V.","year":"1966","unstructured":"R. V. Freivald . 1966. A completeness criterion for partial functions of logic and many-valued logic algebras. Soviet Physics Doklady 11 (Oct . 1966 ), 288. R. V. Freivald. 1966. A completeness criterion for partial functions of logic and many-valued logic algebras. Soviet Physics Doklady 11 (Oct. 1966), 288."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1968.27.95"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 31st International Symposium on Mathematical Foundations of Computer Science (MFCS\u201906)","author":"Grohe M.","year":"2006","unstructured":"M. Grohe . 2006 . The structure of tractable constraint satisfaction problems . In Proceedings of the 31st International Symposium on Mathematical Foundations of Computer Science (MFCS\u201906) . Springer Berlin, Berlin,58--72. M. Grohe. 2006. The structure of tractable constraint satisfaction problems. In Proceedings of the 31st International Symposium on Mathematical Foundations of Computer Science (MFCS\u201906). Springer Berlin, Berlin,58--72."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.03.006"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/120868177"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo R. Paturi and F. Zane. 2001. Which problems have strongly exponential complexity?Journal of Computer and System Sciences 63 4 (2001) 512--530.  R. Impagliazzo R. Paturi and F. Zane. 2001. Which problems have strongly exponential complexity?Journal of Computer and System Sciences 63 4 (2001) 512--530.","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00230-2"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009890709297"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2017.01.005"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2016.07.008"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48057-1_28"},{"volume-title":"Mathematics and Its Applications","author":"P\u00f6schel R.","key":"e_1_2_1_37_1","unstructured":"R. P\u00f6schel . 2004. Galois connections for operations and relations . In Galois Connections and Applications, K. Denecke, M. Ern\u00e9, and S.L. Wismath (Eds.). Mathematics and Its Applications , Vol. 565 . Springer Netherlands , 231--258. R. P\u00f6schel. 2004. Galois connections for operations and relations. In Galois Connections and Applications, K. Denecke, M. Ern\u00e9, and S.L. Wismath (Eds.). Mathematics and Its Applications, Vol. 565. Springer Netherlands, 231--258."},{"key":"e_1_2_1_38_1","first-page":"1","article-title":"The two-valued iterative systems of mathematical logic","volume":"5","author":"Post E.","year":"1941","unstructured":"E. Post . 1941 . The two-valued iterative systems of mathematical logic . Annals of Mathematical Studies 5 (1941), 1 -- 122 . E. Post. 1941. The two-valued iterative systems of mathematical logic. Annals of Mathematical Studies 5 (1941), 1--122.","journal-title":"Annals of Mathematical Studies"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01069627"},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/j.disc.2005.11.033","article-title":"The completeness problem in partial hyperclones","volume":"306","author":"Romov B. A.","year":"2006","unstructured":"B. A. Romov . 2006 . The completeness problem in partial hyperclones . Discrete Mathematics 306 , 13 (July 2006), 1405--1414. B. A. Romov. 2006. The completeness problem in partial hyperclones. Discrete Mathematics 306, 13 (July 2006), 1405--1414.","journal-title":"Discrete Mathematics"},{"key":"e_1_2_1_41_1","volume-title":"Foundations of Artificial Intelligence","volume":"2","author":"Rossi F.","year":"2006","unstructured":"F. Rossi , P. van Beek , and T. Walsh ( Eds .). 2006 . Handbook of Constraint Programming . Foundations of Artificial Intelligence , Vol. 2 . Elsevier. F. Rossi, P. van Beek, and T. Walsh (Eds.). 2006. Handbook of Constraint Programming. Foundations of Artificial Intelligence, Vol. 2. Elsevier."},{"key":"e_1_2_1_42_1","unstructured":"S. J. Russell and P. Norvig. 2010. Artificial Intelligence - A Modern Approach (3rd internat. ed.). Pearson Education.  S. J. Russell and P. Norvig. 2010. Artificial Intelligence - A Modern Approach (3rd internat. ed.). Pearson Education."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"e_1_2_1_44_1","volume-title":"Lecture Notes in Computer Science","volume":"5250","author":"Schnoor H.","unstructured":"H. Schnoor and I. Schnoor . 2008. Partial polymorphisms and constraint satisfaction problems. In Complexity of Constraints, N. Creignou, P. G. Kolaitis, and H. Vollmer (Eds.) . Lecture Notes in Computer Science , Vol. 5250 . Springer Berlin Heidelberg, 229--254. H. Schnoor and I. Schnoor. 2008. Partial polymorphisms and constraint satisfaction problems. In Complexity of Constraints, N. Creignou, P. G. Kolaitis, and H. Vollmer (Eds.). Lecture Notes in Computer Science, Vol. 5250. Springer Berlin Heidelberg, 229--254."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00012-015-0330-7"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.38"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3434387","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3434387","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:31:47Z","timestamp":1750195907000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3434387"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,21]]},"references-count":46,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,3,31]]}},"alternative-id":["10.1145\/3434387"],"URL":"https:\/\/doi.org\/10.1145\/3434387","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2021,1,21]]},"assertion":[{"value":"2019-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-01-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}