Computational complexity of hybrid interval temporal logics

Interval logics are very expressive temporal formalisms, but reasoning with them is often undecidable or has high computational complexity. As a result, a vast number of approaches limiting their expressive power—in order to obtain better computational behaviour—have been introduced. Unfortunately, due to such restrictions, interval logics often lose referentiality, that is, the capacity to refer to specific time intervals, which is crucial for temporal representation and reasoning. The computational price that needs to be paid in order to regain referentiality is not well studied and our research aims to fill this gap. In particular we study the main interval temporal logic, called the Halpern-Shoham logic, and its low complexity modifications. To regain referentiality in these modifications, we extend the language with the hybrid machinery—nominals and satisfaction operators—and classify the obtained logics according to their computational complexity. We show that such a hybridisation often makes tractable logics intractable but not undecidable. This allows us to construct hybrid interval temporal logics which are referential as well as maintain a good compromise between expressiveness and complexity; it makes them valuable formalisms for temporal knowledge representation. We also introduce a class of models which, due to a specific interplay between the interpretation of modal operators and a structure of time, makes reasoning in interval logics computationally hard even in the absence of the hybrid machinery.     

Computational complexity of isothermic DNA sequencing by hybridization

In the paper, the computational complexity of several variants of the problem of isothermic DNA sequencing by hybridization, is analyzed. The isothermic sequencing is a recent method, in which isothermic oligonucleotide libraries are used during the hybridization with an unknown DNA fragment. The variants of the isothermic DNA sequencing problem with errors in the hybridization data, negative ones or positive ones, are proved to be strongly NP-hard. On the other hand, the polynomial time algorithm for the ideal case with no errors is proposed.     

The stack loading and unloading problem

When piling a set of items in a single stack, one often does not pay attention to the order. Real-life experience suggests that, whenever a specific item is suddenly requested, we need to dig very deep into the stack to extract it.In this paper we investigate stack reordering strategies aiming at minimizing the number of pop and push operations. In particular we focus on three versions of the problem in which reordering can take place in different phases: when unloading the stack, when loading it or in both phases. We show that the first two variants can be solved in linear time, while for the third one we devise a dynamic programming method with quadratic complexity.     

Computational complexity of some scheduling problems with multiprocessor tasks

The paper is concerned with scheduling problems with multiprocessor tasks and presents conditions under which such problems can be solved in polynomial time. The application of these conditions is illustrated by two quite general scheduling problems. These results are complemented by a proof of NP-hardness of the problem with a UET task system, two parallel processors, the criterion of total completion time, and precedence constraints in the form of out-trees.     

Computational complexity of logical theories of one successor and another unary function

The first-order logical theory Th\(({\mathbb{N}},x + 1,F(x))\) is proved to be complete for the class ATIME-ALT\((2^{O(n)},O(n))\) when \(F(x) = 2^{x}\), and the same result holds for \(F(x) = c^{x}, x^{c} (c \in {\mathbb{N}}, c \ge 2)\), and F(x) =  tower of x powers of two. The difficult part is the upper bound, which is obtained by using a bounded Ehrenfeucht–Fraïssé game.     

Satisfiability of algebraic circuits over sets of natural numbers

We investigate the complexity of satisfiability problems for {∪,∩,⁻,+,×}-circuits computing sets of natural numbers. These problems are a natural generalization of membership problems for expressions and circuits studied by Stockmeyer and Meyer (1973) [10] and McKenzie and Wagner (2003) [8].Our work shows that satisfiability problems capture a wide range of complexity classes such as NL, P, NP, PSPACE, and beyond. We show that in several cases, satisfiability problems are harder than membership problems. In particular, we prove that testing satisfiability for {∩,+,×}-circuits is already undecidable. In contrast to this, the satisfiability for {∪,+,×}-circuits is decidable in PSPACE.     

A Model for Studying Display Methods of Statistical Graphics

Abstract

A method of statistical graphics consists of two parts: a selection of statistical information to be displayed and a selection of a visual display method to encode the information. Some display methods lead to efficient, accurate visual decoding of encoded information, and others lead to inefficient, inaccurate decoding. It is only through rigorous studies of visual decoding that informed judgments can be made about how to choose display methods. A model has been developed to provide a framework for the study of visual decoding. The model consists of three parts: (1) a two-way classification of information on displays—quantitative-scale, quantitative-physical, categorical-scale, and categorical-physical; (2) a division of the visual processing of graphical displays into pattern perception and table look-up; (3) a specification of visual operations that are employed to carry out pattern perception and table look-up. Display methods are assessed by studying the visual operations to which they lead. Studies use the theory and experimental technique of various areas of vision research including psychophysics, cognitive psychology, and computational vision. This process is illustrated by studies of three display methods: visual reference grids for graphs with juxtaposed panels and common scales, encoding a categorical variable on a scatterplot by the type of plotting symbol, and choosing the aspect ratio of a factor-response graph.     

Computational methods for Conway's Game of Life cellular automaton

The cellular automaton model of computation has drawn the interest of researchers from different disciplines including computer science, biology, mathematics, economy, biochemistry and philosophy. Although a cellular automaton is based on a set of simple rules, over time complex patterns may evolve. We present computational methods for implementing and optimizing a well known two-state cellular automaton, Conway's Game of Life, on a 16-core Intel Xeon. The evaluation is based on three multicore algorithms. The first algorithm is coherent and utilizes shared memory and barrier synchronization. The remaining two algorithms are distributed and utilize private memories and explicit core-to-core message passing. We provide a link to our open source simulation software.     

