Talk:Complexity theory

Also

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

Complexity

Where should the Complexity article fit on this disambiguation page? - Theboywonder 07:29, 19 October 2005 (UTC)

Duplicate. Sorry. (Theboywonder 14:20, 19 October 2005 (UTC))