Complexity theory/Talk

The study of complex systems is also called complexity theory, which is apparently quite a different subject then the one being discussed here.

Perhaps this article should be [Computational Complexity Theory]?.

    I've added a link at the bottom of the article.  Feel free to write that up.
    I'd be very interested in reading an overview of that kind of complexity theory.  -LC

---

I always thought that NP-hard problems need not be decision problems. For instance, finding the shortest roundtrip in a weighted graph is NP-hard; deciding whether a roundtrip shorter than a given number exists is NP-complete. --AxelBoldt

    Yes, that's right.  The article doesn't say an NP-hard problem must be a 
    "decision problem".  It just says it must be a "problem".  It's correct;
    it just didn't give much detail.  That paragraph
    also didn't use the word "reducibility", or distinguish the two types of 
    reductions.  It also didn't describe when you'd be interested in polytime
    reductions (e.g. for NP-Hard), and when you'd be interested in something
    else (e.g. for P-Hard).

    My intent was to put the details in the 
    NP-Hard article which is linked to, but isn't written yet.  Feel free 
    to expand that paragraph, if you'd like.  Or write the NP-Hard article.  -LC