Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Galactic Algorithm

en.wikipedia.org

Post reply on HN
Print view View original

71–74 of 74 posts

Re: Galactic Algorithm

#71

Post by Retric »

nine_k wrote: post #69
Retric wrote: post #32

Earlier quoted context omitted.

It’s 2^1729 digits, (vastly) more digits than there are atoms in the universe. The vastly bit is kind of an understatement. Each stable isotope is indistinguishable from every other carbon isotope. So, you can probably encode a few bits per atom assuming you can somehow read this data. However they are talking vastly larger numbers of digits here. Where there are only ~10^80 digits worth of atoms in the visible unive…

You forgot about ordering. 8 binary bits in order can encode 256 states, as if every bit was capable of encoding 32 states.

Yea, that specific number fits into 2 kilobytes of memory, but it’s so large it’s hard to compare it to anything.

Which is why I suggest comparing it to the number of bits required to encode the universe. If all you wanted was to store a single arbitrary number and could read write the universe you could do anything out to 2^(10^(80 * k)) where k is larger than 1 but I suspect below 100.

Re: Galactic Algorithm

#72

Post by GuB-42 »

Gehinnn wrote: post #42
Gehinnn wrote: post #40

The godfather of a galatic algorithm is the known (!) algorithm that solves SAT in polytime. However, its runtime is only guaranteed to be in polytime, if someone guarantees that P = NP.

Before an unbeliever comments (as I would do myself if I wouldn't know the algorithm): This algorithm involves enumerating f(M, t) where M is the Gödel number of a turing machine T, t an integer and f the output of T after t steps on the original input. This output is interpreted as variable assignment. If it satisfies the formula, the SAT instance is satisfiable. Otherwise the enumeration continues. If P=NP there is…

So, in simpler terms (for me):

- start with a file size (let's say 4kb), and a duration (let's say 1 hour).

- generate all possible files of the given size (there are 2^32768 of them), mark them as executable and run them. If they don't finish after the given duration, kill them.

- check the output of each program that didn't crash. If one matches the solution, OK. If it doesn't, try again with a longer duration and larger size.

It doesn't just solve SAT. At galactic scales, it will either be the optimal solution to any problem, or be as fast as checking the answer, whatever is slower. If all that code generation thing doesn't depend on the input size, it is constant time. That the constant is many times the age of the universe doesn't change the complexity class.

Re: Galactic Algorithm

#73

Post by Gehinnn »

GuB-42 wrote: post #72
Gehinnn wrote: post #42

Earlier quoted context omitted.

Before an unbeliever comments (as I would do myself if I wouldn't know the algorithm): This algorithm involves enumerating f(M, t) where M is the Gödel number of a turing machine T, t an integer and f the output of T after t steps on the original input. This output is interpreted as variable assignment. If it satisfies the formula, the SAT instance is satisfiable. Otherwise the enumeration continues. If P=NP there is…

So, in simpler terms (for me): - start with a file size (let's say 4kb), and a duration (let's say 1 hour). - generate all possible files of the given size (there are 2^32768 of them), mark them as executable and run them. If they don't finish after the given duration, kill them. - check the output of each program that didn't crash. If one matches the solution, OK. If it doesn't, try again with a longer duration and…

Yeah, you got the point ;) This however only works for problems where you can validate a solution in polynomial time. There is still the problem what happens when a solution does not exist. Even in this case, the algorithm must terminate in polynomial time.
Post reply on HN