41–50 of 74 posts
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.
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.
If P=NP there is a turing machine that always outputs a satisfying assignment if one exists with t being polynomial bounded by the input size. As this turing machine is constant, the algorithm runs in poly-time.
Earlier quoted context omitted.
But imagine he had said, "it's the number of dimensions your Fourier transform needs for the fastest way to multiply two numbers" :) BTW who things the other person was really just baiting Ramanujan to say something like this?
Hardy just saw it on a taxi cab and expressed sadness; Ramanujam pointed out the mathematical beauty of the number. The real question is, did he know of this fact already or did he come up with it on the spot after hearing what Hardy said?
n n³
-------
1 1
2 8
3 27
4 64
5 125
6 216
7 343
8 512
9 729
10 1000
11 1331
12 1728The 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.
Can you give a reference, or a hint on where to read more? This sounds really interesting, but Google has failed me.
In addition to galactic algorithms, there are also galactically proven algorithms. One example is the algorithm for matching with mismatches which I presented in the first chapter of my doctoral thesis; I proved that it was faster than other algorithms for inputs of at least ~10^30 bytes. In practice, it wins starting at around 10^4 bytes.
There aren't many non-trivial lower bounds out there, and I think they all use one of three ideas (diagonalization, crossing sequences or oracle reconstruction)!
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…
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…
Interesting, I don’t remember this proof (maybe I learned it, but it’s been a couple of years since university). Do you remember the “stop condition”? At some point the algorithm would have to “give up” and declare the problem unsatisfiable.
^ It would be funny though if P=NP, but for no turing machine exists a proof that it solves SAT. This would have to be ruled out for the algorithm to work.
I've never understood the "number of the atoms in the universe" argument. The number of states the universe can be in doesn't seem to be equal to the number of atoms. For example, just two atoms could encode lots of numbers simply by using their distance. Quantum physics would affect it, but I mean in principle: we are not switching atoms on and off to encode state.
I've never understood the "number of the atoms in the universe" argument. The number of states the universe can be in doesn't seem to be equal to the number of atoms. For example, just two atoms could encode lots of numbers simply by using their distance. Quantum physics would affect it, but I mean in principle: we are not switching atoms on and off to encode state.
It's just there for a reference, maybe a better one would be Kurzweil's ultimate laptop (made from the whole universe). But the interesting part is that I don't think the ultimate laptop takes into account interactions and state between atoms. AFAIR it assumes computation is done on every available dimension (like electron spin) but not on how atoms move and interact with each other. Intuitively it shouldn't make muc…