upvote

points

by charcircuit2 days ago |
comments
upvoteby hcs1 days ago|
next
[-]
An algorithm is a finite sequence of instructions, and so can't include an infinite table. More generally, https://en.wikipedia.org/wiki/Effective_method
reply
upvoteby charcircuit1 days ago|
parent|
[-]
I disagree. 1 step is a finite sequence of instructions.
reply
upvoteby SkiFire131 days ago|
parent|
[-]
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.

reply
upvoteby charcircuit1 days ago|
parent|
[-]
It doesn't have to be part of the algorithm. It all depends on how you measure it.
reply
upvoteby hcs1 days ago|
parent|
next
[-]
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.
reply
upvoteby charcircuit1 days ago|
parent|
[-]
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"

reply
upvoteby hcs1 days ago|
parent|
[-]
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.
reply
upvoteby charcircuit1 days ago|
parent|
[-]
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.
reply
upvoteby SkiFire131 days ago|
parent|
next
[-]
What you are stating is simply that any algorithm whose inputs are bounded can be solved in O(1) time with a lookup table. That's known and obvious, which makes it not interesting.

Moreover it only works with bounded inputs. If your input is unbounded (as is this case with multiplication over arbitrarily large numbers) then an infinitely big lookup table is just not possible because it's part of the algorithm and hence needs to be finite.

If infinitely-big lookup tables were allowed you could for example write an algorithm that solves the halting problem, just index into the lookup table for its solution. And actually you could do this for any problem! So any problem, even so called "non computable" ones, admit a solution that runs in time linear to their input. I hope you see that this is nonsensical and it's why lookup tables are considered part of the algorithm and hence need to be finite.

> You might not "want" something in a proof, but if it works then it works.

And at the same time you don't get to change the definition of algorithm to allow your "proof" to be valid, otherwise you're just talking about nonsense.

reply
upvoteby charcircuit1 days ago|
parent|
[-]
>And at the same time you don't get to change the definition of algorithm to allow your "proof" to be valid

It is other people who are trying to attack my statement who are trying to apply words like "algorithm" to it. You have such a fixed view of how things operate that you are failing to be able to take a step back and accept the existence of being able to solve any problem in a single step. You can claim that it is obvious, and trivial, and uninteresting, but that doesn't invalidate it. Sometimes thinking outside of the box is required and such strict adherence to what has come before can cloud your view of an "obvious" solution that was there the whole time.

reply
upvoteby SkiFire131 days ago|
parent|
[-]
> You can claim that it is obvious, and trivial, and uninteresting, but that doesn't invalidate it. Sometimes thinking outside of the box is required and such strict adherence to what has come before can cloud your view of an "obvious" solution that was there the whole time.

Then sure, go ahead. Define your own model of computation, one not based on turing machines and which somehow allows for infinitely big lookup tables, and then see what great insight it provides you.

I wonder discoveries you will be able to make in a system where you can say that the solution of a problem is just its solution.

reply
upvoteby lll-o-lll1 days ago|
parent|
prev|
[-]
Cool. I will assert a magic 8 ball that gives the correct answer. Are we done?
reply
upvoteby SkiFire131 days ago|
parent|
prev|
[-]
Yup, and everyone measures it to be part of the algorithm, otherwise you start getting nonsensical results.
reply
upvoteby bmacho2 days ago|
prev|
next
[-]
This 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.

reply
upvoteby charcircuit1 days ago|
parent|
[-]
>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.

reply
upvoteby boomlinde1 days ago|
parent|
next
[-]
Using 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.
reply
upvoteby bmacho1 days ago|
parent|
prev|
[-]
Exactly.

So what I wrote debunks your assumptions and proves your argument wrong.

This is how conversations normally go.

reply
upvoteby charcircuit1 days ago|
parent|
[-]
What you wrote agreed with me.

>All O(1) with lookup table!

reply
upvoteby less_less1 days ago|
prev|
next
[-]
The 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).
reply
upvoteby blovescoffee2 days ago|
prev|
[-]
because you're looking up a result not solving for it
reply
upvoteby charcircuit2 days ago|
parent|
[-]
You solve it by looking it up.
reply