iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: http://en.m.wikipedia.org/wiki/Talk:Complexity_theory
Talk:Complexity theory - Wikipedia

Talk:Complexity theory

Latest comment: 19 years ago by Theboywonder in topic Complexity

Also

edit

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

edit

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

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