1,534 reputation
517
bio website
location
age 35
visits member for 3 years, 11 months
seen Jul 3 at 21:51

Oct
25
comment Merlin-Arthur complexity class for function problems
@Tom: From your comment, I doubt that you understand the definition of FNP. Please check the definition of FNP.
Oct
25
comment Is there a log-space algorithm for divisibility?
Integer division is known to be in L. Page 22 of the slides “My Favorite Ten Complexity Theorems of the Past Decade II” by Lance Fortnow refers to Chiu 1995, although I cannot locate this reference right now. If you can access Chiu, Davida, and Litow 2001, I am sure that it contains the reference to it.
Oct
25
answered Merlin-Arthur complexity class for function problems
Oct
18
comment A constrained topological sort?
Whether r>1 or r<1 does not matter because the case of r<1 can be handled by considering 1/r and reversing the result.
Oct
17
revised How to determine if a graph is 3-colorable, given a way to determine for any graph if removing an edge from that graph gives a 3 colorable graph?
better wording
Oct
15
revised How to determine if a graph is 3-colorable, given a way to determine for any graph if removing an edge from that graph gives a 3 colorable graph?
typo
Oct
15
answered How to determine if a graph is 3-colorable, given a way to determine for any graph if removing an edge from that graph gives a 3 colorable graph?
Oct
11
comment Is chess Turing-complete?
There is a closely related question on MathOverflow: Decidability of chess on an infinite board.
Oct
9
awarded  Tumbleweed
Oct
7
comment Reduction over intersection of languages
@XavierLabouze: Requiring the intersection to be nonempty does not make any essential difference. Please think about it.
Oct
7
answered Reduction over intersection of languages
Oct
5
comment Find the subset of a graph that has the highest minimum spanning tree benefit and a total edge weight within some threshold
@Steven: As long as you want an exact algorithm which works for all instances of your problem, there is no hope (unless you can prove P=NP ☺). Typical ways to cope with NP-completeness are (1) try exponential-time algorithms if your instances are small enough, (2) give up solving all the instances and try to find specific structures in instances you want to solve, and (3) consider approximation algorithms. A gentle introduction to them can be found in Garey and Johnson.
Oct
5
revised Find the subset of a graph that has the highest minimum spanning tree benefit and a total edge weight within some threshold
improved wording and made other minor edits
Oct
5
answered Find the subset of a graph that has the highest minimum spanning tree benefit and a total edge weight within some threshold
Oct
5
comment Find the subset of a graph that has the highest minimum spanning tree benefit and a total edge weight within some threshold
Thank you for fixing it. I realized another typo: the formal definition mentions c_0, but it is probably a typo for v_0.
Oct
5
comment Find the subset of a graph that has the highest minimum spanning tree benefit and a total edge weight within some threshold
“I would like to find a minimum spanning tree” That is wrong according to your description of the problem following that part. What you want to find is a subset S⊆V.
Oct
3
revised Finding edges that are not part of any perfect matching
made minor changes
Oct
3
answered Finding edges that are not part of any perfect matching
Sep
12
comment Regular Expression question
I see. I did not read the answer carefully. Sorry for that. Still, I think that it is easy to see why I misinterpreted your answer, given that (as I explained in my previous comment) I consider that the word “complete” in the question means that it is as powerful as regular expressions in formal language theory.
Sep
8
comment Regular Expression question
I thought that “complete” in the question (hence also in your answer) means that BRE is as powerful as regular expressions. If not, I do not know what it is supposed to mean.