We’re rewarding the question askers & reputations are being recalculated! Read more.

Questions tagged [bounds]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
11
votes
2answers
577 views

Fun with inverse Ackermann

The inverse Ackermann function occurs often when analyzing algorithms. A great presentation of it is here: http://www.gabrielnivasch.org/fun/inverse-ackermann. $$\alpha_1(n) = [n/2]$$ $$\alpha_2(n) = ...
0
votes
1answer
284 views

What relations has different bounds for NP?

this is my first question here so I hope I've done everything correctly. I know that if someone finds a polynomial solution to any of the famous NP problems, all of them has one (polynomial solution)....
16
votes
3answers
2k views

Can a nondeterministic finite automata (NDFA) be efficiently converted to a deterministic finite automata (DFA) in subexponential space/time?

Twenty years ago, I built an regular expression package that included conversions from regular expressions to a finite state machine (DFA) and supported a host of closed regular expression operations ...