On the computational complexity of the languages of general symbolic dynamical systems and beta-shifts

AbstractWe consider the computational complexity of languages of symbolic dynamical systems. In particular, we study complexity hierarchies and membership of the non-uniform class P/poly. We prove: 1.For every time-constructible, non-decreasing function t(n)=ω(n), there is a symbolic dynamical system with language decidable in deterministic time O(n2t(n)), but not in deterministic time o(t(n)).2.For every space-constructible, non-decreasing function s(n)=ω(n), there is a symbolic dynamical system with language decidable in deterministic space O(s(n)), but not in deterministic space o(s(n)).3.There are symbolic dynamical systems having hard and complete languages under ≤mlogs- and ≤mp-reduction for every complexity class above LOGSPACE in the backbone hierarchy (hence, P-complete, NP-complete, coNP-complete, PSPACE-complete, and EXPTIME-complete sets).4.There are decidable languages of symbolic dynamical systems in P/poly for every alphabet of size |Σ|≥1.5.There are decidable languages of symbolic dynamical systems not in P/poly iff the alphabet size is >1.For the particular class of symbolic dynamical systems known as β-shifts, we prove that: 1.For all real numbers β>1, the language of the β-shift is in P/poly.2.If there exists a real number β>1 such that the language of the β-shift is NP-hard under ≤Tp-reduction, then the polynomial hierarchy collapses to the second level. As NP-hardness under ≤mp-reduction implies hardness under ≤Tp-reduction, this result implies that it is unlikely that a proof of existence of an NP-hard language of a β-shift will be forthcoming.3.For every time-constructible, non-decreasing function t(n)≥n, there is a real number 1<β<2 such that the language of the β-shift is decidable in time O(n2t(logn+1)), but not in any proper time bound g(n) satisfying g(4n)=o(t(n)/16n).4.For every space-constructible, non-decreasing function s(n)=ω(n2), there is a real number 1<β<2 such that the language of the β-shift is decidable in space O(s(n)), but not in space g(n) where g is any function satisfying g(n2)=o(s(n)).5.There exists a real number 1<β