Relativizations Of The P Np Question

[Raymond Freedman]

Iam afraid this post may show my naivety. At a recent conference, someone told me that there are some arguments in computability theory that don't relativize. Unfortunately, this person (who I think may be an MO regular) couldn't give me any examples off-hand.

My naive understanding is that one can take any proof, fix an oracle and replace "Turing machine" with "Turing machine using that oracle". (Similarly, replace "computable" with "computable w.r.t. this oracle" and so on.) But I am probably missing something.

Actually, while writing this, I may have come up with an example. It's known that $P=NP$ and $P \neq NP$ for different oracles. But this is a relativization of a theorem (conjecture), not it's proof. So this brings up related questions. Is relativizing the statement of a theorem different from relativizing the proof? What if the theorem/proof has nothing to do with the actual model of computation (e.g. the proof doesn't refer to ideas such as time-complexity, only computability)?

Early in the history of recursion theory, the realization that all known proofs in the subject could be relativized in the manner you indicate led Hartley Rogers to make what is called the homogeneity conjecture.

All that being said, just about every proof in recursion theory that I know of relativizes. I'd be very interested in a proof which doesn't relativize and doesn't factor through the coding machinery I've mentioned above.

By the way (and somewhat ironically), the Baker-Gill-Solovay theorem that you mentioned does itself relativize. The relativized version says that for any oracle $X$, there are oracles $A$ and $B$ so that $X$ is poly-time reducible to both $A$ and $B$, and $P^A = NP^A$ and $P^B \neq NP^B$. (We've relativized to $X$ here. The unrelativized result simply says that there are oracles $A$ and $B$ so that $P^A = NP^A$ and $P^B \neq NP^B$). Of course, the real point is that a proof that $P \neq NP$ can't use a technique that relativizes.

So I was faced with a dilemma: do I look up, at the distinguished people from the US, Canada, Japan, and elsewhere winning medals in Israel, or down at my phone, at the bombshell paper by two Israelis now living in the US?

I suppose that for sampling problems (Quantum Sampling, or BosonSampling, or even samling distribution described by bounded depth quantum circuits) it is known that if those belongs to PH then PH collapses. Should we regard the new result as a support that BQP is going beyond PH just like those quantum sampling tasks (and thus perhaps BQP already capture the full supremacy power of QC) or perhaps would the new result of Raz and Tal may lead to stronger results also about hardness for quantum sampling problems?

On a related matter I vaguely remember that we discussed the conjecture that if a classical computer with BQP oracle can perform quantum sampling then PH collapses. (Perhaps this is even a theorem by now?) What is the status of this statement in view of the the evidence of beyond-PH-hardness for BQP itself.

I suppose that for sampling problems (Quantum Sampling, or BosonSampling, or even sampling distribution described by bounded depth quantum circuits) it is known that if those belongs to PH then PH collapses. Should we regard the new result as a support that BQP is going beyond PH just like those quantum sampling tasks or would the new result of Raz and Tal may lead to stronger results also about hardness for quantum sampling problems?

On a related matter I vaguely remember that we discussed the conjecture that if a classical computer with BQP oracle can perform quantum sampling then PH collapses. (Perhaps this is even a theorem by now?) What is the relation of such a statement in view of the the evidence of beyond-PH-hardness for BQP itself?

Two questions: First, where does this put us in terms of whether BQP is outside PH relative to a random oracle? Obviously, this would be a strictly stronger claim than there being at least one such oracle; is there any plausible hope that these methods can work to place BQP outside PH relative to a random oracle?

Even more to the point: if you could do exponential number of classical computations in parallel, and then combine the results using any formula of polynomial depth, the class of problems that you could solve would be PSPACE, which is larger than PH and which has long been known to contain BQP.

And then, given these instances, you could certainly experiment with various algorithms to solve them. If you had a quantum computer (able to query the truth tables of f and g stored in a memory somewhere), you could even run the quantum algorithm for noisy Forrelation, and see that it gave you the expected result.

For example, if it can be implemented using a non-universal quantum gate set, then you might have a separation between PH and wanna-BQP, the class containing all not-quite-quantum simulators that do ok with non-universal gate sets like H+CNOT.

Hi Scott, one follow-up question. We know that if classical computers can perform exact quantum sampling then PH collapses, and there are various conjectures regarding the harness of approximate sampling (in increasing difficulty) 1) that this applies to approximate quantum sampling, 2) that this applies to approximate Boson SAmpling, 3) that this applies to approximate BosonSAmpling for Gaussian matrices. Does the new oracle results for decision imply or gibe hope for oracle results (rather than full results) in the direction of 1) 2) and 3).

