3 ms·
No - 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
by 14113 12y ago
No - 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.