strong exponential time hypothesis (seth)

Exact Algorithms and Strong Exponential Time Hypothesis

• Reference work entry
• First Online: 01 January 2016
• Cite this reference work entry

• Joshua R. Wang 2 &
• Ryan Williams 3  

89 Accesses

1 Citations

Years and Authors of Summarized Original Work

2010; Păatraşscu, Williams

2011; Lokshtanov, Marx, Saurabh

2012; Cygan, Dell, Lokshtanov, Marx, Nederlof, Okamoto, Paturi, Saurabh, Wahlström

Problem Definition

All problems in NP can be exactly solved in 2 poly( n ) time via exhaustive search, but research has yielded faster exponential-time algorithms for many NP-hard problems. However, some key problems have not seen improved algorithms, and problems with improvements seem to converge toward O ( C n ) for some unknown constant C  > 1.

The satisfiability problem for Boolean formulas in conjunctive normal form, CNF-SAT, is a central problem that has resisted significant improvements. The complexity of CNF-SAT and its special case k -SAT, where each clause has k literals, is the canonical starting point for the development of NP-completeness theory.

Similarly, in the last 20 years, two hypotheses have emerged as powerful starting points for understanding exponential-time complexity. In 1999,...

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save.

• Get 10 units per month
• Download Article/Chapter or eBook
• 1 Unit = 1 Article or 1 Chapter
• Cancel anytime
• Available as PDF
• Read on any device
• Instant download
• Own it forever
• Available as EPUB and PDF
• Durable hardcover edition
• Dispatched in 3 to 5 business days
• Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Recommended Reading

Calabro C, Impagliazzo R, Paturi R (2009) The complexity of satisfiability of small depth circuits. In: Chen J, Fomin F (eds) Parameterized and exact computation. Lecture notes in computer science, vol 5917. Springer, Berlin/Heidelberg, pp 75–85. doi:10.1007/978-3-642-11269-0_6. http://dx.doi.org/10.1007/978-3-642-11269-0_6

Chen J, Chor B, Fellows M, Huang X, Juedes D, Kanj IA, Xia G (2005) Tight lower bounds for certain parameterized np-hard problems. Inf Comput 201(2):216–231. doi:http://dx.doi.org/10.1016/j.ic.2005.05.001. http://www.sciencedirect.com/science/article/pii/S0890540105000763

Cygan M, Dell H, Lokshtanov D, Marx D, Nederlof J, Okamoto Y, Paturi R, Saurabh S, Wahlstrom M (2012) On problems as hard as cnf-sat. In: Proceedings of the 2012 IEEE conference on computational complexity (CCC ’12), Washington, DC. IEEE Computer Society, pp 74–84. doi:10.1109/CCC.2012.36. http://dx.doi.org/10.1109/CCC.2012.36

Fomin F, Kratsch D (2010) Exact exponential algorithms. Texts in theoretical computer science, an EATCS series. Springer, Berlin/Heidelberg

Google Scholar  

Impagliazzo R, Paturi R (2001) On the complexity of k-sat. J Comput Syst Sci 62(2):367–375. doi:http://dx.doi.org/10.1006/jcss.2000.1727. http://www.sciencedirect.com/science/article/pii/S0022000000917276

Impagliazzo R, Paturi R, Zane F (2001) Which problems have strongly exponential complexity? J Comput Syst Sci 63(4):512–530. doi:http://dx.doi.org/10.1006/jcss.2001.1774. http://www.sciencedirect.com/science/article/pii/S002200000191774X

Lokshtanov D, Marx D, Saurabh S (2011) Known algorithms on graphs of bounded treewidth are probably optimal. In: Proceedings of the twenty-second Annual ACM-SIAM symposium on discrete algorithms (SODA ’11), San Francisco. SIAM, pp 777–789. http://dl.acm.org/citation.cfm?id=2133036.2133097

Chapter   Google Scholar  

