Complexity, Legacy, and Continuation

In this paper we study the classic problem of determining whether the deterministic and non-deterministic context-sensitive languages are the same or, equivalently, whether the languages accepted by deterministic and non-deterministic linearly bounded automata are the same. We show that this problem is equivalent to several other natural problems in the theory of computing and that the techniques used on the LBA problem have several other applications in complexity theory. For example, we show that there exists a hardest-tape recognizable non-deterministic context-sensitive language L1, such that L1 is a deterministic context-sensitive language if and only if the deterministic and non-deterministic context-sensitive languages are the same. We show furthermore, that many decision problems about sets described by regular expressions are instances of these tape-hardest recognizable context-sensitive languages. Thus, it follows that non-determinism in Turing machine computations (using at least linear tape) can not save memory over deterministic Turing machine computations if and only if the equivalence of regular expressions can be decided by a deterministic linearly bounded automaton. It also follows that the equivalence of regular expressions can be decided by a non-deterministic linearly bounded automaton if and only if the family of context-sensitive languages is closed under complementation.

The computational complexity of a sequence is to be measured by how fast a multitape Turing machine can print out the terms of the sequence. This particular abstract model of a computing device is chosen because much of the work in this area is stimulated by the rapidly growing importance of computation through the use of digital computers, and all digital computers in a slightly idealized form belong to the class of multitape Turing machines. More specifically, if T(n) is a computable, monotone increasing function of positive integers into positive integers and if a is a (binary) sequence, then we say that a is in complexity class ST or that a is T-computable if and only if there is a multitape Turing machine M such that M computes the nth term of a within T(n) operations. Each set ST is recursively enumerable and so no class ST contains all computable sequences. On the other hand, every computable a is contained in some complexity class ST. Thus a hierarchy of complexity classes is assured. Furthermore, the classes are independent of time scale or of the speed of the components from which the machines could be built, as there is a speed-up theorem which states that ST = SkT for positive numbers k.

This paper investigates the computational complexity of binary sequences as measured by the rapidity of their generation by multitape Turing machines. A translational method which escapes some of the limitations of earlier approaches leads to a refinement of the established hierarchy. The previous complexity classes are shown to possess certain translational properties. An related hierarchy of complexity classes of monotonic functions is examined.

We show that the STEINER TREE problem and TRAVELING SALESMAN problem for points in the plane are NP-complete when distances are measured either by the rectilinear (Manhattan) metric or by a natural discretized version of the Euclidean metric. Our proofs also indicate that the problems are NP-hard if the distance measure is the (unmodified) Euclidean metric. However, for reasons we discuss, there is some question as to whether these problems, or even the well-solved MINIMUM SPANNING TREE problem, are in NP when the distance measure is the Euclidean metric.

The uniform word problem for commutative semigroups (UWCS) is the problem of determining from any given finite set of defining relations and any pair of words, whether the words describe the same element in the commutative semigroup defined by the relations. The effective decidability of this classical algebraic problem was first explicitly noted by Malcev [1958] and Emilichev [1958], though in retrospect this result can be seen to be contained in the earlier work of König [1903] and Hermann [1926] on polynomial ideals.

We investigate a divide-and-conquer technique in multidimensional space which decomposes a geometric problem on N points in k dimensions into two problems on N/2 points in k dimensions plus a single problem on N points in k−1 dimension. Special structure of the subproblems is exploited to obtain an algorithm for finding the two closest of N points in 0(N log N) time in any dimension. Related results are discussed, along with some conjectures and unsolved geometric problems.

In Freydenberger (Theory Comput Syst 53(2):159–193, 2013. https://doi.org/10.1007/s00224-012-9389-0), Freydenberger shows that the set of invalid computations of an extended Turing machine can be recognized by a synchronized regular expression [as defined in Della Penna et al. (Acta Informatica 39(1):31–70, 2003. https://doi.org/10.1007/s00236-002-0099-y)]. Therefore, the widely discussed predicate “={0, 1}*” is not recursively enumerable for synchronized regular expressions (SRE). In this paper, we employ a stronger form of non-recursive enumerability called productiveness and show that the set of invalid computations of a deterministic Turing machine on a single input can be recognized by a synchronized regular expression. Hence, for a polynomial-time decidable subset of SRE, where each expression generates either {0, 1}* or {0, 1}* - {w}, the predicate “={0, 1}*” is productive. This result can be easily applied to other classes of language descriptors due to the simplicity of the construction in its proof. This result also implies that many computational problems, especially promise problems, for SRE are productive. These problems include language class comparison problems (e.g., does a given synchronized regular expression generate a context-free language?), and equivalence and containment problems of several types (e.g., does a given synchronized regular expression generate a language equal to a fixed unbounded regular set?). In addition, we study the descriptional complexity of SRE. A generalized method for studying trade-offs between SRE and many classes of language descriptors is established.

We study the complexity of a restricted version of the universality problem: testing equivalence to {0, 1}⁎ for languages that are either {0, 1}⁎ or {0, 1}⁎ - {w}. We show that this restricted problem for multi-pattern languages (MPL) is NP-hard, and for multi-pattern languages with regular substitutions (MPLREG) is not recursively enumerable. Moreover, this undecidability result holds for any class of languages that effectively contains {w#w | w in {0, 1}*}, and is effectively closed under union, and concatenation with regular sets. Consequently, it has broad applicability and extends to many generalizations of regular languages. Sufficient conditions are then presented for a language predicate to be as hard as the restricted universality problem. By applying these conditions, we develop a uniform method for showing undecidability and complexity results simultaneously via highly efficient many-one reductions. In addition, the properties of this restricted universality problem can be used to investigate the descriptional complexity of multi-patterns. We show that the trade-off between multi-patterns and regular expressions is not exponential-size bounded. Non-recursive trade-offs between multi-patterns (or multi-patterns with regular substitutions) and numerous classes of language descriptors are also established.

Computable analysis extends classical computability theory to continuous domains, investigating the computability and complexity of problems in mathematical analysis. In this paper, we develop a framework for analyzing the complexity of mathematical problems across various fields by constructing highly efficient many-one reductions. For example, we show that the equivalence-to-identically-zero-function problem is reducible to determining whether the Jacobian determinant of a set of functions is identically zero, whether a Fredholm integral equation of the first kind has no eigenvalue, whether a Fredholm integral equation of the second kind has a trivial solution, whether the gradient of a function is identically zero, whether all finite orbits are closed in a given potential, and whether the Poisson bracket of two functions vanishes. Building on prior undecidability and productiveness (a stronger form of non-recursive enumerability) results for the equivalence-to-identically-zero-function problem, we establish that these problems are productive for specific classes of elementary functions. Furthermore, we explore potential approaches for applying classical complexity classes, such as NP, PSPACE, and EXPTIME, to computable analysis by leveraging the efficiency of our reductions. Our results provide a unified proof technique for analyzing complexity across different scientific domains, offering a practical extension of computational complexity theory to continuous mathematical structures.