Mitch
Reputation
4,929
Top tag
Next privilege 5,000 Rep.
Approve tag wiki edits
 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