4 ms·
Considering that people were having typical days of programming before complexity theory existed, of course it's not required. I don't know of anybody who serio
by j2kun 12y ago
Considering that people were having typical days of programming before complexity theory existed, of course it's not required. I don't know of anybody who seriously claims that it is required.
- kristjan 12y agoComplexity theory had been explored, if not deeply, somewhat before what we'd consider "typical days of programming": https://en.wikipedia.org/wiki/Computational_complexity_theory#History https://en.wikipedia.org/wiki/Computational_complexity_theor...
- j2kun 12y agoI suggest you read that more closely. There was no theory laid out until the late 60's, and "complexity theory" was not a field until the 70's. On the other hand, there is a long list of programming languages invented in the 50's.
- 14113 12y agoI'd argue that the definition of computability is an instance of complexity theory, which easily predates what we'd call "programming".
- j2kun 12y agoDefinitely not. Nobody in mathematics considered the efficiency of Turing machines until the late 60's.
- 14113 12y agoDid I say anything about efficiency? Computability itself is a topic within computational complexity, as (in many ways) it's one of the "hardest" rungs of the complexity ladder.
- j2kun 12y agoI'm sorry, but you're wrong. Complexity theory is by definition the subfield of computer science that studies the efficiency of algorithms, or the inability for algorithms to meet certain efficiency requirements. This is my field of research, and I assure you computability theory is not a subset of it.
- 14113 12y agoNo - complexity theory deals with the "hardness" of problems not of algorithms, and yes, then the bounds on what algorithms we can write to solve them. By that metric (and even by your own argument "the inability for algorithms"), the undecidability of the halting problem definitely fits within the complexity definition.
- j2kun 12y agoIf you won't listen to me (someone who does this for a living) maybe you will listen to a quote from wikipedia: > imposing restrictions on the available resources is what distinguishes computational complexity from computability theory And for the record when I say the ability of algorithms to do something I mean the class of all possible algorithms.
- 14113 12y agoThat is what I understood you as saying. I still don't see how my phrasing of the decidability of the halting problem as a complexity problem is any less valid. In any case, it's clear from your appeal-to-wikipedia that this conversation is over.
- j2kun 12y ago> I still don't see how my phrasing of the decidability of the halting problem as a complexity problem is any less valid. Because you are not constraining any resources.