Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories (Q793017): Difference between revisions

A language L belongs to the complexity class \(LATIME(t(n))\) if it is accepted by some alternating Turing machine M which on inputs of length n makes at most t(n) steps and involves at most n alternations. For \(\Sigma\) a finite alphabet \(BCT(\Sigma^*| t(n))\) is the theory of the structure \((\Sigma^*,Con(t(n)))_{n\in N}\) where Con(t(n)) denotes the concatenation relation on \(\{w\in \Sigma^*| \quad | w| \leq t(n)\}.\) The author states without proof that \(BCT(\{0,1\}^*| t(n))\) (and some variants) are complete in \(LATIME(t(0(n)))\) with respect to polynomial time reductions whenever t satisfies \(t(m_ 1+m_ 2)\geq t(m_ 1)\cdot t(m_ 2)\) for \(m_ 1,m_ 2>0\) and t(1)\(\geq 2\).