Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.
user avatar
user avatar
user avatar
a3nm
  • Member for 11 years, 1 month
  • Last seen this week
25 votes
1 answer
883 views

Is it still open to determine the complexity of computing the treewidth of planar graphs?

25 votes
1 answer
772 views

Recognizing sequences with all permutations of $\{1, \ldots, n\}$ as subsequences

23 votes
1 answer
824 views

Languages recognized by polynomial-size DFAs

23 votes
4 answers
6k views

Proof of the pumping lemma for context-free languages using pushdown automata

23 votes
2 answers
538 views

Testing whether letters can be scheduled to achieve a word in a regular language

18 votes
2 answers
2k views

"Almost sorting" integers in linear time

16 votes
1 answer
285 views

Which monotone Boolean functions are representable as thresholds on sums?

16 votes
0 answers
352 views

Complexity of the homomorphism problem parameterized by treewidth

16 votes
2 answers
948 views

Complexity of counting the number of edge covers of a graph

16 votes
1 answer
308 views

What are bounded-treewidth circuits good for?

15 votes
4 answers
423 views

Worst number of questions needed to learn a monotonic predicate over a poset

15 votes
3 answers
1k views

Complexity of topological sort with constrained positions

15 votes
1 answer
482 views

Imperfect subgraph isomorphism

14 votes
2 answers
355 views

Smallest set not included in a collection of sets

13 votes
2 answers
4k views

Lexicographically minimal topological sort of a labeled DAG

13 votes
0 answers
252 views

Which monotone DNFs are evasive?

12 votes
0 answers
180 views

Regular languages accepted by an automaton with at most one transition per letter

12 votes
2 answers
1k views

Enumerating topological sorts of a vertex-labeled DAG

12 votes
0 answers
158 views

Is it #P-hard to compute the number of antichains of a distributive lattice?

12 votes
1 answer
408 views

Minimal elements of a monotonic predicate over the powerset $2^{|n|}$

12 votes
2 answers
5k views

Space complexity to compute the optimal string alignment for the Levenshtein edit distance

11 votes
2 answers
386 views

Find items that are in at least $k$ of $n$ sets

11 votes
2 answers
274 views

Determining what can be achieved by a permutation of elements of a noncommutative group

11 votes
1 answer
1k views

Identifying useless edges for shortest path

11 votes
1 answer
405 views

Generalization of Dilworth's theorem for labeled DAGs

10 votes
0 answers
145 views

Which convex polytopes have volumes of polynomial bit-length?

10 votes
2 answers
329 views

Finding subgraphs with high treewidth and constant degree

10 votes
1 answer
348 views

Complexity of checking if two words have an interleaving in a language

10 votes
1 answer
317 views

Lighting up all elements of a poset by toggling upsets

10 votes
0 answers
129 views

Reconstructing labeled poset from linear extensions