On extremal behaviors of Murty's least index method

In this small note, we observe some extremal behaviors of Murty's least index method for solving linear complementarity problems. In particular, we show that the expected number of steps for solving Murty's exponential example with a random permutation of variable indices is exactly equal ton, wheren is the size of the input square matrix.Corresponding author.     

The complexity of detecting fixed-density clusters

We study the complexity of finding a subgraph of a certain size and a certain density, where density is measured by the average degree. Let γ:N→Q₊ be any density function, i.e., γ is computable in polynomial time and satisfies γ(k)?k-1 for all k∈N. Then γ-CLUSTER is the problem of deciding, given an undirected graph G and a natural number k, whether there is a subgraph of G on k vertices that has average degree at least γ(k). For γ(k)=k-1, this problem is the same as the well-known CLIQUE problem, and thus NP-complete. In contrast to this, the problem is known to be solvable in polynomial time for γ(k)=2. We ask for the possible functions γ such that γ-CLUSTER remains NP-complete or becomes solvable in polynomial time. We show a rather sharp boundary: γ CLUSTER is NP-complete if γ=2+Ω(1/k^1-ε) for some ε>0 and has a polynomial-time algorithm for γ=2+O(1/k). The algorithm also shows that for γ=2+O(1/k^1-o(1)), γ-CLUSTER is solvable in subexponential time 2^no(1).     

Bottleneck combinatorial optimization problems with uncertain costs and the OWA criterion

In this paper a class of bottleneck combinatorial optimization problems with uncertain costs is discussed. The uncertainty is modeled by specifying a discrete scenario set containing a finite number of cost vectors, called scenarios. In order to choose a solution the Ordered Weighted Averaging aggregation operator (OWA for short) is applied. The OWA operator generalizes traditional criteria in decision making under uncertainty such as the maximum, minimum, average, median, or Hurwicz criterion. New complexity and approximation results in this area are provided. These results are general and remain valid for many problems, in particular for a wide class of network problems.     

一类P-函数非线性互补问题的宽邻域路径跟踪算法及其计算复杂性

对一致P-函数非线性互补问题,提出了一种新的宽邻域(N-∞(β))路径跟踪算法,并讨论了该算法的收敛性及计算复杂性.分析结果表明,所给方法是一多项式时间算法.     

Complexity of the job insertion problem in multi-stage scheduling

The job insertion problem in multi-stage scheduling is: given a schedule for n jobs and an additional job, find a feasible insertion of the additional job into the schedule that minimizes the resulting makespan. We prove that finding the optimal job insertion is NP-hard for flow shops and open shops.     

Computational complexity of reconstruction and isomorphism testing for designs and line graphs

Graphs with high symmetry or regularity are the main source for experimentally hard instances of the notoriously difficult graph isomorphism problem. In this paper, we study the computational complexity of isomorphism testing for line graphs of t-(v,k,λ) designs. For this class of highly regular graphs, we obtain a worst-case running time of O(vlogv+O(1)) for bounded parameters t, k, λ.In a first step, our approach makes use of the Babai-Luks algorithm to compute canonical forms of t-designs. In a second step, we show that t-designs can be reconstructed from their line graphs in polynomial-time. The first is algebraic in nature, the second purely combinatorial. For both, profound structural knowledge in design theory is required. Our results extend earlier complexity results about isomorphism testing of graphs generated from Steiner triple systems and block designs.     

The computational complexity of basic decision problems in 3-dimensional topology

We study the computational complexity of basic decision problems of 3-dimensional topology, such as to determine whether a triangulated 3-manifold is irreducible, prime, ∂-irreducible, or homeomorphic to a given 3-manifold M. For example, we prove that the problem to recognize whether a triangulated 3-manifold is homeomorphic to a 3-sphere, or to a 2-sphere bundle over a circle, or to a real projective 3-space, or to a handlebody of genus g, is decidable in nondeterministic polynomial time (NP) of size of the triangulation. We also show that the problem to determine whether a triangulated orientable 3-manifold is irreducible (or prime) is in PSPACE and whether it is ∂-irreducible is in coNP. The proofs improve and extend arguments of prior author’s article on the recognition problem for the 3-sphere.      

Computing an Element in the Lexicographic Kernel of a Game

The lexicographic kernel of a game lexicographically maximizes the surplusses s _ij (rather than the excesses as would the nucleolus) and is contained in both the least core and the kernel. We show that an element in the lexicographic kernel can be computed efficiently, provided we can efficiently compute the surplusses s _ij (x) corresponding to a given allocation x. This approach improves the results in Faigle et al. (in Int J Game Theory 30:79–98, 2001) and allows us to determine a kernel element without appealing to Maschler transfers in the execution of the algorithm.We thank the referees for clarifying the presentation of the proof of Proposition 2.1.     

On the complexity of computing Kostka numbers and Littlewood-Richardson coefficients

Kostka numbers and Littlewood-Richardson coefficients appear in combinatorics and representation theory. Interest in their computation stems from the fact that they are present in quantum mechanical computations since Wigner [15]. In recent times, there have been a number of algorithms proposed to perform this task [1–3, 11, 12]. The issue of their computational complexity has received at-tention in the past, and was raised recently by E. Rassart in [11]. We prove that the problem of computing either quantity is #P-complete. Thus, unless P = NP, which is widely disbelieved, there do not exist efficient algorithms that compute these numbers.