Abstract

In this article, we construct \(\P\)-incomplete sets under log-space many-one reduction. For a positive integer \(k\), \(\DSPACE(\log^{k+1}(n))\)-complete sets are not log-space reducible to sets contained in \(\DSPACE(\log^k(n))\) by the space hierarchy theorem.

It is generally undecidable whether a set is in \(\P\). Hence, according to the space hierarchy theorem, there exists a set in \(\DTISP(\poly,\log^{k+1}(n))\), which is not log-space reducible to sets contained in \(\DTISP(\poly,\log^{k}(n))\).

Thus, no set in \(\SC\) is \(\P\)-complete, which implies that \(\P\) is not equal to \(\cL\), and to \(\NC\). Therefore, complete sets in \(\P\) are inherently sequential.

1 Introduction↩︎

The set \[\mathcal{A}=\{(M,x,1^t) \mid \text{ TM }M \text{ accepts } x \text{ within } t \text{ steps} \}\] is \(\P\)-complete under log-space many-one reduction [1], i.e. \(\mathcal{A}\in\P\), and for every set \(X\) in \(\P\), \(X\le_m^{\log}\mathcal{A}\).

It is generally undecidable whether a TM accepts an input. However, when a TM accepts an input, it does this so finitely many steps. Therefore, \[\label{eq:acceptfinite} x \in L(M) \iff \exists t\in\nat\;(M,x,1^t) \in \mathcal{A}\tag{1}\] for all \(M\) and \(x\). Hence, we can apply computability theory to analyze the \(\P\)-complete set \(\mathcal{A}\).

In this paper, we construct \(\P\)-incomplete sets. The sets \[\label{eq:usp} \begin{align} U_{k} := \{(M,x,1^s) \mid &\text{ The TM } M \text{ accepts }x \text{ within }\log^k(s) \text{ tape space,}\\ &\text{ and the runtime of }M\text{ is polynomially bounded}\\&\text{ in }|x|+s. \} \end{align}\tag{2}\] are in \(\P\), since for each positive integer \(k\), \(U_{k}\in\DTISP(\poly,\log^k(n))\).

Unfortunately, these sets are hard to analyze directly, as shown in Section 2. For this reason, we observe the sets: \[\label{eq:bsp} B_{k} := \{(M,x,1^s) \mid \text{ TM } M \text{ accepts } x \text{ within } \log^k(s) \text{ tape space} \}.\tag{3}\]

For each positive integer \(k\), the set \(B_{k}\) is \(\DSPACE(\log^k(n))\)-complete under log-space many-one reduction.

Lemma 1. \(U_{k} \le_m^{\log} B_{k}\) and \(U_{k} \le_m^{\log} \mathcal{A}\)

Proof. If \((M,x,1^s) \in U_{k}\) then \((M,x,1^s) \in B_{k}\). Therefore, \(U_{k} \le_m^{\log} B_{k}\).

For all \(k\in\nat\), \(U_{k}\in\P\) and \(\mathcal{A}\) is \(\P\)-complete. Thus, \(U_{k} \le_m^{\log} \mathcal{A}\). ◻

In Section 3, we prove that \(B_{k+1}\not\le_m^{\log} B_{k}\) for \(k\in\nat\) in Theorem 1. Theorem 1 and Lemma 2 imply that \(U_{k+1}\not\le_m^{\log} U_{k}\) for \(k>0\). Therefore, all \(U_{k}\) are \(\P\)-incomplete.

To prove irreducibility, we need methods from computability theory. To emphasize this, we put Lemma 2 in its own section, Section 2. We prove with the halting problem in Lemma 2 that it is undecidable whether a set is in \(\P\), and therefore, whether a set in \(\DSPACE(\log^k(n))\) is in \(\DTISP(\poly,\log^k(n))\) for \(k>1\).

In Section 4, we show other \(\P\)-incomplete problems, and that there is no parallel algorithm with efficient speedup for any \(\P\)-complete problem.

Baker, Gill, and Solovay have proved the relativization barrier for P versus NP [2]. Any proof separating L from P also must not relativize. In Section 5, we explain why the proof in our paper circumvents the relativization barrier.

2 On Computability↩︎

As mentioned in Eq. (1 ), we use computability to analyse the complexity class \(\P\).

Lemma 2. Let \(k>1\). For a TM with space requirement of \(\Theta(\log^k)\), no algorithm can decide in general whether the runtime of the TM is polynomial.

Proof. We reduce the halting problem [3] to the question of whether the runtime is polynomial.

