= 27d567bc2d48d9f40e9ccc20ea370b15)
Vladimir_Nesov comments on Quantum Russian Roulette - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (55)
It's in FP^NP, not in NP. Only the decision problem for whether a given value C is more than the minimum is in NP, not minimization itself.
Yes, that's certainly right, thanks. I was careless in assuming that people would just mentally convert everything to decision problems, like I do :-)
ETA: Vladimir, I couldn't find any proof that NP is strictly contained in PP; is it known? Our thread seems to depend on that question only. It should be true because PP is so freaky powerful, but nothing's turned up yet.
P⊆NP⊆PP⊆PSPACE, but we don't even have a proof of P≠PSPACE.
Unconditionally proven strict containments are pretty rare. You'll probably want to settle for some lesser evidence.
Hah. Thanks, that settles the issue for now: short of Scott Aaronson making an unexpected breakthrough, we have no proof that quantum suicide computing can solve any non-polynomial problems :-)
On the computational power of PP and ⊕P says it gives strong evidence that PP is strictly harder than PH, which contains NP.
According to this FNP is strictly harder than NP.
No idea about PP. Where did PP come up, or how does it relate to FNP?
ETA: Ah, I see. Aaronson's paper here shows that postselection (which is what our suicide voodoo is) gives you PP. Since postselection also gives you FNP, and since FNP is harder than NP, then we should have that PP is strictly harder than NP.
Jordan, I'm really sorry to inject unneeded rigor into the discussion again, but the statement "FNP is strictly harder than NP" doesn't work. It makes sense to talk about P=NP because P and NP are both sets of decision problems, but FNP is a set of function problems, so to compare it with NP you have to provide a mapping of some sort. Thus your argument doesn't prove that PP>NP yet.
For me personally, function problems are exotic beasts and I'd prefer to settle the power of quantum voodoo on decision problems first :-)
There's a natural partial mapping in my mind, but a rigorous mapping is beyond me. Check out this. Apparently it can be shown that FNP is strictly harder than NP, under certain conditions. I didn't understand the condition, and whether it was reasonable or not.
Regardless of all this complexity jazz, which has definitely exceeded my grasp, my random dictionary example still demonstrates that certain problems can be solved exponentially faster with postselection than without, even if it doesn't prove that FNP > NP.
ETA: Coming from a numerics background, decision problems seem like exotic beasts. I'd prefer to settle the power of quantum voodoo on function problems first =P