Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR06-027 | 22nd February 2006 00:00

Finding Lower Bounds for Nondeterministic State Complexity is Hard



We investigate the following lower bound methods for regular
languages: The fooling set technique, the extended fooling set
technique, and the biclique edge cover technique. It is shown that
the maximal attainable lower bound for each of the above mentioned
techniques can be algorithmically deduced from a canonical finite
graph, the so called dependency graph of a regular
language. This graph is very helpful when comparing the techniques
with each other and with nondeterministic state complexity. In most
cases it is shown that for any two techniques the gap between the
best bounds can be arbitrarily large. The only exception is the
biclique edge cover technique which is always as good as the
logarithm of the deterministic or nondeterministic state complexity.
Moreover, we show that deciding whether a certain lower bound
w.r.t. one of the investigated techniques can be achieved is in
most cases computationally hard, i.e., PSPACE-complete and hence
are as hard as minimizing nondeterministic finite automata.

ISSN 1433-8092 | Imprint