Given a TM \(M\), which contains a read-only input tape and a limited work tape with read-write head, and an input \(x\). The TMs \(M,\) and \(M'\) terminate

they reach

an accepting state, or rejecting state. For convenience, we assume that each of the TMs only reaches the rejecting state if it requires more space than reserved on the work tape during the runtime.

We construct a multi-tape TM as described in Algorithm 1.

Figure 1: FUNCTION \text{testLM\_maybe\_poly}(k,M,M',x) — Figure 1: FUNCTION \(\text{testLM\_maybe\_poly}(k,M,M',x)\)

This multi-tape TM runs simultaneously \(M\) on input \(x\) and \(M'\) on input \(\langle M'\rangle\) using different work tapes. The space of each work tape is limited to \(\log^k(|x|)\). Additionally, there is a counter tape initialized with a string of \(\log^k(|x|)\) ‘0’-symbols.

While the counter contains a ‘0’-symbol, we do the following steps:

We increment the counter in binary. Then we execute one step of \(M\) on input \(x\) and one step of \(M'\) on the encoding of itself as input. As soon as the computation of \(M'\) on input \(\langle M'\rangle\) reaches an accepting state, we resize the counter to \(\log(|x|)\) cells filled with ‘0’-symbols.

If the TM \(M'\) accepts the encoding of itself, then Algorithm 1 executes \(O(2^{\log(|x|)})=O(|x|)\) iterations. Otherwise, the number of iterations is \(2^{\log^k(|x|)}= |x|^{\log^{k-1}(|x|)}\). The multi-tape TM has a polynomial runtime if and only if the TM \(M'\) accepts the encoding of itself, i.e.\(\langle M'\rangle \in L(M')\). Therefore, this property is undecidable in general. ◻

The following corollary follows directly from Lemma 2:

Corollary 1. For \(k>1\), it is undecidable for a triple in \(B_k\) whether this triple is contained in \(U_k\).

3 Space Hierarchy within ¶↩︎

Recall the sets \(B_{k}\) in Eq. (3 ), and \(U_{k}\) in Eq. (2 ).

Theorem 1. For each positive integer \(k\), the set \(B_{k}\) is \(\DSPACE(\log^k(n))\)-complete under log-space many-one reduction.

Proof. Obviously, \(B_{k}\in\DSPACE(\log^k(n))\).

If \(X \in\DSPACE(\log^k(n))\), then \(X\) is the language of a TM that requires \(O(\log^k(n))\) tape space. This means there is a constant \(C>0\), such that the tape space required by the TM for an input \(x\) is less than \(C\cdot\log^k(|x|)\). Using a log-space transducer, we can construct a triple consisting of the TM, the input \(x\), and a padding argument of length \(C\cdot\log^k(|x|)\). This triple is in \(B_{k}\) if and only if the TM accepts the input \(x\). ◻

Theorem 2. If \(k\) is a positive integer, then \(B_{k+1} \not\le_m^{\log} B_{k}\).

Proof. Due to the space hierarchy theorem [4], there exists a set \(X \in \DSPACE(\log^{k+1})\) such that \(X \not\in \DSPACE(\log^k)\). Thus, by Theorem 1, \(X \le_m^{\log} B_{k+1}\) and \(X \not\le_m^{\log} B_{k}\). This implies \(B_{k+1} \not\le_m^{\log} B_{k}\). ◻

Lemma 3. If \(k\) is a positive integer, then \(U_{k+1} \not\le_m^{\log} B_{k}\).

Proof. To construct a contradiction, we assume that \(U_{k+1} \le_m^{\log} B_{k}\). In this case, there would be a general log-space transducer mapping the triple \((M,x,1^s)\inU_{k+1}\) to an element in \(B_{k}\). By Theorem 2, there is no such transducer for a triple \((M,x,1^s)\inB_{k+1}\) to \(B_{k}\). The construction of this transducer could be used as an exploit to decide whether the triple in \(B_{k+1}\) is also in \(U_{k+1}\). However, by Corollary 1, whether this triple is contained in \(U_{k+1}\) is generally undecidable.

We assume that there is a log-space transducer \(T\) from \(U_{k+1}\) to \(B_{k}\). By Theorem 2, there is a TM \(M\) with space limit \(\log^{k+1}(n)\), such that the transducer \(T\) fails to map \(M\) to a TM with space limit \(O(\log^{k}(n))\). Without loss of generality there is an input \(x\in L(M)\), but \(x\not\in L(T(M))\).

