But normally, problems eventually found to be in P are first found to be in BPP (primality testing being the most prominent example). Shouldn't there at least be some probabilistic factoring algorithms (whatever that would mean)?
This is an example where moving between a decision problem (returning a yes or no answer) and a function problem (returning a number or list of numbers) may break down. To make factoring equivalent to a decision problem one instead asks the question "Given n, and given a and b, is there are prime factor of n which is between a and b?" If one has a factorization of n one can answer this question quickly. If one has an oracle that can answer this question then one can factor in polynomial time by using a binary search tree of the intervals under n. This allows one to iterate calls to the oracle to find a prime factor in log_2 n time. Each time you find a prime factor p, you store it and then do the same process for n/p. This takes at most (log2 n) times the number of prime factors of n. In general, if calls to your oracle take time f(n), the whole thing takes at most f(n) (log2 n)^2 time. (You can actually do slightly better than that but this is good enough for pretty much all purposes.)
What I'm not sure about is whether the equivalent problem in BPP goes through. Say one has an oracle that answers the interval question with a BPP-like answer. Is there some way to turn that into a process that returns the correct factorization quickly with high probability? That's not obvious to me. I haven't really thought about the question that hard.
Also, in the likely event that P != NP, that would imply the existence of NP-intermediate problems, and factoring is a good candidate for being in such a class.
Right. That and and graph isomorphism seem to be the two most common natural problems that are potentially in that intermediate class.
Personally, my hunch is that factoring is indeed in P, but I'm far from qualified to have a lot of confidence in that.
I think you'd be in an extreme minority here. Even people like Henry who think that the evidence for factoring not being in P is small don't seem to think it is actually in P. If I had to make a guess on the chance that factoring is in P, I'd probably put it at under 20%.
Right. That and and graph isomorphism seem to be the two most common natural problems that are potentially in that intermediate class.
Yes, but I thought there's much higher confidence that graph isomorphism will be de-randomized, given how hard it is to even find problem instances that are unresolved after a few simple checks (e.g. of invariants of the adjacency matrices).
Let P(chr) = the probability that the statements attributed to Jesus of Nazareth and Paul of Tarsus regarding salvation and the afterlife are factually mostly correct; and let U(C) be the utility of action C, where C is in {Christianity, Islam, Judaism, atheism}.
Two of the key criticisms of Pascal's wager are that
If, however, P(chr) is not infinitessimal, and U(Christianity) is merely very large, these counter-arguments fail.
Many poor arguments have been made that P(chr) > .1. But as far as I know, no one has ever made the best argument in favor of Christianity:
If you accept the simulation argument, then P(sim) > .99.
If you look at the fraction of computing power used for entertainment, I don't know what it is, but the top 100 supercomputer list for June 2011 lists a total of 4,531,940 cores in the top 100 supercomputers in the world; versus (rough guess) a billion personal computers and video game consoles, and a similar number of ordinary computers used at work. It would be reasonable to set p(ent|sim) = .5.
If you set P(ego|ent, sim) according to the fraction of entertainment simulations in which the person playing the game has an avatar in the game, then P(ego|ent, sim) is large. I originally set this at p > .99, but am now setting it to p = .5 in response to Jack's comment below.
We notice there are no obviously immortal world leaders on Earth (but see vi21maobk9vp's comment below). If we therefore limit the possible avatars that our simulator God is using on Earth to the major monotheistic religions of Christianity, Islam, and Judaism, and consider them all equiprobable; plus a 25% chance that this God is jumping from one avatar to another, or chose to reveal Himself via Jesus but then Paul screwed everything up, or some other minority position; then p(chr0|ego, ent, sim, Earth) = .25.
P(follow-thru) is difficult to estimate; I will set it somewhat arbitrarily as .1. Given our observations of game-players here on Earth, it is not independent of p(ego), as players of self-glorifying games are likely to be young adolescent males, and so are people who enjoy burning insects with magnifying glasses.
We now have p(chr) > .99 x .5 x .5 x .25 x .1 = .0061875. As stipulated, your afterlife accounts for at least 99% of your utility if follow-thru (and hence chr) is true. If we suppose that the length of time for which God rewards us in Heaven or torments us in Hell has an exponential distribution, and we are considering only the part of that distribution where >= 99% of your utility is in the afterlife, then almost certainly p(chr) * U(Christianity | chr) > (1-p(chr)) * U(atheism | not(chr)). It now appears we should accept Pascal's wager.
(The expected utilities for Christianity and Islam are similar, and this argument gives no reason for favoring one over the other. That is of only minor interest to me unless I accept the wager. The important point is that they both will have expected utilities similar to, and possibly exceeding, that of atheism.)
You can argue with any of the individual numbers above. But you would have to make pretty big changes to make p(chr)(U(Christianity|chr)) negligible in your utility calculation.
(IMHO, voting this article up should indicate it passed the threshold, "That's an interesting observation that contributes to the discussion", not, "Omigod you're right, I am going out to get baptized RIGHT NOW!".)