On the Computational Complexity of the Languages of General Symbolic Dynamical Systems and Beta-Shifts

TY - JOUR

T1 - On the Computational Complexity of the Languages of General Symbolic Dynamical Systems and Beta-Shifts

AU - Simonsen, Jakob Grue

PY - 2009

Y1 - 2009

N2 - We 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)=@w(n), there is a symbolic dynamical system with language decidable in deterministic time O(n^2t(n)), but not in deterministic time o(t(n)). 2.For every space-constructible, non-decreasing function s(n)=@w(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 @?"m^l^o^g^s- and @?"m^p-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 |@S|>=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 @b-shifts, we prove that: 1.For all real numbers @b>1, the language of the @b-shift is in P/poly. 2.If there exists a real number @b>1 such that the language of the @b-shift is NP-hard under @?"T^p-reduction, then the polynomial hierarchy collapses to the second level. As NP-hardness under @?"m^p-reduction implies hardness under @?"T^p-reduction, this result implies that it is unlikely that a proof of existence of an NP-hard language of a @b-shift will be forthcoming. 3.For every time-constructible, non-decreasing function t(n)>=n, there is a real number 1<@b<2 such that the language of the @b-shift is decidable in time O(n^2t(logn+1)), but not in any proper time bound g(n) satisfying g(4^n)=o(t(n)/16^n). 4.For every space-constructible, non-decreasing function s(n)=@w(n^2), there is a real number 1<@b<2 such that the language of the @b-shift is decidable in space O(s(n)), but not in space g(n) where g is any function satisfying g(n^2)=o(s(n)). 5.There exists a real number 1<@b<2 such that the language of the @b-shift is recursive, but not context-sensitive.

AB - We 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)=@w(n), there is a symbolic dynamical system with language decidable in deterministic time O(n^2t(n)), but not in deterministic time o(t(n)). 2.For every space-constructible, non-decreasing function s(n)=@w(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 @?"m^l^o^g^s- and @?"m^p-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 |@S|>=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 @b-shifts, we prove that: 1.For all real numbers @b>1, the language of the @b-shift is in P/poly. 2.If there exists a real number @b>1 such that the language of the @b-shift is NP-hard under @?"T^p-reduction, then the polynomial hierarchy collapses to the second level. As NP-hardness under @?"m^p-reduction implies hardness under @?"T^p-reduction, this result implies that it is unlikely that a proof of existence of an NP-hard language of a @b-shift will be forthcoming. 3.For every time-constructible, non-decreasing function t(n)>=n, there is a real number 1<@b<2 such that the language of the @b-shift is decidable in time O(n^2t(logn+1)), but not in any proper time bound g(n) satisfying g(4^n)=o(t(n)/16^n). 4.For every space-constructible, non-decreasing function s(n)=@w(n^2), there is a real number 1<@b<2 such that the language of the @b-shift is decidable in space O(s(n)), but not in space g(n) where g is any function satisfying g(n^2)=o(s(n)). 5.There exists a real number 1<@b<2 such that the language of the @b-shift is recursive, but not context-sensitive.

U2 - 10.1016/j.tcs.2009.06.037

DO - 10.1016/j.tcs.2009.06.037

M3 - Journal article

SN - 0304-3975

VL - 410

SP - 4878

EP - 4891

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 47-49

ER -