user avatar
user avatar
user avatar
xskxzr
  • Member for 4 years, 6 months
  • Last seen this week
  • 中国
29 votes
Accepted

Recover a set with the information of the sums of all its subsets

11 votes
Accepted

Is {a^n (a+b)^n | n>0} a Deterministic CFL?

10 votes
Accepted

What algorithm should I use to find a minimal tree that include certain nodes within a graph?

8 votes

Under what conditions does the function C = f(A,B) satisfy H(C|A) = H(B)?

7 votes
Accepted

Finding the smallest string that contains a given set of substrings

7 votes

Prove that "Finishing the degree in three years" problem is NP-Complete

6 votes
Accepted

Worst-case input for median-of-medians with groups of size 3

6 votes
Accepted

Is Knapsack restricted to integers between 1 and 100 still NP-complete?

6 votes
Accepted

Empty intersection of longest path in connected graph

6 votes

Does adding S->SS in a context-free grammar change the language to its Kleene star?

5 votes
Accepted

Is it NP complete to decide whether a graph has $k$ disjoint triangles?

5 votes
Accepted

Graph where only two vertices have the same degree

5 votes
Accepted

How to maximize $(h[j]-h[i])(j-i)$ in $O(n)$

5 votes

How to reduce 3-COLOR to 42-COLOR?

5 votes
Accepted

Vertex cover with covering radius 2

5 votes
Accepted

Prove that the 2-approximation of a modified local search algorithm for max-cut is tight

4 votes
Accepted

find the union of all min cuts of a flow network

4 votes
Accepted

Are weakly polynomial time algorithms truly polynomial?

4 votes
Accepted

In a DAG, finding the path with the highest score

4 votes

How to give a context-sensitive grammar for a^nba^nba^nb?

4 votes
Accepted

Finding a negative cycle in a bipartite graph

4 votes
Accepted

Is DFA and Regular Expression equivalent?

4 votes
Accepted

Create a grammar that generate the language a^n . b^m . c^q . d^p such that n + p = q + m

4 votes
Accepted

Checking if there is a single path that visits all nodes in a directed graph

4 votes

Show a TM-recognizable language of TMs can be expressed by TM-description language of equivalent TMs

4 votes
Accepted

Time complexity of computing binomial coefficients (with binary representation of integers)

4 votes
Accepted

Union-Find with link-by-rank to represent a binary field with simple operations

4 votes
Accepted

Is it NP hard to partition a graph into 2 vertex sets with minimum degree of 2 and 3?

4 votes

Is there any language that can be Turing-reduced to all languages?

3 votes
Accepted

Halting problem for polynomial space bounded Turing machines

1
2 3 4 5
8