It's true though. Time complexity is a relative measure. Big-O notation is an upper bound, not a lower one. You don't take the fastest storage (L1 cache) as the baseline `x` and then say it takes some f(n) > x time to access storage because it's not in the fastest cache. This is a complete misrepresentation of Big-O notation.
When we say something is O(1), we're saying that there is a constant upper bound on time to compute the algorithm. It is constant time if it takes no longer to to perform the algorithm when `n` becomes large. O(1) simply means the worst case time to compute is independent of `n`. If the algorithm is accessing storages of varying latencies, then the baseline is the slowest medium.
For small `n` (ie, what might fit into cache), Big-O notation is not really that useful. When `n` is tiny a O(n) algorithm can outperform a O(1) algorithm. The notation doesn't tell us anything about how efficient a particular implementation is. It is mainly useful when we're talking about `n` which can grow to large sizes, where whatever micro-optimizations we, or the machine might perform are dominated by `n`.
This is quite wrong. If an algorithm requires one memory read, and reading one byte from memory takes (size of data)^1/3 time steps, then the complexity of that algorithm is O(N^1/3), not O(1).
This is well known for doing large number arithmetic. For example, we typically consider that a+a is an operation that takes O(1) time to execute. This is because we know we are limiting the analysis to small numbers, even if we have a lot of them. But if the numbers can be arbitrarily large, then a+a doesn't take O(1) time, it takes O(log a) time. So, an algorithm that needs to perform O(N) additions doesn't take O(N) time, it takes O(N log K) time. And if we are doing something like adding the first N numbers, the complexity is actually O(N log N), not O(N).
The same thing happens to memory: if we assume that the problem will fit into very fast memory even for the largest sizes, we can indeed approximate memory access as O(1). But if we admit that the more memory we need to store the components of the problem, the slower memory access will get, then we need to model the cost of accessing memory as a function of program size - and the author is proposing O(N^1/3) as that cost. This means that our algorithm for adding the first N numbers actually requires O(N^4/3) time for reading N numbers from memory and then O(N log N) additions, which gives it a total complexity of O(N^4/3 + N log N) = O(N^4/3).
Now, this type of analysis is not useful if we think all our numbers will fit into a single computer's memory, probably. But if we are trying to, say, figure out how our algorithm will scale from gigabytes of data to hundreds of petabytes of data, we need to model the rising cost of memory access as our data set gets bigger too. At some point as N grows to infinity, even just computing the address of the next byte becomes a complex operation that can take longer than the whole time it took to add the first 100GB of numbers.
Sure. And for any algorithm that needs to perform a read from memory, no such upper bound exists, this is the point.
For example, say we want to read the last number from an array. We get given the array index as an input, and we need to perform one memory read. You'd typically say that such an algorithm has a complexity of O(1).
However, if you actually write this algorithm and benchmark it for N=1, N=1MB, N=1GB, N=1TB, N=1PB and so on, you'll find that each of these is larger than the next. You'll also find that this number never stops growing. Accessing the last item in an array that is as large as a planet will take longer than accessing the last item in an array that is as large as a continent. So the actual complexity class is greater than O(1). Maybe O(n^1/3) is a good, maybe O(n^1/2) is better, maybe O(log n) would be best - whatever it is, it's not a constant.
That presumes you know all secrets ahead of time. A risk in and of itself. But from a practical point of view you will never know all secrets, because they are generated constantly in real time.
A recommendation is in the domain of subjectivity, meaning that there is no consensus on the correctness... so, even if the algorithm is faster, its usefulness shouldn't be superior to a random pick based on some matching criteria... which is already as fast as it can be
You're mixing up two things here. It doesn't really matter if the recommendation algorithm is good or not.
The advancement isn't that we now have a better recommendation algorithm, it's that we thought that there was a problem that was impossible to solve with current computers and was being used as example of a problem that only quantum computing could solve and we've now learned that that isn't the case.
It's a theoretical result. There was a problem believed to take exponential time on a classical computer but polynomial time on a quantum computer. It turns out to be solvable in polynomial time on both types of computer, removing the quantum exponential speedup. Whether one polynomial was bigger or smaller than the other wasn't of much interest, as I understand it. The surprise was just that both are polynomials.
The actual problem that is being solved here is well defined mathematically and is matrix completion via low rank matrix factorization. And using a sampling approach for it. (I have not read the paper in its entirety, just skimmed the intro a bit). It is called "recommendation system" largely due to some history around some of its common appplications (Netflix challenge). But this is not addressing the subjective recommendation problem, but a very particular instantiation of it.
Besides, "subjectivity" concerns the subject, "objectivity" the object. The former is a matter of how an object is received by the observer, and so all perception is subjective in that sense; it can't be otherwise. But the subject can become an object of another subject. We can infer with varying certainty what someone is more or less likely to enjoy based on our knowledge of what they like.
As long as you accept subjectivity, you must also accept that logical inference isn't really useful... because the observer can add rules at any given time - without any logical constraint - thus preferences aren't deterministic... so a random option is as good as it can be.
The application, method and algorithm needs to be separated. The application is movie recommendation. One of the methods which works pretty well for this is low rank matrix completion. There are several algorithms for this method, one of which is quantum.
"TFNP is the class of total function problems which can be solved in nondeterministic polynomial time", i.e. we don't consider decision problems (as for NP), but total functions.
This class contains quite some interesting subclasses, such as PLS (solution can be found via Local Search), PPA (solution exists because of a Parity Argument), PPP (solution exists because of a Pigeonhole Principle), PPAD (solution exists because of a Directed Parity Argument), CLS, ...
