Hacker News new | ask | show | jobs
by charcircuit 13 days ago
I disagree. 1 step is a finite sequence of instructions.
1 comments

The 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.

It doesn't have to be part of the algorithm. It all depends on how you measure it.
Well, 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.
I 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"

Maybe I'm not communicating the point clearly. In order to use a table to do the whole multiplication it has to be much larger than the largest number you would want to multiply with it. A lot of the analysis of algorithms, especially multiplication as discussed here, is about astronomically large numbers, so you don't want the existence of an even more astronomically large table as a prerequisite.
We are talking about mathematicians. We are not talking about computer engineers trying to implement a physical GPU that can multiply matrices as fast as possible. You don't have to physically build the astronomically look up table by hand. One can simply state that it exists. Proofs do not have to be clean to be a proof. You might not "want" something in a proof, but if it works then it works.
Yup, and everyone measures it to be part of the algorithm, otherwise you start getting nonsensical results.