user avatar
user avatar
user avatar
a3nm
  • Member for 11 years, 4 months
  • Last seen more than a week ago
50 votes
0 answers
2k views

Monotone complexity of s-t connectivity

  • 6,635
31 votes
5 answers
1k views

what is easy for minor-excluded graphs?

30 votes
0 answers
744 views

The complexity of checking whether two DAG have the same number of topological sorts

  • 709
30 votes
2 answers
1k views

Commonest Subsequence

  • 1,100
30 votes
5 answers
3k views

Binary search generalizations for posets?

  • 8,651
29 votes
2 answers
2k views

How many DFAs accept two given strings?

  • 10.1k
24 votes
2 answers
568 views

Relation between hardness of recognition of a graph class and forbidden subgraph characterization

24 votes
1 answer
862 views

What is the complexity of this covering problem?

23 votes
3 answers
727 views

Convex Body with minimum expected l2 norm

22 votes
2 answers
2k views

Detecting two kinds of almost-simple polygons

  • 22.8k
20 votes
5 answers
2k views

A special class of languages: “circular” languages. Is it known?

18 votes
0 answers
474 views

Perfect matching of monotone Boolean function with null Euler characteristic

  • 1,197
18 votes
2 answers
470 views

Separating words with random DFAs

17 votes
1 answer
453 views

What is the complexity of this graph problem?

15 votes
0 answers
620 views

Is it NP-hard to find (the root of) a small decision tree for a monotone boolean function?

  • 4,746
14 votes
0 answers
294 views

Is this problem on unambiguous finite automata NP-complete?

  • 1,197
12 votes
0 answers
279 views

Hardness of optimal sorting

  • 1,085
10 votes
0 answers
595 views

Simple path on dag with backward edges

  • 1,085
10 votes
0 answers
244 views

Complexity of the min edge-colored cut problem

  • 101
10 votes
1 answer
682 views

What class of languages is recognized by finite-state automata with $k$ heads?

  • 842
10 votes
1 answer
184 views

Tree decompositions of optimal width where every vertex is in a bounded number of bags?

  • 161
9 votes
1 answer
611 views

Minimum spanning tree over all vertex matchings

  • 313
9 votes
1 answer
2k views

What's the expected length of the shortest hamiltonian path on a randomly selected points from a planar grid?

  • 251
9 votes
0 answers
122 views

Computing weighted sums of binomial coefficients

  • 1,085
9 votes
1 answer
382 views

"Verifiable information": is this a known concept?

  • 2,131
9 votes
1 answer
355 views

Transition monoid membership for DFAs

  • 1,345
8 votes
0 answers
113 views

Computing the most likely winner in elections : intermediate case between Kemeny and Borda?

  • 1,085
8 votes
0 answers
256 views

Existence of "colouring matrices" — a generalisation

8 votes
2 answers
799 views

Finding a subset of a set in a collection of sets

8 votes
3 answers
385 views

Find the nearest $d+1$ corners of a cube in $\mathbb{R}^d$

  • 325