Tsuyoshi Ito
Reputation
1,574
Next privilege 2,000 Rep.
Edit questions and answers
6 17
Impact
~52k people reached

• 0 helpful flags
• 140 votes cast

229 Actions

 Feb12 comment Different solutions under distributive and commutative equivalence Not that I know a fast algorithm, but I would suggest to break the problem into two parts: finding all the solutions which result in the desired result, and deciding whether two solutions are equivalent (in your sense) or not. Feb3 comment Converse of Gold's theorem and necessary condition for unlearnability I would ask for sufficient conditions for learnability rather than necessary conditions for unlearnability because the latter sounds confusing. Jan26 revised A question on context-free languages from Sipser's computation book edited tags Jan19 comment Question about greedy algorithms @Raphael: I suppose that radius r is given as part of input. Jan17 answered Is there an efficient algorithm to find a length maximizing combination? Jan17 comment Is there an efficient algorithm to find a length maximizing combination? @PeterTaylor: Minimization of a convex quadratic function over a polytope is solvable in polynomial time by using ellipsoid or interior-point method. Therefore, probably the reduction you are thinking of does not work. Jan17 comment Is there an efficient algorithm to find a length maximizing combination? Maximization of a convex quadratic function over [0,1]^n (or {0,1}^n, which is equivalent) is NP-hard, e.g. by a reduction from the subset sum problem. Jan17 comment Running time (Big O) of counting in binary Well, that is why I said that it is easier to argue in a different order. Jan17 comment Running time (Big O) of counting in binary Strictly speaking, when you claim that T(n) is at most two times $T(2^m)$, you are using the fact $T(2^{m+1}) \le 2T(2^m)$ before you prove it. To avoid this, it is easier to argue in a different order: first you show what $T(2^m)$ is, and then you show that T(n) is within a factor of two from $T(2^m)$. Jan11 comment What does this “double less than or equals to” sign mean? In short, $\leqq=\leq$. Jan5 comment Is Turing completeness monotone with respect to Cook reductions? The term “Turing complete” is usually used for a computational model, not for a language. What do you mean by “The language of Boolean expressions is Turing complete”? Dec20 comment Finding equivalent matrix product of a simple quantum circuit @user4143: To have this answer rendered correctly, you need a font which supports character U+27E9 (Mathematical Right Angle Bracket). I personally prefer to avoid MathJax because it seems like an unnecessarily complicated system. Dec18 revised Finding equivalent matrix product of a simple quantum circuit simplified the counterexample a little Dec18 answered Finding equivalent matrix product of a simple quantum circuit Dec14 comment CNF to DNF — conversion is NP Hard @HenningMakholm: “NP-hardness is usually formulated only for decision problems”: That claim is too general to be true. Some people prefer to consider Turing reducibility by default (although I do not). NP-hardness under Turing reducibility applies to function problems or relation problems as well as to decision problems. Nov25 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?) Nov22 answered Complexity of sorting algorthms Nov22 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? Nov20 comment Does DTIME(O(n)) = REGULAR? @DimitriSurinx: The equality REG=DSPACE(O(1)) is almost by definition. The question asks about something deeper. Nov19 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.