user avatar
user avatar
user avatar
dspyz
  • Member for 9 years, 6 months
  • Last seen more than a month ago
10 votes
2 answers
2k views

Is Almost-2-SAT NP-hard?

6 votes
1 answer
390 views

Would an optimal sorting network ever have to swap two numbers the "wrong" way

6 votes
1 answer
226 views

Does the 0-1 principle apply to merge networks?

5 votes
1 answer
466 views

Worst case ratio between minimum clique cover and maximum independent set

5 votes
1 answer
83 views

Can a normal form term be extensionally equivalent to a term with no WHNF?

4 votes
1 answer
338 views

Asymptotic complexity of CDCL SAT solver that only selects negative literals

3 votes
1 answer
80 views

Translating pure literal elimination into rup

2 votes
1 answer
947 views

How to approximate minimum clique edge cover

2 votes
0 answers
190 views

Most general form of SAT which is in P

1 vote
0 answers
72 views

Best Asymptotic Complexity for Persistent Union Find

1 vote
0 answers
45 views

Find all paths between specially paired nodes in a DAG in linear time

0 votes
0 answers
35 views

Is having a particular form equivalent to being computable for functions on Church numerals?

0 votes
0 answers
198 views

Finding assignment-minimum complete k-partite graph cover

0 votes
3 answers
276 views

Terminology for complete k-partite graph where k is not fixed

-2 votes
1 answer
67 views

Assign each biclique to a distinct left