1,564 reputation
617
bio website
location
age 35
visits member for 4 years, 4 months
seen Nov 10 at 6:16

Oct
26
comment The tricky time complexity of the permutation generator
“When classifying problems, they are not classified according to the size of the output, in bits, but rather, the size of the input.” This claim is too strong to be true. When we study enumeration problems (such as the one in the question), considering the time complexity in terms of output size is very common. On the other hand, you are right in that complexity classes P and EXP are defined in terms of the time complexity as a function of the input size. (Here I put aside the fact that they are usually defined as classes of decision problems instead of enumeration problems.)
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.