Reputation
4,869
Top tag
Next privilege 5,000 Rep.
Approve tag wiki edits
Badges
19 42
Newest
 Talkative
Impact
~263k people reached

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
Mar
15
comment NP vs NP-Complete
The OP didn't restrict things to between P and NP. There are classes that are subsets of P which might be proper subclasses.
Mar
15
comment How does e, or the exponential function, relate to rotation?
I hope I'm not being obtuse, but I just don't see immediately what the composition inverse of exponentiation (the natural log) corresponds to here. Is it rotation in the other direction? That seems to be the multiplicative inverse (the negative angle). What corresponds to taking the log of ...well of what? The log of a complex number is an angle? That's what isn't obvious.
Mar
15
comment How does e, or the exponential function, relate to rotation?
This explains something about $e$ and exponeniation. What about the inverse, the natural log?