Complexity arguments in algebraic language theory
Complexity aspects of the Helly property: graphs and hypergraphs.
Complexity of partial inverse assignment problem and partial inverse cut problem
For a given partial solution, the partial inverse problem is to modify the coefficients such that there is a full solution containing the partial solution, while the full solution becomes optimal under new coefficients, and the total modification is minimum. In this paper, we show that the partial inverse assignment problem and the partial inverse minimum cut problem are NP-hard if there are bound constraints on the changes of coefficients.
Complexity of Partial Inverse Assignment Problem and Partial Inverse Cut Problem
For a given partial solution, the partial inverse problem is to modify the coefficients such that there is a full solution containing the partial solution, while the full solution becomes optimal under new coefficients, and the total modification is minimum. In this paper, we show that the partial inverse assignment problem and the partial inverse minimum cut problem are NP-hard if there are bound constraints on the changes of coefficients.
Complexity of Stratifications of Semi-Pfaffian Sets.
Complexity of the decidability of the unquantified set theory with a rank operator.
Computational complexity of a statistical theoremhood testing procedure for propositional calculus with pseudo-random inputs
Computing a Centerpoint of a Finite Planar Set of Points in Linear Time.
Computing complexity distances between algorithms
We introduce a new (extended) quasi-metric on the so-called dual p-complexity space, which is suitable to give a quantitative measure of the improvement in complexity obtained when a complexity function is replaced by a more efficient complexity function on all inputs, and show that this distance function has the advantage of possessing rich topological and quasi-metric properties. In particular, its induced topology is Hausdorff and completely regular. Our approach is applied to the measurement...
Computing Convolutions by Reciprocal Search.
Computing Simple Circuits from a Set of Line Segments.
Computing the dimension of a semi-algebraic set.
Computing the Geodesic Center of a Simple Polygon.
Computing the Link Center of a Simple Polygon.
Computing the Volume, Counting Integral Points, and Exponential Sums.
Computing the Volume is Difficult.
Computing -free NFA from regular expressions in time
Computing ϵ-Free NFA from Regular Expressions in O(n log2(n)) Time
The standard procedure to transform a regular expression of size n to an ϵ-free nondeterministic finite automaton yields automata with O(n) states and O(n2) transitions. For a long time this was supposed to be also the lower bound, but a result by Hromkovic et al. showed how to build an ϵ-free NFA with only O(n log2(n)) transitions. The current lower bound on the number of transitions is Ω(n log(n)). A rough running time estimation for the common follow sets (CFS) construction proposed...
Congruence classes in regular varieties.
Congruence, Similarity, and Symmetries of Geometric Objects.