4 ms·
How is it measured? A lookup table takes 1 step to find the answer of a multiplication.
by charcircuit 3mo ago
How is it measured? A lookup table takes 1 step to find the answer of a multiplication.
- blovescoffee 3mo agobecause you're looking up a result not solving for it
- charcircuit 3mo agoYou solve it by looking it up.
- bmacho 3mo agoThis would be the solution for any problem/algorithm, wouldn't it? Factorize big numbers, sort an array, beat stockfish at chess, create a SOTA microkernel OS from English description. All O(1) with lookup table! It's not how complexity works.
- charcircuit 3mo ago>This would be the solution for any problem/algorithm, wouldn't it? Yes, but it suffers from a large amount of space complexity, and probably would have high constant factors in practice.
- bmacho 3mo agoExactly. So what I wrote debunks your assumptions and proves your argument wrong. This is how conversations normally go.
- charcircuit 3mo agoWhat you wrote agreed with me. >All O(1) with lookup table!
- boomlinde 3mo agoUsing e.g. a single zettabit-sized look-up table to give the 64-bit result of a multiplication of two 32-bit numbers suffers from a similar problem. But if we're talking about practical concerns there are already faster methods than random access in >100 exabytes of memory. And if we're talking theoretical concerns your answer still hasn't addressed the question of how to multiply numbers fast.
- hcs 3mo agoAn algorithm is a finite sequence of instructions, and so can't include an infinite table. More generally, https://en.wikipedia.org/wiki/Effective_method https://en.wikipedia.org/wiki/Effective_method
- charcircuit 3mo agoI disagree. 1 step is a finite sequence of instructions.
- SkiFire13 3mo agoThe lookup table is part of the algorithm, and is not finite. In general any problem can be solved in 1 step with a lookup table, so here you go P=NP solved.
- charcircuit 3mo agoIt doesn't have to be part of the algorithm. It all depends on how you measure it.
- hcs 3mo agoWell, yes, which is why they don't measure it your way, as it doesn't lead to discovering anything interesting about computation to have a shortcut like that. Or if they do it's part of a larger analysis, called an oracle machine.
- charcircuit 3mo agoI am against statements like: A: "X people don't know how to do Y" B: "Why not do Z?" A: "Z is too easy and boring so they actually added more restrictions to how you are allowed to do Y so that solution doesn't count"
- hcs 3mo ago
- less_less 3mo agoThe model usually measures in terms of fixed-size operations, e.g. 2-input binary gates. There's some variation in how to count memory lookups, but even in models where accessing a large memory counts as only one step, any tables present in the code still have to be fixed-size (except in models like P/poly, but even then they can't be exponential size).