Reputation
4,929
Top tag
Next privilege 5,000 Rep.
Approve tag wiki edits
Badges
19 43
Impact
~284k people reached

Mar
19
awarded  Civic Duty
Mar
19
answered Quicksort with Trivalued Logic
Mar
18
answered What is $\gcd(0,a)$, where a is a positive integer?
Mar
17
revised Floyd's algorithm for the shortest paths…challenging
fixed up, explained algebra, added extra commentary
Mar
17
revised Floyd's algorithm for the shortest paths…challenging
added 359 characters in body
Mar
17
comment Floyd's algorithm for the shortest paths…challenging
I'm wondering, was this for homework? Or what? It's a good concept to know about. But it is kind of a mess to actually calculate by hand.
Mar
17
comment Integer multiplication using FFT
Excellent example...ya know, you can make your own answer out of this so it is sorta official.
Mar
17
answered Floyd's algorithm for the shortest paths…challenging
Mar
17
comment Decision procedure for the problem of regular expression equivalence with not
But if you're expecting to use nested 'not's, as one might expect if you need to implement this, the stack of two's goes up by the nesting depth. By depth 5 or $2^{65536}$, you're already well beyond the number of particles in the universe.
Mar
17
answered Decision procedure for the problem of regular expression equivalence with not
Mar
17
answered What are good books to learn graph theory?
Mar
17
answered Good Book On Combinatorics
Mar
17
comment Good Book On Combinatorics
These are both good for non-advanced learning.
Mar
16
comment How does Lambert's W behave near ∞?
+1 for referring to the Stirling number used as the 'Stirling cycle' number. Whoever originally named them '.. of the first kind' and '...of the 2nd kind' cost the world precious brain energy in trying to remember which was which.
Mar
16
comment NP vs NP-Complete
@Moron: Given that NP-completeness is defined using PTIME reductions, I realize now that if $P=NP$ then, yes, all problems in NP would be NP-complete (except for the pedantic trivial case I mention). But I still find this an annoying technicality. The whole direction of proliferation of complexity classes is to either show that some collapse (some definitions turn out to describe the same class) or show strict inclusion, and lumping all subclasses of P together ignores the complex hierarchy there.
Mar
15
awarded  Quorum
Mar
15
comment NP vs NP-Complete
@Moron:If P=NP, then every P-complete problem is NP-Complete. There are problems in P (and therefore NP) that provably not NP-complete. To amend your answer, it should be "If there is some problem that is P-complete, but it is provably not NP-Complete, it would imply that P≠NP." (and the rest of your answer though true and interesting is not saying the relevant story: there's an infinite hierarchy -beneath- P, too. (yes, as one gets smaller and smaller, one must use much more restricted reductions there, even more than logspace).
Mar
15
comment NP vs NP-Complete
@Moron: If a problem in P is shown to be NP-complete, then that shows that P=NP. But if the problem in P is -not- NP-complete, it does not follow that P != NP. Take an extreme class, the class of problems that take constant time to decide (i.e. need no resources at all to decide). This is -definitely- a subset of NP (you can easily compute these constant time decision problems using an NP TM (you can always use less than you have available). But trivially -no- problem here is NPC. ANd this is not a proof of 'P!=NP'. There are nontrivial problems that provably NPC problems do not to.
Mar
15
comment Non-associative, non-commutative binary operation with a identity
@Vafa Khalighi: If there is an identity in a associative, commutative groupoid, then it must be both left and right, but a left identity in an nonassociative noncommutative groupoid is not guaranteed to be a right identity. Thats why I asked (also, in all the excellent examples given by Jacob Schlater, the identity is only one sided).
Mar
15
answered NP vs NP-Complete