On the approximability of comparing genomes with duplicates.
On the average case complexity of some P-complete problems
On the Average Case Complexity of Some P-complete Problems
We show that some classical P-complete problems can be solved efficiently in average NC. The probabilistic model we consider is the sample space of input descriptions of the problem with the underlying distribution being the uniform one. We present parallel algorithms that use a polynomial number of processors and have expected time upper bounded by (e ln 4 + o(1))log n, asymptotically with high probability, where n is the instance size.
On the average minimal prefix-length of the generalized semi-Dycklanguage
On the average number of registers needed to evaluate a special class of backtrack trees
On the Ball Spanned by Balls.
On the categorical semantics of elementary linear logic.
On the classes of languages accepted by limited context restarting automata
In the literature various types of restarting automata have been studied that are based on contextual rewriting. A word w is accepted by such an automaton if, starting from the initial configuration that corresponds to input w, the word w is reduced to the empty word by a finite number of applications of these contextual rewritings. This approach is reminiscent of the notion of McNaughton families of languages. Here we put the aforementioned types of restarting automata into the context of McNaughton...
On the complexities of selected satisfiability and equivalence queries over Boolean formulas and inclusion queries over hulls.
On the Complexity of a Single Cell in Certain Arrangements of Surfaces Related to Motion Planning.
On the complexity of computable real sequences
On the complexity of covering nodes by K node-disjoint cycles
On the complexity of events recognizable in real time
On the complexity of parametrizing curves.
On the Complexity of Polyhedral Separability.
On the complexity of problems on simple games
Simple games cover voting systems in which a single alternative, such as a bill or an amendment, is pitted against the status quo. A simple game or a yes-no voting system is a set of rules that specifies exactly which collections of “yea” votes yield passage of the issue at hand. Each of these collections of “yea” voters forms a winning coalition. We are interested in performing a complexity analysis on problems defined on such families of games. This analysis as usual depends on the game representation...
On the complexity of problems on simple games
Simple games cover voting systems in which a single alternative, such as a bill or an amendment, is pitted against the status quo. A simple game or a yes-no voting system is a set of rules that specifies exactly which collections of “yea” votes yield passage of the issue at hand. Each of these collections of “yea” voters forms a winning coalition. We are interested in performing a complexity analysis on problems defined on such families of games....
On the Complexity of Reinforcement in Graphs
We show that the decision problem for p-reinforcement, p-total rein- forcement, total restrained reinforcement, and k-rainbow reinforcement are NP-hard for bipartite graphs.
On the complexity of the Double Digest Problem
On the complexity of the hidden weighted bit function for various BDD models