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

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 ...
  • 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