1,564 reputation
617
bio website
location
age 35
visits member for 4 years, 2 months
seen 7 hours ago

Nov
19
comment How to express the following algorithm more concisely
You are not processing matrix S in any way. What is relevant is the integers associated with each row, but from your description, they have nothing to do with matrix S.
Nov
19
comment How to express the following algorithm more concisely
The matrix S does not seem relevant to your algorithm.
Nov
19
comment Find a path in G which cross all the edges in $A\subseteq E$
Sorry, I overlooked that your G was a directed graph.
Nov
18
comment Find a path in G which cross all the edges in $A\subseteq E$
Do you allow to use the same edge more than once? If so, it is always possible as long as the graph is connected.
Nov
18
comment Connecting cells by line and column permutations in a finite grid
Simultaneous crosspost is discouraged.
Nov
17
comment Is it possible to remove exactly one solution from a CNF in polynomial time?
I think that the essential part of this question is interesting, but I agree with joriki that in its current form, the answer is “no” for a trivial and inessential reason.
Nov
17
awarded  Disciplined
Nov
17
comment Is coNP closed under Kleene star?
I tend not to use the term “certificate” in the coNP case because its meaning is so different from the usual meaning of the word “certificate” in English, but I guess that some people use in the way you did. Sorry for taking long to realize that I was just confused by the terminology.
Nov
17
comment Is coNP closed under Kleene star?
Now I think that I understand what you mean by certificate for a coNP-language, but is that a usual terminology? In what I am familiar with, it is a string which is not a certificate for the complement of L.
Nov
16
comment Is coNP closed under Kleene star?
When L is in coNP, “certificate for L” is not well-defined. Now I see that you probably have a correct algorithm in mind (which is indeed simpler than what I was thinking), but it is not correctly stated in your answer.
Nov
16
comment Is coNP closed under Kleene star?
Your algorithm for coNP does not work. A nondeterministic Turing machine for the complement of L* is required to certify the absence of a path, and your NTM is doing something else (what it is doing is unclear to me). Hint: Use the same graph, but try to find a cut in the graph.
Nov
10
comment Is there a log-space algorithm for divisibility?
@Kaveh: That is true. I did not mention that result in the answer because I wanted to keep the answer simple by focusing on space complexity by a Turing machine.
Nov
6
comment Which oracles does Relativization apply to?
What you are doing does not sound like anything related to whether P=NP or P≠NP, although I cannot follow much of your comment.
Nov
6
comment Which oracles does Relativization apply to?
Because “using an oracle” is a very vague notion, any possibility exists. The result by Baker, Gill, and Solovay implies that whether P^A = NP^A or not depends on oracle A, and therefore if one argument applies to all oracles A, it cannot settle whether P=NP or not.
Nov
6
comment Which oracles does Relativization apply to?
Baker, Gill, and Solovay proved two facts, and both are in the form “There exists an oracle relative to which ….” Therefore, these results do not talk about all oracles.
Oct
26
comment Is there a log-space algorithm for divisibility?
I realized that the master thesis of Chiu in 1995 seems to contain a proof that integer division is in L (and more strongly in log-space-uniform NC1), and I am not sure its relation to [CDL01] because I cannot access [CDL01].
Oct
26
comment Is there a log-space algorithm for divisibility?
By the way, according to the introduction of [BCH86], there seems to be a folklore O((log n)^2)-space algorithm.
Oct
26
answered Is there a log-space algorithm for divisibility?
Oct
26
revised Finding a pair of edge disjoint paths in a graph, such that the weight of each of them is bounded
linkified; corrected a seeming typo; spelled out ILP
Oct
26
suggested suggested edit on Finding a pair of edge disjoint paths in a graph, such that the weight of each of them is bounded