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

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.
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.