Mathematics of the impossible, Chapter 8, Three impossibility results for 3Sat

Thoughts 2023-04-15

We should turn back to a traditional separation technique – diagonalization.[21]

In this chapter we put together many of the techniques we have seen to obtain several impossibility results for 3Sat. The template of all these results (and others, like those mentioned in section º5.1) is similar. All these results prove time bounds of the form $t\ge n^{1+\epsilon }$ where $\epsilon \in (0,1)$ . One can optimize the methods to push $\epsilon$ close to $1$ , but even establishing $\epsilon =1$ seems out of reach, and there are known barriers for current techniques [16].

8.1 Impossibility I

We begin with the following remarkable result.

Theorem 8.1. [21] Either $\text {3Sat}\not \in \text {L}$ or $\text {3Sat}\not \in \text {Time}(n^{1+\epsilon })$ for some constant $\epsilon$ .

Note that we don’t know if $\text {3Sat}\in \text {L}$ or if $\text {3Sat}\in \text {Time}(n\log ^{10}n)$ . In particular, Theorem 8.1 implies that any algorithm for 3Sat either must use super-logarithmic space or time $n^{1+c}$ .

Proof. We assume that what we want to prove is not true and derive the following striking contradiction with the hierarchy Theorem 3.4:

$\begin{aligned} \text {Time}(n^{2}) & \subseteq \text {L}\\ & \subseteq \bigcup _{d}\Sigma _{d}\text {Time}(n)\\ & \subseteq \text {Time}(n^{1.9}). \end{aligned}$

The first inclusion holds by the assumption that $\text {3Sat}\in \text {L}$ and the fact that any function in $\text {Time}(n^{2})$ can be reduced to 3Sat in log-space, by Theorem 5.1 and the discussion after that.

The second inclusion is Theorem 7.11.

For the third inclusion, the assumption that $\text {3Sat}\in \text {Time}(n^{1+\epsilon })$ for every $\epsilon$ implies that $\text {NTime}(dn)\subseteq \text {Time}(n^{1+\epsilon })$ for every $d$ and $\epsilon$ , by the quasi-linear-time completeness of 3Sat, Theorem 5.4. Now apply Exercise 6.2. QED

8.2 Impossibility II

We now state and prove a closely related result for TiSp. We seek to rule out algorithms for 3Sat that simultaneously use little space and time, whereas in Theorem 8.1 we even ruled out the possibility that there are two distinct algorithms, one optimizing space and the other time. The main gain is that we will be able to handle much larger space: power rather than log.

Theorem 8.2. $\text {3Sat}\not \in \text {TiSp}(n^{1+c_{\epsilon }},n^{1-\epsilon })$ , for any $\epsilon >0$ .

The important aspect of Theorem 8.1 is that it applies to the RAM model; stronger results can be shown for space-bounded TMs.

Exercise 8.1. Prove that $\text {Palindromes}\not \in \text {TM-TiSp}(n^{1+c_{\epsilon }},n^{1-\epsilon })$ , for any $\epsilon >0$ . (TM-TiSp $(t,s)$ is defined as Space $(s)$ , cf. Definition 7.1, but moreover the machine runs in at most $t$ steps.) Hint: This problem has a simple solution. Give a suitable simulation of TM-Tisp by 1TM, then apply Theorem 3.1.

Proof. We assume that what we want to prove is not true and derive the following contradiction with the hierarchy Theorem 3.4:

$\begin{aligned} \text {Time}(n^{1+\epsilon }) & \subseteq \text {\text {TiSp}(c\ensuremath {n^{(1+\epsilon )(1+c_{\epsilon })}},c\ensuremath {n^{(1+\epsilon )(1-\epsilon )}})}\\ & \subseteq \text {\text {TiSp}(\ensuremath {n^{1+c_{\epsilon }}},c\ensuremath {n^{1-\epsilon ^{2}}})}\\ & \subseteq \Sigma _{c_{\epsilon }}\text {Time}(n)\\ & \subseteq \text {Time}(n^{1+\epsilon /2}). \end{aligned}$

The first inclusion holds by the assumption, padding, and the fact that 3Sat is complete under reductions s.t. each bit is computable in time (and hence space) $n^{o(1)}$ , a fact we do not prove here. QED

Exercise 8.2. Finish the proof by justifying the remaining inclusions.

8.3 Impossibility III

