dreams of math and science

[gusl]

Apparently, my dreams are more visual than most people's. More mathematical as well.

Last week, I was thinking about model selection ideas, relating to the question of why Occam's Razor is useful. At my job, we do a search for production rules that explain a given problem-solving behavior. My dream had a person on a diagram, jumping from model to next-simplest model... reminescent of Levin search (incidentally, jcreed recently told me that one of the problems in Rudich's Complexity Theory class was to find a program that will compute a given NP-complete problem in P-time, *IF* it is the case that P=NP. The solution is to (1) write a P-time reduction of the problem to SAT, and (2) to write an algorithm that will solve SAT in P-time if that it at all possible (i.e. P=NP), by searching through all algorithms.).

Yesterday, shaktool and I were discussing why milk is white. My argument was that this meant that milk couldn't be a pure substance (I believe it is a suspension), since white solids always become colorless when you melt them.

So tonight I dreamed that I was explaining to my mom something about the solubility of salts, and I predicted that Hudson Bay, consisting of cold polar water, would have precipitated salt at the bottom. In order to check my prediction, we walked over to Hudson Bay, walked in the not-unpleasantly-cool water, and to my surprise, we found salt crystals *floating*. Most of them were 5-10cm long and diamond-shaped but snow-flakish in texture, and tended to form clusters on the water's surface.

Another association to explain this dream is that I was speaking to my aunt in Alberta yesterday.

Comments

[rdore.livejournal.com]

write an algorithm that will solve SAT in P-time if that it at all possible (i.e. P=NP), by searching through all algorithms.

Well, you do need to be careful about the simulation of all possible algorithms for this to work -- you need to dovetail in the right way, and you need to check your answers. (Neither is hard to do, but I think these are important details.)

[gustavolacerda.livejournal.com]

Yes, indeed. In fact, I'm not sure about the part where you check your answers: how do you know that the algorithm you found really solved SAT in P-time? Do you need to implement an algorithm analyzer? If not, do you need to restrict your search to only P-time algorithms? If so, how?

[rdore.livejournal.com]

Given an algorithm for deciding SAT, you can use it to actually find an assignment:

Take your formula phi(x₁,...x_n), and see if it is satisfiable.
If so, try phi(1,x₂,...x_n) and phi(0,x₂,...x_n) and assign x₁ to whichever one works. Then repeat with x₂, x₃, etc.

So now, if SAT in P, then there is a polytime program that finds the solution. So now run all the various possible machines for computing the assignment. When one finishes, check if it is an actual correct assignment.

For the dovetailing part, let's say your possible algorithms are A₁, A₂, ...

Then run as follows:
One step for A₁.
One step for A₁ and A₂.
One step for A₁, A₂, and A₃.
This way algorithm A_i will have have run k steps by the time the overall machine has run O(kⁱ) steps.

So if the correct algorithm is Algorithm A_j and it runs in time O(n^m) then the Algorithm will get the solution in time O(n^mj) which is polynomial since m and j are constants. Although j will probably be enormous.

[gustavolacerda.livejournal.com]

The problem is that, while your dovetailing algorithm decides SAT in P-time if P=NP, you won't know that P=NP, even when it has found the elusive P-time SAT algorithm.

So your algorithm runs in P-time due to the fact that P=NP, despite not having a proof of P=NP.


This way algorithm A_i will have have run k steps by the time the overall machine has run O(k^i) steps.

Are you sure? It seems to me that the number of steps would be proportional to k^2.

[rdore.livejournal.com]

Yes, all it does is give a polytime algorithm if one exists. It isn't even obvious that the algoroithm will always terminate if P != NP. It always does though, eventually.

My time calculation is off, it should be the time for k steps is O((k+i)²) and then the overall time is like (n+j)^2m, which I suppose is actually just O(n^2m) with horrible constant factors.

[bhudson.livejournal.com]

Milk is every chemistry teacher's first example of a colloid.

However, I'm completely unconvinced that whiteness is a proof of anything.