We construct an algorithm, denoted Algorithm 2, with TM \(M\), which is irreducible via \(T\), and an arbitrary but fixed TM \(M'\).

Algorithm 2 tests for each input whether Algorithm 1 returns the same result with and without applying transducer \(T\), and halt, if both results are unequal.

If the TM \(M'\) does not accept itself as input, then Algorithm 1 returns true, if and only if \(M\) accepts \(x\) with space limit \(\log^{k+1}(|x|)\). Thus, there exists an input \(x\), where Algorithm 1 accepts \(x\), but not after applying the transducer \(T\).

If the TM \(M'\) accepts itself as input, then Algorithm 1 has polynomial run time. Hence, the transducer \(T\) works correctly. Applying \(T\) on Algorithm 1 does not change the result.

Figure 2: find input that Algorithm 1 classifies different after transducing

Thus, Algorithm 2 terminates if and only if \(M'\) does not terminate with itself as input. This would allow us to decide the halting problem, and so, the transducer \(T\) cannot exist. ◻

Theorem 3. If \(k\) is a positive integer, then \(U_{k+1} \not\le_m^{\log} U_{k}\).

Proof. We have \(U_{k+1} \not\le_m^{\log} B_{k}\), but \(U_{k} \le_m^{\log} B_{k}\). ◻

4 Conclusion↩︎

For all \(k\), \(U_{k}\in\P\) and \(\mathcal{A}\not\le_m^{\log} U_{k}\), so \(U_{k}\) is \(\P\)-incomplete. From the existence of incomplete sets, it follows:

Corollary 2. \(\cL \neq \P\)

Proof. If \(X\in\cL\), then \(X\le_m^{\log}U_{2}\). Therefore, \(\mathcal{A}\not\le_m^{\log}X\), since \(\mathcal{A}\not\le_m^{\log}U_{2}\). So, \(\mathcal{A}\in\P\), and \(\mathcal{A}\not\in\cL\). ◻

The class \(\SC\) is defined as \[\SC = \bigcup_{k\in\nat} \DTISP\bigl(\poly,\log^k(n)\bigr).\]

Corollary 3. \(\SC \neq \P\)

Proof. For every \(X\in\SC\), there exists \(Y\in\SC\) such that \(X\not\le_m^{\log}Y\). Thus, there is no \(\P\)-complete set in \(\SC\). ◻

Corollary 4. \(\NC \neq \P\)

Proof. By definition, \(\NC = \bigcup_{i\in\nat}\NC^i\), and \(\NC^i \subseteq \DSPACE(\log^i(n))\) [5], so there is no \(\P\)-complete set in \(\NC\). ◻

Corollary 4 implies that \(\P\)-complete problems are inherently sequential [6].

5 Notes on the Relativization Barrier↩︎

To separate \(\cL\) and \(\P\), the relativization barrier applies as it did for \(\P\) versus \(\NP\) [2].

Aaronson and Wigderson wrote [7]: “On the other hand, if we allow only polynomially-long queries, then results based on padding – for example, \(\P = \NP \Longrightarrow \EXP = \NEXP\) – will generally fail to relativize.”

The proof method in this paper uses padding, and the oracle queries are bounded by the input length including the padding argument. Thus, the method is suitable to circumvent the relativization barrier¹.

Acknowledgments↩︎

Many thanks to Lance Fortnow. His email correspondence helped me find bugs in the predecessor to this article [8]. The bugs were also mentioned by Ian Clingerman, and Quan Luu from the University of Rochester [9].

References↩︎

[1]

Steven Homer and Alan L. Selman. Computability and Complexity Theory, Second Edition. Texts in Computer Science. Springer, 2011.

[2]

Theodore Baker, John Gill, and Robert Solovay. Relativizations of the p=?np question. SIAM Journal on Computing, 4(4):431–442, 1975.

[3]

Alan Mathison Turing. On computable numbers, with an application to the Entscheidungsproblem. J. of Math, 58(5):345–363, 1936.

[4]

Richard Edwin Stearns, Juris Hartmanis, and Philip M. Lewis II. Hierarchies of memory limited computations. In 6th Annual Symposium on Switching Circuit Theory and Logical Design, Ann Arbor, Michigan, USA, October 6-8, 1965, pages 179–190. IEEE Computer Society, 1965.

[5]

Allan Borodin. On relating time and space to size and depth. SIAM J. Comput., 6:733–744, 1977.

[6]

Raymond Greenlaw, H James Hoover, and Walter L Ruzzo. Limits to parallel computation: P-completeness theory. Oxford university press, 1995.

[7]

Scott Aaronson and Avi Wigderson. Algebrization: a new barrier in complexity theory. ACM Trans. Comput. Theory, 1(1):54, 2009. Id/No 2.

[8]

Reiner Czerwinski. Separation of PSPACE and EXP, 2021.

[9]

Ian Clingerman and Quan Luu. A critique of czerwinski’s "separation of \({\rm pspace}\) and \({\rm exp}\)", 2023.

This phrase is self-plagiarism because it is used in many papers of the author since 2020↩︎

Incomplete Sets in \(\P\) under log-space Reduction