Sorry, you misunderstood my point. Perhaps I’m being a little pedantic and unclear.
For the cities example, the point is that when the problem domain is restricted to a single example (the top 100 cities in the US), there is some program out there that outputs the list of cities in the correct order.
You can imagine the set of all possible programs, similar to The Library of Babel—Wikipedia. Within that set, there are programs that print the 100 cities in every possible order. One of them is the correct answer. I don’t need to know which program that is to know that it exists.
This is why the OP’s suggestion to define “fundamental units of computation” doesn’t really make sense, and why the standard tools of computational complexity theory are (as far as I know) the only reasonable approach.
If that’s what you meant, it is rather unclear in the initial comment. It is, in fact, very important that we do not know what the sequence is. You could see it as the computation is to determine which book in the library of Babel to look at. There is only one correct book [though some are close enough], and we have to find that one [thus, it is a search problem.] How difficult this search is, is actually a well defined problem, but it simply has multiple ways of being done [for instance, by a specialist algorithm, or a general one.]
Of course, I do agree that a lookup table can make some problems trivial, but that doesn’t work for this sort of thing [and a lookup table of literally everything is basically is what the Library of Babel would be.] Pure dumb search doesn’t work that well, especially when the table is infinite.
Edit: You can consider finding it randomly the upper bound on computational difficulty, but lowering bound requires an actual algorithm [or at least a good description of the kind of thing it is], not just the fact that there is an algorithm. The Library of Babel proves very little in this regard. (Note: I had to edit my edit due to writing something incorrect.)
Sorry, you misunderstood my point. Perhaps I’m being a little pedantic and unclear.
For the cities example, the point is that when the problem domain is restricted to a single example (the top 100 cities in the US), there is some program out there that outputs the list of cities in the correct order.
You can imagine the set of all possible programs, similar to The Library of Babel—Wikipedia. Within that set, there are programs that print the 100 cities in every possible order. One of them is the correct answer. I don’t need to know which program that is to know that it exists.
This is why the OP’s suggestion to define “fundamental units of computation” doesn’t really make sense, and why the standard tools of computational complexity theory are (as far as I know) the only reasonable approach.
If that’s what you meant, it is rather unclear in the initial comment. It is, in fact, very important that we do not know what the sequence is. You could see it as the computation is to determine which book in the library of Babel to look at. There is only one correct book [though some are close enough], and we have to find that one [thus, it is a search problem.] How difficult this search is, is actually a well defined problem, but it simply has multiple ways of being done [for instance, by a specialist algorithm, or a general one.]
Of course, I do agree that a lookup table can make some problems trivial, but that doesn’t work for this sort of thing [and a lookup table of literally everything is basically is what the Library of Babel would be.] Pure dumb search doesn’t work that well, especially when the table is infinite.
Edit: You can consider finding it randomly the upper bound on computational difficulty, but lowering bound requires an actual algorithm [or at least a good description of the kind of thing it is], not just the fact that there is an algorithm. The Library of Babel proves very little in this regard. (Note: I had to edit my edit due to writing something incorrect.)