Pătraşcu M, Williams R (2010) On the possibility of faster sat algorithms. In: Proceedings of the twenty-first annual ACM-SIAM symposium on discrete algorithms (SODA ’10), Philadelphia. Society for Industrial and Applied Mathematics, pp 1065–1075. http://dl.acm.org/citation.cfm?id=1873601.1873687

Woeginger G (2003) Exact algorithms for np-hard problems: a survey. In: Jünger M, Reinelt G, Rinaldi G (eds) Combinatorial optimization Eureka, you shrink! Lecture notes in computer science, vol 2570. Springer, Berlin/Heidelberg, pp 185–207. doi:10.1007/3-540-36478-1_17. http://dx.doi.org/10.1007/3-540-36478-1_17

Download references

Author information

Authors and affiliations.

Department of Computer Science, Stanford University, Stanford, CA, USA

Joshua R. Wang

Ryan Williams

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Joshua R. Wang .

Editor information

Editors and affiliations.

Department of Electrical Engineering and Computer Science, Northwestern University, Evanston, IL, USA

Ming-Yang Kao

Rights and permissions

Reprints and permissions

Copyright information

© 2016 Springer Science+Business Media New York

About this entry

Cite this entry.

Wang, J.R., Williams, R. (2016). Exact Algorithms and Strong Exponential Time Hypothesis. In: Kao, MY. (eds) Encyclopedia of Algorithms. Springer, New York, NY. https://doi.org/10.1007/978-1-4939-2864-4_519

Download citation

DOI : https://doi.org/10.1007/978-1-4939-2864-4_519

Published : 22 April 2016

Publisher Name : Springer, New York, NY

Print ISBN : 978-1-4939-2863-7

Online ISBN : 978-1-4939-2864-4

eBook Packages : Computer Science Reference Module Computer Science and Engineering

Share this entry

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Publish with us

Policies and ethics

• Find a journal
• Track your research

On the Usefulness of the Strong Exponential Time Hypothesis

Over the past 15 years or so, the Strong Exponential Time Hypothesis (SETH) has been very useful for proving conditional hardness for many problems: it's a problem at the heart of fine-grained complexity. In this talk, I will discuss another way in which SETH has been useful.

Video Recording

• Export ACM-XML
• Export DOAJ-XML
• Export Schema.org
• Export BibTeX

A Framework of Quantum Strong Exponential-Time Hypotheses

Authors harry buhrman , subhasree patro , florian speelman.

• Part of: Volume: 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021) Part of: Series: Leibniz International Proceedings in Informatics (LIPIcs) Part of: Conference: Symposium on Theoretical Aspects of Computer Science (STACS)

• Publication Date: 2021-03-10

• Filesize: 0.8 MB

Document Identifiers

• DOI: 10.4230/LIPIcs.STACS.2021.19
• URN: urn:nbn:de:0030-drops-136642

Author Details

• QuSoft, CWI, Amsterdam, The Netherlands
• University of Amsterdam, The Netherlands

Acknowledgements

Cite as get bibtex, subject classification, acm subject classification.

• Theory of computation → Problems, reductions and completeness
• Theory of computation → Quantum complexity theory
• complexity theory
• fine-grained complexity
• longest common subsequence
• edit distance
• quantum query complexity
• strong exponential-time hypothesis
• Access Statistics
• Total Accesses (updated on a weekly basis) 0 PDF Downloads 0 Metadata Views

Related Versions

