Tsuyoshi Ito
Reputation
1,599
Next privilege 2,000 Rep.
 Feb 15 comment The Average Running Time Of Euclid Algorithm? For every d, there are infinitely many pairs (m,n) such that gcd(m,n)=d. How do you define the average? Feb 15 answered if P=NP, then is E=NE? Feb 12 answered Different solutions under distributive and commutative equivalence Feb 12 comment Different solutions under distributive and commutative equivalence @Rik: Yes, append any two numbers and operators + and / to the formulas I showed, such as (((3−2)×6)+12)/9 and (((6−3)×2)+12)/9. Feb 12 comment Different solutions under distributive and commutative equivalence @RikPoggi: If that is the question, then you should have asked it. It is much simpler than the current question. The answer is no. Consider two formulas (3−2)×6=6 and (6−3)×2=6. If we forget the numbers and just consider them as (x−y)×z and (z−x)×y, they are not equivalent. They happen to be equal because of the particular choice of the numbers. Feb 12 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. Feb 3 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. Jan 26 revised A question on context-free languages from Sipser's computation book edited tags Jan 19 comment Question about greedy algorithms @Raphael: I suppose that radius r is given as part of input. Jan 17 answered Is there an efficient algorithm to find a length maximizing combination? Jan 17 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. Jan 17 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. Jan 17 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. Jan 17 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)$. Jan 11 comment What does this “double less than or equals to” sign mean? In short, $\leqq=\leq$. Jan 5 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”? Dec 20 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. Dec 18 revised Finding equivalent matrix product of a simple quantum circuit simplified the counterexample a little Dec 18 answered Finding equivalent matrix product of a simple quantum circuit Dec 14 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.