Reputation
1,599
Next privilege 2,000 Rep.
Edit questions and answers
Badges
7 18
Newest
 Nice Answer
Impact
~88k people reached

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.