3
votes
Is the reversal of a minimal DFA also minimal?
The "standard" example that shows that the NFA to DFA construction is exponential in size also works for reversal.
The DFA for $\{0,1\}^*1\{0,1\}^n$, the $n+1$-st symbol from the right is $1$...
- 28.2k
2
votes
Computer Algebra: Algorithms for solving equations symbolically
I am no specialist, but IMO this problem is even harder than symbolic integration, and I have not heard of a general theorem that would parallel that of Liouville. (https://en.wikipedia.org/wiki/...
- 5,285
1
vote
Sieve of Eratosthenes for factorization: bitwise complexity?
Newer multiplication algorithms aren't needed to show such a time bound in this model.
Given a precomputed multiplication table of size $O(p)$, multiplication $a \times b$ of $a, b \leq p^{O(1)}$ ...
- 1,511
1
vote
Accepted
Can equations be simplified with the help of a given set of equations?
If your knowledge is in the form of linear equations, as in your example, then you can make a simple substitution. In your example, set $b=2-a$ and $y=-1-x$, as Yves Daoust suggests. This will work ...
D.W.♦
- 145k
1
vote
Tiling a simple polygon with hexagons
Checking if two polygons intersect is equivalent to checking if a point lies inside their Minkwoski sum. Illustration with a triangle:
The Minkowki sum of a polygon and a convex hexagon is found in ...
- 5,285
Only top scored, non community-wiki answers of a minimum length are eligible