• Full Version https://arxiv.org/abs/1911.05686
• Scott Aaronson, Nai-Hui Chia, Han-Hsuan Lin, Chunhao Wang, and Ruizhe Zhang. On the quantum complexity of closest pair and related problems. arXiv preprint, 2019. URL: http://arxiv.org/abs/1911.01973 .
• Scott Aaronson, Daniel Grier, and Luke Schaeffer. A Quantum Query Complexity Trichotomy for Regular Languages. Electronic Colloquium on Computational Complexity (ECCC), 26:61, 2019. URL: https://eccc.weizmann.ac.il/report/2019/061 .
• Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. Quadratic-time hardness of LCS and other sequence similarity measures. CoRR, abs/1501.07053, 2015. URL: http://arxiv.org/abs/1501.07053 .
• Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. Tight hardness results for LCS and other sequence similarity measures. In Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), FOCS '15, pages 59-78, Washington, DC, USA, 2015. IEEE Computer Society. URL: https://doi.org/10.1109/FOCS.2015.14 .
• Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, and Ryan Williams. Simulating Branching Programs with Edit Distance and Friends Or: a Polylog Shaved is a Lower Bound Made. In Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing, STOC '16, pages 375-388, New York, NY, USA, 2016. ACM. URL: https://doi.org/10.1145/2897518.2897653 .

• Amir Abboud, Virginia Vassilevska Williams, and Huacheng Yu. Matching triangles and basing hardness on an extremely popular conjecture. In Proceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing, STOC '15, pages 41-50, New York, NY, USA, 2015. ACM. URL: https://doi.org/10.1145/2746539.2746594 .
• Andris Ambainis. Quantum lower bounds by quantum arguments. In Proceedings of the Thirty-second Annual ACM Symposium on Theory of Computing, STOC '00, pages 636-643, New York, NY, USA, 2000. ACM. URL: https://doi.org/10.1145/335305.335394 .
• Andris Ambainis, Kaspars Balodis, Janis Iraids, Kamil Khadiev, Vladislavs Klevickis, Krisjanis Prusis, Yixin Shen, Juris Smotrovs, and Jevgenijs Vihrovs. Quantum lower and upper bounds for 2d-grid and dyck language. In Javier Esparza and Daniel Král', editors, 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020, August 24-28, 2020, Prague, Czech Republic, volume 170 of LIPIcs, pages 8:1-8:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.MFCS.2020.8 .
• Marshall Ball, Alon Rosen, Manuel Sabin, and Prashant Nalini Vasudevan. Proofs of useful work. Cryptology ePrint Archive, Report 2017/203, 2017. URL: https://eprint.iacr.org/2017/203 .
• Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum lower bounds by polynomials. J. ACM, 48(4):778-797, July 2001. URL: https://doi.org/10.1145/502090.502097 .
• Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. Strengths and weaknesses of quantum computing. SIAM J. Comput., 26(5):1510-1523, October 1997. URL: https://doi.org/10.1137/S0097539796300933 .
• E. Bernstein and U. Vazirani. Quantum complexity theory. SIAM Journal on Computing, 26(5):1411-1473, 1997. URL: https://doi.org/10.1137/S0097539796300921 .
• Mahdi Boroujeni, Soheil Ehsani, Mohammad Ghodsi, Mohammad Taghi Hajiaghayi, and Saeed Seddighin. Approximating edit distance in truly subquadratic time: Quantum and mapreduce. CoRR, abs/1804.04178, 2018. URL: http://arxiv.org/abs/1804.04178 .
• Karl Bringmann. Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless seth fails. In Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, FOCS '14, pages 661-670, Washington, DC, USA, 2014. IEEE Computer Society. URL: https://doi.org/10.1109/FOCS.2014.76 .
• Karl Bringmann and Marvin Kunnemann. Quadratic conditional lower bounds for string problems and dynamic time warping. In Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), FOCS '15, pages 79-97, Washington, DC, USA, 2015. IEEE Computer Society. URL: https://doi.org/10.1109/FOCS.2015.15 .
• Harry Buhrman, Subhasree Patro, and Florian Speelman. A framework of quantum strong exponential-time hypotheses, 2019. URL: http://arxiv.org/abs/1911.05686 .
• Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi. A duality between clause width and clause density for SAT. In Proceedings of the 21st Annual IEEE Conference on Computational Complexity, CCC '06, pages 252-260, Washington, DC, USA, 2006. IEEE Computer Society. URL: https://doi.org/10.1109/CCC.2006.6 .
• Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucký, and Michael E. Saks. Approximating edit distance within constant factor in truly sub-quadratic time. CoRR, abs/1810.03664, 2018. URL: http://arxiv.org/abs/1810.03664 .
• Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, and Magnus Wahlström. On problems as hard as CNF-SAT. ACM Trans. Algorithms, 12(3):41:1-41:24, May 2016. URL: https://doi.org/10.1145/2925416 .
• Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. Limit on the speed of quantum computation in determining parity. Phys. Rev. Lett., 81:5442-5444, December 1998. URL: https://doi.org/10.1103/PhysRevLett.81.5442 .
• Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing, STOC '96, pages 212-219, New York, NY, USA, 1996. ACM. URL: https://doi.org/10.1145/237814.237866 .
• Cupjin Huang, Michael Newman, and Mario Szegedy. Explicit lower bounds on strong quantum simulation. arXiv preprint, 2018. URL: http://arxiv.org/abs/1804.10368 .
• Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. Journal of Computer and System Sciences, 62(2):367-375, 2001. URL: https://doi.org/10.1006/jcss.2000.1727 .
• Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512-530, 2001. URL: https://doi.org/10.1006/jcss.2001.1774 .
• Robin Kothari. An optimal quantum algorithm for the oracle identification problem. In Ernst W. Mayr and Natacha Portier, editors, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), volume 25 of Leibniz International Proceedings in Informatics (LIPIcs), pages 482-493, Dagstuhl, Germany, 2014. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.STACS.2014.482 .
• William J. Masek and Michael S. Paterson. A faster algorithm computing string edit distances. Journal of Computer and System Sciences, 20(1):18-31, 1980. URL: https://doi.org/10.1016/0022-0000(80)90002-1 .
• Tomoyuki Morimae and Suguru Tamaki. Fine-grained quantum computational supremacy. Quantum Information & Computation, 19(13&14):1089-1115, 2019. URL: http://www.rintonpress.com/xxqic19/qic-19-1314/1089-1115.pdf .
• Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, and Francis Zane. An improved exponential-time algorithm for k-SAT. J. ACM, 52(3):337-364, May 2005. URL: https://doi.org/10.1145/1066100.1066101 .
• Jorg Van Renterghem. The implications of breaking the strong exponential time hypothesis on a quantum computer. Master’s thesis, Ghent University, 2019. URL: https://lib.ugent.be/fulltxt/RUG01/002/787/416/RUG01-002787416_2019_0001_AC.pdf .
• Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci., 348(2):357-365, December 2005. URL: https://doi.org/10.1016/j.tcs.2005.09.023 .

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Could not send message.