So far our impossibility results required bounds on space. We now state and prove a result that applies to time. Of course, as discussed in Chapter 3, we don’t know how to prove that, say, 3Sat cannot be computed in linear time on a 2TM. For single-tape machines, we can prove quadratic bounds, for palindromes (Theorem 3.1) and 3Sat (Problem 4.2). Next we consider an interesting model which is between 1TM and 2TM and is a good indication of the state of our knowledge.

Definition 8.1. A $1.5\text {TM}$ is like a 2TM except that the input tape is read-only.

Theorem 8.3. [43, 70] 3Sat requires time $n^{1+c}$ on a 1.5TM.

Exercise 8.3. Prove Theorem 8.3 following this guideline:

Let $M$ be a 1.5 TM running in tine $t(n)$ . Divide the read-write tape of $M$ into consecutive blocks of $b$ cells, shifted by an offset $i \leq b$ . Prove that for every input there is an offset s.t. the sum of the lengths of all the crossing sequences between adjacent blocks is small.
Prove that $1.5\text {TM-Time}(n^{1.1})\subseteq \exists y\in \{0,1\} ^{n^{1-c}}\text {TiSp}(n^{c},n^{1-c})$ . (The right-hand side is the class of functions $f:\{0,1\}^* \to \{0,1\}$ for which there is a RAM $M$ that on input $(x,y)$ , where $|x|=n$ , runs in time $n^{c}$ and uses memory cells $0..n^{1-c}$ and s.t. $f(x)=1\Leftrightarrow \exists y\in \{0,1\} ^{n^{1-c}}M(x,y)=1$ .)
Conclude the proof.

Notes

For a survey (not up to date) of this type of impossibility results see [69].

[1] Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. Tight hardness results for LCS and other sequence similarity measures. In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 59–78. IEEE Computer Society, 2015.

[2] Leonard Adleman. Two theorems on random polynomial time. In 19th IEEE Symp. on Foundations of Computer Science (FOCS), pages 75–83. 1978.

[3] Mikl≤s Ajtai. $\Sigma \sp {1}\sb {1}$ -formulae on finite structures. Annals of Pure and Applied Logic, 24(1):1–48, 1983.

[4] Mikl≤s Ajtai. A non-linear time lower bound for boolean branching programs. Theory of Computing, 1(1):149–176, 2005.

[5] Eric Allender. A note on the power of threshold circuits. In 30th Symposium on Foundations of Computer Science, pages 580–584, Research Triangle Park, North Carolina, 30 October–1 November 1989. IEEE.

[6] Eric Allender. The division breakthroughs. Bulletin of the EATCS, 74:61–77, 2001.

[7] Eric Allender and Michal Koucký. Amplifying lower bounds by means of self-reducibility. J. of the ACM, 57(3), 2010.

[8] Noga Alon, Oded Goldreich, Johan Hσstad, and RenΘ Peralta. Simple constructions of almost $k$ -wise independent random variables. Random Structures & Algorithms, 3(3):289–304, 1992.

[9] Dana Angluin and Leslie G. Valiant. Fast probabilistic algorithms for hamiltonian circuits and matchings. J. Comput. Syst. Sci., 18(2):155–193, 1979.

[10] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. J. of the ACM, 45(3):501–555, May 1998.

[11] Arturs Backurs and Piotr Indyk. Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). SIAM J. Comput., 47(3):1087–1097, 2018.

[12] Kenneth E. Batcher. Sorting networks and their applications. In AFIPS Spring Joint Computing Conference, volume 32, pages 307–314, 1968.

[13] Paul Beame, Stephen A. Cook, and H. James Hoover. Log depth circuits for division and related problems. SIAM J. Comput., 15(4):994–1003, 1986.

[14] Paul Beame, Michael Saks, Xiaodong Sun, and Erik Vee. Time-space trade-off lower bounds for randomized computation of decision problems. J. of the ACM, 50(2):154–195, 2003.

[15] Michael Ben-Or and Richard Cleve. Computing algebraic formulas using a constant number of registers. SIAM J. on Computing, 21(1):54–58, 1992.

[16] Samuel R. Buss and Ryan Williams. Limits on alternation trading proofs for time-space lower bounds. Comput. Complex., 24(3):533–600, 2015.

[17] Lijie Chen and Roei Tell. Bootstrapping results for threshold circuits “just beyond” known lower bounds. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 34–41. ACM, 2019.

[18] Richard Cleve. Towards optimal simulations of formulas by bounded-width programs. Computational Complexity, 1:91–105, 1991.

[19] Stephen A. Cook. A hierarchy for nondeterministic time complexity. J. of Computer and System Sciences, 7(4):343–353, 1973.

