Satisfiability and computing van der Waerden numbers.
Selected multicriteria shortest path problems: an analysis of complexity, models and adaptation of standard algorithms
The paper presents selected multicriteria (multiobjective) approaches to shortest path problems. A classification of multi-objective shortest path (MOSP) problems is given. Different models of MOSP problems are discussed in detail. Methods of solving the formulated optimization problems are presented. An analysis of the complexity of the presented methods and ways of adapting of classical algorithms for solving multiobjective shortest path problems are described. A comparison of the effectiveness...
Self-reducibility structures and solutions of NP problems.
Using polynomial time self-reducibility structures, we characterize certain helping notions, show how the characterization provides the main tool for the proof of known relationships between decisional and functional NP-complete problems, and extend this relationships to the case of optimization NP-complete problems.
Semi-algebraic complexity-additive complexity of diagonalization of quadratic forms.
We study matrix calculations such as diagonalization of quadratic forms under the aspect of additive complexity and relate these complexities to the complexity of matrix multiplication. While in Bürgisser et al. (1991) for multiplicative complexity the customary thick path existence argument was sufficient, here for additive complexity we need the more delicate finess of the real spectrum (cf. Bochnak et al. (1987), Becker (1986), Knebusch and Scheiderer (1989)) to obtain a complexity relativization....
Separating Two Simple Polygons by a Sequence of Translations.
Several methods of the reduction of computational complexity.
Shortest Watchman Routes in Simple Polygons.
Signed bits and fast exponentiation
An exact analysis is given of the benefits of using the non-adjacent form representation for integers (rather than the binary representation), when computing powers of elements in a group in which inverting is easy. By counting the number of multiplications for a random exponent requiring a given number of bits in its binary representation, we arrive at a precise version of the known asymptotic result that on average one in three signed bits in the non-adjacent form is non-zero. This shows that...
Similarity relations and cover automata
Cover automata for finite languages have been much studied a few years ago. It turns out that a simple mathematical structure, namely similarity relations over a finite set of words, is underlying these studies. In the present work, we investigate in detail for themselves the properties of these relations beyond the scope of finite languages. New results with straightforward proofs are obtained in this generalized framework, and previous results concerning cover automata are obtained as immediate...
Similarity relations and cover automata
Cover automata for finite languages have been much studied a few years ago. It turns out that a simple mathematical structure, namely similarity relations over a finite set of words, is underlying these studies. In the present work, we investigate in detail for themselves the properties of these relations beyond the scope of finite languages. New results with straightforward proofs are obtained in this generalized framework, and previous results concerning cover automata are obtained as immediate...
Simplifying the propositional satisfiability problem by sub-model propagation.
Simultaneously good bases of a lattice and its reciprocal lattice.
Small-Dimensional Linear Programming and Convex Hulls Made Easy.
Smooth and sharp thresholds for random -XOR-CNF satisfiability
The aim of this paper is to study the threshold behavior for the satisfiability property of a random -XOR-CNF formula or equivalently for the consistency of a random Boolean linear system with variables per equation. For we show the existence of a sharp threshold for the satisfiability of a random -XOR-CNF formula, whereas there are smooth thresholds for and .
Software complexity as a software quality indicator (the three doubts and the light at the end of tunnel)
Some Characteristics of the Process Measure of the Amount of Information
Some graphic uses of an even number of odd nodes
Vertex-degree parity in large implicit “exchange graphs” implies some EP theorems asserting the existence of a second object without evidently providing a polytime algorithm for finding a second object.
Some hardness results for question/answer games.
Some Properties of the Combinational Measure of Complexity of Binary Words
Some Provably Hard Crossing Number Problems.