Computer Science & Engineering

Stefan Schneider (Theory Seminar)

Joint work with Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mikhailin and Ramamohan Paturi

Paper Link http://eccc.hpi-web.de/report/2015/148

Related: Final Defense of Stefan Schneider's Ph.D. dissertation in June 2017 .

Nondeterministic Strong Exponential Time Hypothesis (NSETH)

• 1 Target Problem
• 2 Description
• 3 Implies the following Hypothesis
• 4 Implied by the following Hypothesis
• 5 Computation Model
• 8 References/Citation

Target Problem

Description.

Refuting unsatisfiable $k$-CNF formulas on $n$ variables requires nondeterministic $2^{n-o(n)}$ time for unbounded $k$.

Implies the following Hypothesis

Implied by the following hypothesis, computation model.

No (Variants have been disproved)

References/Citation

http://people.csail.mit.edu/virgi/eccentri.pdf Hypothesis 10

Navigation menu

Stack Exchange Network

Stack Exchange network consists of 183 Q&A communities including Stack Overflow , the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Q&A for work

Connect and share knowledge within a single location that is structured and easy to search.

Is there a SETH (Strong Exponential Time Hypothesis) for CSP (Constraint Satisfaction Problem)?

The Constraint Satisfaction Problem I mentioned is similar to CNF-SAT: A variable can take values from some finite domain $D$ where $|D| = d$ . A literal of variable $x$ is an expression of the form $x\neq c$ , where $c\in D$ . A constraint is a disjunction of literals, and a formula is a conjunction of constraints. For example, let $D=\{0,1,2\}$ , then $$(x_1\neq 1\vee x_2\neq 0\vee x_3\neq 2)\wedge (x_2\neq 0\vee x_4\neq 2\vee x_5\neq 1)\wedge (x_3\neq 2\vee x_5\neq 0)$$ is a formula with $6$ variables and $3$ constraints. If we assign $x=0$ , then literal $x\neq 0$ evaluates to false, and literals $x\neq 1$ and $x\neq 2$ evaluate to true. A formula is satisfiable if an assignment makes the formula evaluate to true. In CSP, the task is to decide whether the input formula is satisfiable.

