Reputation
1,574
Next privilege 2,000 Rep.
Edit questions and answers
Badges
6 17
Newest
 Yearling
Impact
~54k people reached

Apr
2
awarded  Tag Editor
Apr
2
revised graph-theory wiki description
linked to tag:graph to explain that it is different from this tag
Apr
2
suggested approved edit on graph-theory tag wiki
Mar
27
comment How is the graph coloring problem NP-Complete?
You are talking about coloring of a planar graph, but strictly speaking, the question is about coloring of a general graph.
Mar
16
comment A non-distinct system of representative edges.
@utdiscant: I prefer your terminology, but some people prefer to treat an edge of a graph as a set of two vertices, in which case the wording of the question is fine.
Mar
11
comment Knapsack with non-trivial “utility” function
In the standard Knapsack problem, only single copy of each item is available. You are probably talking about a variation of the NP-hard problem called the unbounded Knapsack problem. Please check the Wikipedia article which you linked to.
Mar
10
comment P or NP-Complete? (concerning 2-CNF formulas)
@J.D.: cs.stackexchange.com is currently in private beta.
Feb
29
awarded  Enlightened
Feb
29
awarded  Nice Answer
Feb
24
comment Properties of a valid DFA
@CamMcLeman: The word “equivalent” in your comment has to be interpreted with caution, because people care about the difference between, say, DFA and NFA, although they are fairly easily proven “equivalent” under some standard terminology.
Feb
19
comment The Average Running Time Of Euclid Algorithm?
What do you mean by “define it in the limit”?
Feb
19
comment No identical rectangles in a matrix
There is an $O(N^2 M \log M)$-time algorithm. (Hint: First consider the case of a 2×M matrix.) I do not know if there is a faster one.
Feb
16
comment 1/3+2/3 in double precision
In general, if you cannot be sure of the correctness of your own calculation, one of the good ways to check the correctness is by writing down steps more carefully. In your case, the first step is to represent 1/3 and 2/3 as double-precision floating-point numbers.
Feb
16
comment How can I create/modify 3-SAT functions according to Valiant-Varizani?
(1) If you do not understand the proof, then do not say “it’s fairly straightforward.” It may seem cool to say that, but it gives a wrong impression that you believe that you have understood the proof. (2) First, forget Boolean formulas (let alone 3CNF formulas) and understand the algorithm which computes h(x) in the lecture note. It is straightforward, but you cannot go forward without understanding that part. After that, convert the algorithm to a 3CNF formula, either by making some observations about the algorithm or by using the reduction in the Cook-Levin theorem.
Feb
16
comment How can I create/modify 3-SAT functions according to Valiant-Varizani?
Judging from the last paragraph, I doubt that you understand the proof of Valiant-Vazirani, in particular the use of pairwise independent family of hash functions in the proof.
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.