Best, Gil

A relativization or standardization is a transformation that is affected by other elements in the matrix. Another way to think of this is that the action taken on an individual element would be different if you consider it alone or as part of a set of elements.

Relativizations can be applied to rows (sample units), columns (variables), or both. For example, relativizing a data frame by columns will mean that each element within a given column is adjusted based on the values of other elements in that same column.

The relativizations described below are often based on a single variable, but another approach is to relativize on the basis of another variable. For example, in wildlife studies abundance is commonly divided by sampling effort to account for differences in sampling effort (Hopkins & Kennedy 2004). This was also evident in the medical trial reported below, where the number of cases was expressed per 10,000 women.

Analyses based on absolute values and on relative values address different questions. Imagine a study in which you capture and count the animals in an area. What hypotheses might be tested if you analyze the number of raccoons captured (an absolute value)? What about if you analyze the proportion of all animals captured that were raccoons (a relative value)?

Grace (1995) provides an example of how a dataset can be used to answer one set of questions based on absolute values and another set of questions based on relative values (see Freckleton et al. (2009) for more of this conversation). And, Fox (2013) provides some nice examples of the difference between absolute and relative fitness.

Knowing the direction and magnitude of an absolute effect does not necessarily tell you the direction and magnitude of a corresponding relative effect. It is possible for them to respond similarly, or for one to be positive and the other to be neutral or negative.

After normalization, the values for a variable are expressed in units of how many standard deviations they are from the mean (negative if below the mean, positive if above the mean). As a result, this relativization can permit equitable comparisons among variables even if they were measured in very different units.

This is commonly applied to columns of normally-distributed data. This relativization is generally not applied to species abundances but is very reasonable for other response variables and for some explanatory variables.

Set maximum value to 1 and calculate all other elements as a proportion between 0 and 1. This is commonly applied to the columns (species) of a species abundance matrix or to other variables where zero is a reasonable expectation for a minimum value.

When applied to species abundance data, this allows species to contribute equally to differences between plots. Assuming that two species were absent from some plots, and thus have zero as their minimum, their relativized values will span the same range even if they differed greatly in abundance.

This relativization is similar to relativizing by maxima but is useful for variables that do not have zero as the expected minimum value. For example, it would be more appropriate to relativize the latitude of each plot (Oak$LatAppx or Oak_explan$LatAppx) by range than by maxima. Do you see why this is the case? Try calculating and comparing the two approaches!

This is commonly applied to the rows (sample units) of a species abundance matrix. The resulting data equalizes the contribution of plots: the relativized data sum to 1 for every plot regardless of how much plots differed in total abundance. Note that it only makes sense to apply this to a set of values where the sum of those values is meaningful.

Sometimes it makes sense to apply this to a subset of the variables. For example, if the explanatory variables include depths of different soil horizons, you could relativize each horizon as a proportion of the total soil depth.

McCune & Grace (2002, p.70) note that the degree of variability in row or column totals can be used to assess whether relativization will have much of an effect. They are referring here to data that have been measured in the same units for all variables (columns) in all sample units (rows). In other words, it needs to make sense to compare row or column totals.

McCune & Grace express the degree of variability by the coefficient of variation (CV) of the row or column totals. The CV is the ratio of the standard deviation of a variable to its mean, multiplied by 100 to express it as a percentage. They propose the following benchmarks:

3a8082e126