CSP with $n$ variables ranging over a domain of $d$ values can be solved in $O^*(d^n)$ time (the $O^*(\cdot)$ notation omits polynomial factor) by enumerating all possible assignments. Since CSP is a generalization of CNF-SAT, I wonder if there is any hypothesis about the worst-case runtime like SETH, e.g., CSP can not be solved in $O^*(d^{(1-\epsilon)n})$ time for any constant $\epsilon>0$ ?

Since CNF-SAT can be reduced to CSP with $d=2$ , what I want to know is the case when $d \geq 3$ .

My motivation for asking this question :

To the best of my knowledge, I did not find a better runtime for CSP. But I did not find any SETH-like hypothesis either. I am not sure if I missed something and if "SETH for CSP" is convincing.

Based on SETH, one can get a conditional lower bound for a problem by reducing CNF-SAT to it. This paradigm works not only for NP-hard problems but also for problems in P . So, if there is a SETH for CSP with $d\geq 3$ , maybe based on this, we can establish tighter condition lower bounds for some problems than those based on SETH for CNF-SAT?

• reference-request
• time-complexity
• lower-bounds

• 2 $\begingroup$ I assume that $d$ is constant and the number of terms in each clause is constant. 1) A variable with $d=2^k$ values can be used to encode $k$ boolean variables. For variable $x_i$ let's denote the corresponding boolean variables as $x_{i1}, \ldots, x_{ik}$. 2) You can write a condition on $x_{ij}$ by enumerating all matching values of $x_i$. E.g, if $x_{i1}$ corresponds to the lowest bit, then $x_{11} \lor \bar{x}_{22}$ can be written as $(x_1 \ne 0 \lor x_2 \ne 1) \land (x_1 \ne 2 \lor x_2 \ne 1) \land (x_1 \ne 0 \lor x_2 \ne 3) \land (x_1 \ne 2 \lor x_2 \ne 3)$. $\endgroup$ –  Dmitry Commented Nov 20, 2023 at 17:31
• 1 $\begingroup$ So, it gives a lower bound $\Omega((d/2)^{(1 - \epsilon) n})$ for arbitrary $d$. Probably you can get $\Omega(d^{(1 - \epsilon) n})$ with careful encoding. $\endgroup$ –  Dmitry Commented Nov 20, 2023 at 17:32
• $\begingroup$ @Dmitry I got your idea, but a little confused with the lower bound $\Omega((d/2)^{(1-\epsilon)n})$. Following your reduction, we can reduce CNF-SAT with $n$ variables to CSP with $d=2^k$ and $n'=\frac{n}{k}=\frac{n}{\log_{2}d}$ variables. So, a $d^{({1-\epsilon}n')}$-time algorithm for CSP yields a $d^{(1-\epsilon)\frac{n}{\log_{2}d}}=2^{(1-\epsilon)n}$-time algorithm for CNF-SAT, which refutes SETH. This gives a lower bound $\Omega(d^{(1-\epsilon)n})$ for $d$ being a power of two, since in the reduction, $k$ should be an integer. Am I right? $\endgroup$ –  Junqiang Peng Commented Nov 21, 2023 at 4:08
• 2 $\begingroup$ From the title I expected this question to be about general CSPs, but I see the question is only about one specific example of a CSP. Knowing that some CSPs are PTIME and some are NP-hard (and this is now known to be a dichotomy), one could wonder which of the hard CSPs are "equivalent" to SETH, i.e., assuming they are not solvable in subexponential time is equivalent to SETH? But there seems to be work in that direction already epubs.siam.org/doi/abs/10.1137/1.9781611973105.92 $\endgroup$ –  a3nm Commented Nov 24, 2023 at 18:15
• 2 $\begingroup$ FWIW, the CSP the OP asks about is "CSP-complete" via a fine-grained (arity- and #-of-variables-preserving) reduction, so the question is equivalent to asking about general CSPs. The idea is to map each general CSP constraint $C : [d]^k \to \{0, 1\}$ to $|C^{-1}(0)|$ many "OP CSP" (a.k.a $(d, k)$-SAT) constraints, each disallowing one of the assignments in $C^{-1}(0)$. $\endgroup$ –  Huck Bennett Commented Nov 24, 2023 at 23:16

2 Answers 2

This CSP is known to be SETH-hard. More precisely, assuming SETH, for any constant $\varepsilon > 0$ there is no $d^{(1-\varepsilon)n}$ -time algorithm for solving this CSP with domain size $d$ .

This is proved in Theorem 3.3 in https://eccc.weizmann.ac.il/report/2019/159/ . Note that their $q$ is your $d$ , and that they describe their $(q,k)$ -SAT constraints in a different but equivalent way (in both cases they're functions $[q]^k \to \{0,1\}$ such that the preimage of $0$ has size exactly $1$ , i.e., there's exactly one way to falsify each constraint).

• 1 $\begingroup$ Thank you, this is the best possible answer that I was hoping for. I'm a little surprised there wasn't such a statement until 2019. In the paper you referenced, it says: "In a different context, Traxler proved a slightly weaker result , which in our terminology corresponds to a lower bound of $2^{(1−\epsilon)n\lceil \log_{2}q\rceil}$. This is weaker, e.g., for constant $q$ that is not a power of two." $\endgroup$ –  Junqiang Peng Commented Nov 21, 2023 at 4:30
• $\begingroup$ I also noticed that in Section 3 of the paper you mentioned, it says "we will always take $q$ to be a prime power". I am not familiar with abstract algebra. So just to double-check, does the SETH-hardness proved in the paper hold for any constant $q$, or just for $q$ being a prime power? Thank you. $\endgroup$ –  Junqiang Peng Commented Nov 21, 2023 at 5:09
• $\begingroup$ There is a typo in the previous comment, the lower bound proved by Traxler should be $2^{(1-\epsilon)n\lfloor \log_{2}{q}\rfloor}$ (round-down instead of round-up). $\endgroup$ –  Junqiang Peng Commented Nov 21, 2023 at 9:36
• 2 $\begingroup$ The result holds for all integer $q \geq 2$, but the authors (only) use the case where $q$ is a prime power for their hardness results about coding problems. $\endgroup$ –  Huck Bennett Commented Nov 21, 2023 at 16:19
• $\begingroup$ Got it. Thanks for your explanation! $\endgroup$ –  Junqiang Peng Commented Nov 21, 2023 at 16:41

To give an alternative (slightly older) reference to the one proposed in another answer, the result "If the SETH is true, then $n$ -variable CSP over alphabets of size $d$ cannot be solved in time $(d-\varepsilon)^n$ " is given for all fixed $d\ge 3$ in my paper "Finer Tight Bounds for Coloring on Clique-width" ( https://arxiv.org/abs/1804.07975 ).

To be fair, and despite the self-promotion, I'm not actually claiming that I deserve credit for this result. The technique of mapping groups of binary variables of the original SAT instance into groups of $d$ -ary variables of the new instance, in a way that we don't mind that $\log d$ is not an integer, goes back to Lokshtanov, Marx, and Saurabh ( https://arxiv.org/abs/1007.5450 ), who used this to show that Dominating Set cannot be solved in time $(3-\varepsilon)^{tw}n^{O(1)}$ . The same technique has also been used in several follow-up papers that show lower bounds of the form $c^kn^{O(1)}$ , where $c$ is not a power of $2$ . My paper only puts what they already did in a packaged lemma that is easy to reuse. I guess this also implicitly addresses the comment that "This should have been known before 2019", since this paper is from 2010.

• $\begingroup$ Yes, your answer has really cleared up my doubts. Before now, my guess was that this result may have been given implicitly in some earlier paper (instead of 2019) that proves SETH-hardness for some specific problem. Thank you for providing these references. They are helpful to me. I gave you a vote since I have accepted the previous answer. $\endgroup$ –  Junqiang Peng Commented Nov 22, 2023 at 3:18
• 1 $\begingroup$ Hi Michael, cool, and sorry not to have known about your work (+1)! I read your Thm. 2 proof, and I think there's a small difference between it and the result I mentioned: you reduce $q$-SAT to $(qp)$-CSP-$B$ where arbitrary CSP constraints are allowed, and not just ones of the type mentioned by the OP. (In your reduction, an output $(qp)$-constraint has exactly one falsifying assignment iff the map from assignments to $V_{i_1} \cup \cdots \cup V_{i_q}$ to $X_{i_1} \cup \cdots \cup X_{i_q}$ is bijective and not just injective.) You can in turn reduce this to "$(qp)$-SAT-$B$" though. $\endgroup$ –  Huck Bennett Commented Nov 24, 2023 at 22:06

Your Answer

Sign up or log in, post as a guest.

Required, but never shown

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy .

Not the answer you're looking for? Browse other questions tagged reference-request time-complexity sat lower-bounds csp or ask your own question .

• Featured on Meta
• Site maintenance - Mon, Sept 16 2024, 21:00 UTC to Tue, Sept 17 2024, 2:00...
• User activation: Learnings and opportunities
• Join Stack Overflow’s CEO and me for the first Stack IRL Community Event in...

Hot Network Questions

• Latin lyrics to "Far away"
• How to easily detect new appended data with bpy?
• Why is resonance such a widespread phenomenon?
• Is it defamatory to publish nonsense under somebody else's name?
• How did people know that the war against the mimics was over?
• The consequence of a good letter of recommendation when things do not work out
• "There is a bra for every ket, but there is not a ket for every bra"
• On the history of algae classification
• How should I email HR after an unpleasant / annoying interview?
• When I use \llap to overlap words, the space between the overlapped words and the rest of the text is too much: how do I fix it?
• Copyright Fair Use: Is using the phrase "Courtesy of" legally acceptable when no permission has been given?
• What is the action-cost of grabbing spell components?
• How can I switch from MAG to TRU heading in a 737?
• Is it really a "space walk" (EVA proper) if you don't get your feet wet (in space)?
• Solaris 11 cbe: no more updates?
• Ubuntu 22.04.5 - Final Point Release
• The meaning of an implication with the existential quantifier
• Whom did Jesus' followers accompany -- a soldier or a civilian?
• 1950s comic book about bowling ball looking creatures that inhabit the underground of Earth
• Is it possible to draw this picture without lifting the pen? (I actually want to hang string lights this way in a gazebo without doubling up)
• Should I change advisors because mine doesn't object to publishing at MDPI?
• Why was Esther included in the canon?
• How frequently is random number generated when plotting function containing RandomReal?
• Stuck as a solo dev