We construct a first-order formula φ such that all finite models of φ are non-narrow rectangular grids without using any binary relations other than the grid neighborship relations. As a corollary, we prove that a set A ⊆ ℕ is a spectrum of a formula which has only planar models if numbers n ∈ A can be recognized by a non-deterministic Turing machine (or a one-dimensional cellular automaton) in time t (n) and space s (n), where t (n)s (n) ≤ n and t (n), s (n) = Ω(log(n)).
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
In Descriptive Complexity, there is a vast amount of literature on decision problems, and their classes such as P, NP, L and NL. However, research on the descriptive complexity of optimisation problems has been limited. In a previous paper [13], we characterised the optimisation versions of P via expressions in second order logic, using universal Horn formulae with successor relations. In this paper, we study the syntactic hierarchy within the class of polynomially bound maximisation problems. We extend the result in the previous paper by showing that the class of polynomially-bound NP (not just P) maximisation problems can be expressed in second-order logic using Horn formulae with successor relations. Finally, we provide an application - we show that the Bin Packing problem with online LIB constraints can be approximated to within a Q(logn) bound, by providing a syntactic characterisation for this problem.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.