[20] L. Csanky. Fast parallel matrix inversion algorithms. SIAM J. Comput., 5(4):618–623, 1976.

[21] Lance Fortnow. Time-space tradeoffs for satisfiability. J. Comput. Syst. Sci., 60(2):337–353, 2000.

[22] Aviezri S. Fraenkel and David Lichtenstein. Computing a perfect strategy for n x n chess requires time exponential in n. J. Comb. Theory, Ser. A, 31(2):199–214, 1981.

[23] Michael L. Fredman and Michael E. Saks. The cell probe complexity of dynamic data structures. In ACM Symp. on the Theory of Computing (STOC), pages 345–354, 1989.

[24] Anka Gajentaan and Mark H. Overmars. On a class of ${O}(n^2)$ problems in computational geometry. Comput. Geom., 5:165–185, 1995.

[25] M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.

[26] K. G÷del. ▄ber formal unentscheidbare sΣtze der Principia Mathematica und verwandter systeme I. Monatsh. Math. Phys., 38, 1931.

[27] Oded Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press, 2008.

[28] Raymond Greenlaw, H. James Hoover, and Walter Ruzzo. Limits to Parallel Computation: P-Completeness Theory. 02 2001.

[29] David Harvey and Joris van der Hoeven. Integer multiplication in time $O(n\mathrm {log}\, n)$ . Annals of Mathematics, 193(2):563 – 617, 2021.

[30] F. C. Hennie. One-tape, off-line turing machine computations. Information and Control, 8(6):553–578, 1965.

[31] Fred Hennie and Richard Stearns. Two-tape simulation of multitape turing machines. J. of the ACM, 13:533–546, October 1966.

[32] John E. Hopcroft, Wolfgang J. Paul, and Leslie G. Valiant. On time versus space. J. ACM, 24(2):332–337, 1977.

[33] Russell Impagliazzo and Ramamohan Paturi. The complexity of $k$ -sat. In IEEE Conf. on Computational Complexity (CCC), pages 237–, 1999.

[34] Russell Impagliazzo, Ramamohan Paturi, and Michael E. Saks. Size-depth tradeoffs for threshold circuits. SIAM J. Comput., 26(3):693–707, 1997.

[35] Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Computer & Systems Sciences, 63(4):512–530, Dec 2001.

[36] Russell Impagliazzo and Avi Wigderson. $\mathit {P} = \mathit {BPP}$ if $E$ requires exponential circuits: Derandomizing the XOR lemma. In 29th ACM Symp. on the Theory of Computing (STOC), pages 220–229. ACM, 1997.

[37] Richard M. Karp and Richard J. Lipton. Turing machines that take advice. L’Enseignement MathΘmatique. Revue Internationale. IIe SΘrie, 28(3-4):191–209, 1982.

[38] Kojiro Kobayashi. On the structure of one-tape nondeterministic turing machine time hierarchy. Theor. Comput. Sci., 40:175–193, 1985.

[39] Kasper Green Larsen, Omri Weinstein, and Huacheng Yu. Crossing the logarithmic barrier for dynamic boolean data structure lower bounds. SIAM J. Comput., 49(5), 2020.

[40] Leonid A. Levin. Universal sequential search problems. Problemy Peredachi Informatsii, 9(3):115–116, 1973.

[41] Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan. Algebraic methods for interactive proof systems. J. of the ACM, 39(4):859–868, October 1992.

[42] O. B. Lupanov. A method of circuit synthesis. Izv. VUZ Radiofiz., 1:120–140, 1958.

[43] Wolfgang Maass and Amir Schorr. Speed-up of Turing machines with one work tape and a two-way input tape. SIAM J. on Computing, 16(1):195–202, 1987.

[44] David A. Mix Barrington. Bounded-width polynomial-size branching programs recognize exactly those languages in NC $^1$ . J. of Computer and System Sciences, 38(1):150–164, 1989.

[45] Joseph Naor and Moni Naor. Small-bias probability spaces: efficient constructions and applications. SIAM J. on Computing, 22(4):838–856, 1993.

[46] E. I. Nechiporuk. A boolean function. Soviet Mathematics-Doklady, 169(4):765–766, 1966.

[47] Valery A. Nepomnjaščiĭ. Rudimentary predicates and Turing calculations. Soviet Mathematics-Doklady, 11(6):1462–1465, 1970.

[48] NEU. From RAM to SAT. Available at http://www.ccs.neu.edu/home/viola/, 2012.

