logoalt Hacker News

voxltoday at 8:17 AM1 replyview on HN

I'm not sure if you're just choosing intentionally obtuse verbiage or if you're actually saying something completely incoherent.

"Overall Complexity" is a meaningless term without you defining it. I suppose you mean that there is some lower bound limit to the amount of work relative to a model of computation, but this is a trivial statement, because the limit is always at least no work.

We have many problems where we don't know the least upper bound, so even an interesting formulation of your idea is not necessarily true: work need not be conserved at the least upper bound, because reaching the bound may not be possible and epsilon improvement might always be possible.

Finally, algorithmic complexity is the wrong analogy for reverse mathematics anyway.


Replies

zkmontoday at 9:37 AM

To give an example, we consider that binary search requires less work than a linear search. But there are costs and usecase considerations involved. Insertion of new recod need to use binary search to keep the data sorted. Also if the number of lookups is far less than number of records, the overall cost is more than appending and linear search. That's what I mean by by moving the complexity around.

A problem scenario doesn't have absolute characteristics. It's relative to your way of looking at it, and your definition of a problem.

show 1 reply