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

209 Answers

Newest Activity Votes
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
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
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
Finding the smallest string that contains a given set of substrings
Feb 21 '18 at 14:10
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
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
Graph find all vertices that are part of a cycle
Jun 7 '18 at 13:19
3
find the union of all min cuts of a flow network
Dec 22 '19 at 3:35
3
Are SAT problems with at most one false clause NP-complete?
Oct 15 '19 at 6:36
3
Is {a^n: n is a product of exactly two primes} regular?
Oct 14 '19 at 8:52
3
maximum flow with all or nothing through each edge
Sep 18 '19 at 19:34
3
The time complexity for finding the kth smallest number in a min-heap
Sep 5 '19 at 18:43
3
Proving that EXP doesn't have polynomial-size circuits
Mar 18 '18 at 16:16
3
Is F(F(s,x), x) necessarily a PRF if F is?
Jun 30 '19 at 14:56
1 2 3 4 5 … 7