Tsuyoshi Ito
Reputation
1,599
Next privilege 2,000 Rep.
 Nov 25 comment Number Partitioning with Cardinality Constraint: Is that NP-Hard? The statement you quoted alone already implies that the problem in the question is NP-hard. (Exercise: why?) Nov 22 answered Complexity of sorting algorthms Nov 22 comment Do calculators have floating point error? TomCat: “I dont think calculators have round off errors as in floating points.” I think that you are right, but why did you ask the question if you know the answer? Nov 20 comment Does DTIME(O(n)) = REGULAR? @DimitriSurinx: The equality REG=DSPACE(O(1)) is almost by definition. The question asks about something deeper. 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].