= 27d567bc2d48d9f40e9ccc20ea370b15)
cousin_it 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)
...That's an interesting way to look at it. For example take the traveling salesman problem: it's traditionally converted to a decision problem by asking if there's a route cheaper than X. Note that only "yes" answers have to have quickly checkable certificates - this is NP, not NP intersected with co-NP. Now if we start asking if X is exactly the minimum instead, would that be equivalent in complexity? And would it be helpful, seeing as it takes away our ability to do binary search?
In short, I'm a little funny in the head right now, but still think my original claim was correct.
This paper (which I found via this Ph.D. thesis) says that for TSP, the question "Is the optimal value equal to k" is D^P-complete. It also says D^P contains both NP and coNP, so assuming NP!=coNP, that problem is not in NP.
Your original claim was "If computing the function is in P, minimization is in NP." Technically, this sentence doesn't make sense because minimization is a functional problem, whereas NP is a class of decision problems. But the ability to minimize a function certainly implies the ability to determine whether a value is a minimum, and since that problem is not in NP, I think your claim is wrong in spirit as well.
As Nesov pointed out, TSP is in FP^NP, so perhaps a restatement of your claim that is correct is "If computing the function takes polynomial time, then it can be minimized in polynomial time given an NP oracle." This still seems to imply that function minimization isn't much harder than NP-complete problems.
Are there any problems in PostBQP that can be said to be much harder than NP-complete problems? I guess you asked that already.
There was a dumb comment here, I deleted it. You're actually completely right, thanks!