New Applications of Random Sampling in Computational Geometry.
New Bounds for Lower Envelopes in Three Dimensions, with Applications to Visibility in Terrains.
New complexity results for time-constrained dynamical optimal path problems.
New results on generalized graph coloring.
Nondeterminism is essential for reversal-bounded two-way multihead finite automata
Non-deterministic behaviour of deterministic computer
Nonoverlap of the Star Unfolding.
Nonuniform complexity classes specified by lower and upper bounds
Note on the complexity of Las Vegas automata problems
We investigate the complexity of several problems concerning Las Vegas finite automata. Our results are as follows. (1) The membership problem for Las Vegas finite automata is in NL. (2) The nonemptiness and inequivalence problems for Las Vegas finite automata are NL-complete. (3) Constructing for a given Las Vegas finite automaton a minimum state deterministic finite automaton is in NP. These results provide partial answers to some open problems posed by Hromkovič and Schnitger [Theoret....
Note on the number of sequences with given complexity.
Note sur l'algèbre des fonctions
Nový pohled na algoritmickou matematiku
NP-hardness results for intersection graphs
NP-harte Probleme für minimale Polygonüberdeckungen