Computer Science
Profile Activity
Meta user
Network profile
xskxzr
Summary Answers Questions Tags Badges Bookmarks Bounties Reputation All actions

225 Answers

Votes Activity Newest
11
Is {a^n (a+b)^n | n>0} a Deterministic CFL?
Mar 24 '18 at 12:04
10
What algorithm should I use to find a minimal tree that include certain nodes within a graph?
Jul 9 '18 at 11:09
8
Under what conditions does the function C = f(A,B) satisfy H(C|A) = H(B)?
Mar 28 '19 at 8:38
7
Prove that “Finishing the degree in three years” problem is NP-Complete
May 12 '19 at 8:39
6
Is Knapsack restricted to integers between 1 and 100 still NP-complete?
Feb 22 '20 at 2:44
6
Does adding S->SS in a context-free grammar change the language to its Kleene star?
Jun 14 '18 at 6:46
6
Empty intersection of longest path in connected graph
Apr 17 '18 at 9:23
6
Finding the smallest string that contains a given set of substrings
Feb 21 '18 at 14:10
5
Prove that the 2-approximation of a modified local search algorithm for max-cut is tight
Dec 21 '19 at 4:02
5
How to reduce 3-COLOR to 42-COLOR?
Dec 16 '18 at 14:55
5
Vertex cover with covering radius 2
Sep 15 '18 at 7:50
5
Is it NP complete to decide whether a graph has $k$ disjoint triangles?
May 12 '18 at 15:51
5
How to maximize $(h[j]-h[i])(j-i)$ in $O(n)$
Feb 7 '18 at 13:09
5
Graph where only two vertices have the same degree
Jan 21 '18 at 2:47
4
Show a TM-recognizable language of TMs can be expressed by TM-description language of equivalent TMs
Mar 11 '18 at 7:31
4
In a DAG, finding the path with the highest score
Mar 13 '20 at 3:15
4
find the union of all min cuts of a flow network
Dec 22 '19 at 3:35
4
How to give a context-sensitive grammar for a^nba^nba^nb?
Jun 21 '19 at 7:06
4
Worst-case input for median-of-medians with groups of size 3
Apr 13 '19 at 4:18
4
Finding a negative cycle in a bipartite graph
Apr 5 '19 at 13:10
4
Create a grammar that generate the language a^n . b^m . c^q . d^p such that n + p = q + m
Mar 7 '19 at 12:07
4
Is DFA and Regular Expression equivalent?
Aug 24 '18 at 9:57
4
Is it NP hard to partition a graph into 2 vertex sets with minimum degree of 2 and 3?
May 21 '18 at 9:11
4
Is there any language that can be Turing-reduced to all languages?
Apr 8 '18 at 3:48
4
Union-Find with link-by-rank to represent a binary field with simple operations
Mar 18 '18 at 3:22
4
Checking if there is a single path that visits all nodes in a directed graph
Feb 21 '18 at 3:57
3
Context free grammar problem for number of a's is twice the number of b's
Aug 6 '20 at 11:40
3
Saturated sets in bipartite graph
Apr 17 '20 at 12:20
3
Are weakly polynomial time algorithms truly polynomial?
Feb 26 '20 at 2:22
3
Given a network flow find if there's a min cut that only one of the given edges lay on it
Jan 18 '20 at 10:46
1
2 3 4 5
…
8