[49] Christos H. Papadimitriou and Mihalis Yannakakis. Optimization, approximation, and complexity classes. J. Comput. Syst. Sci., 43(3):425–440, 1991.

[50] Wolfgang J. Paul, Nicholas Pippenger, Endre SzemerΘdi, and William T. Trotter. On determinism versus non-determinism and related problems (preliminary version). In IEEE Symp. on Foundations of Computer Science (FOCS), pages 429–438, 1983.

[51] Nicholas Pippenger and Michael J. Fischer. Relations among complexity measures. J. of the ACM, 26(2):361–381, 1979.

[52] Alexander Razborov. Lower bounds on the dimension of schemes of bounded depth in a complete basis containing the logical addition function. Akademiya Nauk SSSR. Matematicheskie Zametki, 41(4):598–607, 1987. English translation in Mathematical Notes of the Academy of Sci. of the USSR, 41(4):333-338, 1987.

[53] Omer Reingold. Undirected connectivity in log-space. J. of the ACM, 55(4), 2008.

[54] J. M. Robson. N by N checkers is exptime complete. SIAM J. Comput., 13(2):252–267, 1984.

[55] Rahul Santhanam. On separators, segregators and time versus space. In IEEE Conf. on Computational Complexity (CCC), pages 286–294, 2001.

[56] Walter J. Savitch. Relationships between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences, 4(2):177–192, 1970.

[57] Arnold Sch÷nhage. Storage modification machines. SIAM J. Comput., 9(3):490–508, 1980.

[58] Adi Shamir. IP = PSPACE. J. of the ACM, 39(4):869–877, October 1992.

[59] Claude E. Shannon. The synthesis of two-terminal switching circuits. Bell System Tech. J., 28:59–98, 1949.

[60] Victor Shoup. New algorithms for finding irreducible polynomials over finite fields. Mathematics of Computation, 54(189):435–447, 1990.

[61] Alan Siegel. On universal classes of extremely random constant-time hash functions. SIAM J. on Computing, 33(3):505–543, 2004.

[62] Michael Sipser. A complexity theoretic approach to randomness. In ACM Symp. on the Theory of Computing (STOC), pages 330–335, 1983.

[63] Roman Smolensky. Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In 19th ACM Symp. on the Theory of Computing (STOC), pages 77–82. ACM, 1987.

[64] Larry Stockmeyer and Albert R. Meyer. Cosmological lower bound on the circuit complexity of a small problem in logic. J. ACM, 49(6):753–784, 2002.

[65] Seinosuke Toda. PP is as hard as the polynomial-time hierarchy. SIAM J. on Computing, 20(5):865–877, 1991.

[66] Alan M. Turing. On computable numbers, with an application to the entscheidungsproblem. Proc. London Math. Soc., s2-42(1):230–265, 1937.

[67] Leslie G. Valiant. Graph-theoretic arguments in low-level complexity. In 6th Symposium on Mathematical Foundations of Computer Science, volume 53 of Lecture Notes in Computer Science, pages 162–176. Springer, 1977.

[68] Leslie G. Valiant and Vijay V. Vazirani. NP is as easy as detecting unique solutions. Theor. Comput. Sci., 47(3):85–93, 1986.

[69] Dieter van Melkebeek. A survey of lower bounds for satisfiability and related problems. Foundations and Trends in Theoretical Computer Science, 2(3):197–303, 2006.

[70] Dieter van Melkebeek and Ran Raz. A time lower bound for satisfiability. Theor. Comput. Sci., 348(2-3):311–320, 2005.

[71] N. V. Vinodchandran. A note on the circuit complexity of PP. Theor. Comput. Sci., 347(1-2):415–418, 2005.

[72] Emanuele Viola. On approximate majority and probabilistic time. Computational Complexity, 18(3):337–375, 2009.

[73] Emanuele Viola. On the power of small-depth computation. Foundations and Trends in Theoretical Computer Science, 5(1):1–72, 2009.

[74] Emanuele Viola. Reducing 3XOR to listing triangles, an exposition. Available at http://www.ccs.neu.edu/home/viola/, 2011.

[75] Emanuele Viola. Lower bounds for data structures with space close to maximum imply circuit lower bounds. Theory of Computing, 15:1–9, 2019. Available at http://www.ccs.neu.edu/home/viola/.

[76] Emanuele Viola. Pseudorandom bits and lower bounds for randomized turing machines. Theory of Computing, 18(10):1–12, 2022.