Skip to main content
D.W.'s user avatar
D.W.'s user avatar
D.W.'s user avatar
D.W.
Moderator
  • Member for 12 years, 3 months
  • Last seen this week
129 votes
15 answers
16k views

How to fool the "try some test cases" heuristic: Algorithms that appear correct, but are actually incorrect

81 votes
3 answers
55k views

Express boolean logic operations in zero-one integer linear programming (ILP)

50 votes
6 answers
59k views

How to prove greedy algorithm is correct

35 votes
5 answers
9k views

Enumerate all non-isomorphic graphs of a certain size

33 votes
3 answers
7k views

Encoding 1-out-of-n constraint for SAT solvers

31 votes
3 answers
10k views

Teaching NP-completeness - Turing reductions vs Karp reductions

28 votes
2 answers
48k views

How to prove that a language is context-free?

22 votes
6 answers
2k views

Algorithm to test whether a language specified in algebraic form is context-free

22 votes
4 answers
571 views

Complexity classes where $C^C = C$

22 votes
3 answers
2k views

Algorithm to minimize surface area, given volume

20 votes
1 answer
2k views

Could min cut be easier than network flow?

19 votes
1 answer
3k views

When to use SAT vs Constraint Satisfaction?

15 votes
2 answers
2k views

MIN-2-XOR-SAT and MAX-2-XOR-SAT: are they NP-hard?

15 votes
0 answers
718 views

Test whether two languages are equal, when give in algebraic form

15 votes
3 answers
3k views

Cast to boolean, for integer linear programming

13 votes
3 answers
6k views

Closest pair of points between two sets, in 2D

12 votes
1 answer
2k views

Algorithm to test whether a language is regular

12 votes
2 answers
2k views

Smallest DFA that accepts given strings and rejects other given strings

11 votes
1 answer
675 views

What do complexity classes look like, if we use Turing reductions?

11 votes
1 answer
2k views

Data structure for map on intervals

10 votes
1 answer
202 views

Mathematical optimization on a noisy function

9 votes
3 answers
4k views

Kernelization trick, for neural networks

9 votes
0 answers
179 views

Boolean formula that agrees with most truth assignments

9 votes
1 answer
1k views

Given n strings, is one of them a substring of another?

9 votes
4 answers
3k views

Can element uniqueness be solved in deterministic linear time?

9 votes
1 answer
239 views

Verify correctness of quantifier elimination, using SAT

7 votes
2 answers
332 views

Automated lip-reading: inferring what someone is saying, based upon video of them speaking

7 votes
1 answer
145 views

Subsequence of one string but not of others

7 votes
2 answers
416 views

Integral solutions to circulation problem

6 votes
1 answer
68 views

Small world theorem for set constraints