Skip to main content
Share Your Experience: Take the 2024 Developer Survey
David Monniaux's user avatar
David Monniaux's user avatar
David Monniaux's user avatar
David Monniaux
  • Member for 11 years, 11 months
  • Last seen more than a month ago
14 votes
3 answers
1k views

Proof of undecidability not by reduction from the halting problem

13 votes
1 answer
733 views

Complexity of the problem of words with fewest distinct letters accepted by a finite automaton

10 votes
1 answer
284 views

Algorithms on graphs represented using BDDs

9 votes
0 answers
125 views

Complexity of checking the equivalence of constraints and generator descriptions of convex polyhedra

8 votes
1 answer
202 views

Decidability of inductive invariant existence in Presburger arithmetic

8 votes
0 answers
163 views

Practical interactive proof schemes for NP-hard problems

7 votes
1 answer
353 views

Reaching the double exponential upper bound in Fourier-Motzkin elimination

6 votes
1 answer
143 views

Complexity of maximizing the number of models in a parametric formula

6 votes
1 answer
209 views

What is known about $\mathrm{NP}^{\mathrm{PP}[1]}$?

6 votes
4 answers
461 views

Simplification of Presburger formulas in practice

0 votes
0 answers
89 views

Complexity of projected model counting