Complexity theory/Talk

From Wikipedia

< Complexity theory

HomePage | Recent changes | View source | Discuss this page | Page history | Log in |

Printable version | Disclaimers | Privacy policy

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