26
You can just take the oracle A s.t. NP$^A$=EXP$^A$ since EXP is not in i.o.-subexp. For SAT$^A$ it depends on the encoding, for example if the only valid SAT instances have even length then it is easy to solve SAT on odd-length strings. But if you use a language like $L=\{\phi 01^*\ |\ \phi\in SAT^A\}$ then you should be fine.
20
The oracle is basically just an implementation of the predicate you want to search for a satisfying solution to.
For example, suppose you have a 3-sat problem:
(¬x1 ∨ ¬x3 ∨ ¬x4) ∧
(x2 ∨ x3 ∨ ¬x4) ∧
(x1 ∨ ¬x2 ∨ x4) ∧
(x1 ∨ x3 ∨ x4) ∧
(¬x1 ∨ x2 ∨ ¬x3)
Or, in table form with each row being a 3-clause, x meaning "this variable false", o ...
16
You don't have to go to the lengths Lance was suggesting. For
example, relative to a random oracle, using the oracle as a one-way function
(say, evaluated on consecutive bit postions)
is exponentially hard to invert on all but finitely many lengths.
This problem directly reduces to SAT on the same length input, so it does
follow that SAT^A is not in ...
16
Yes.
First, since it took me a minute to figure this out myself, let me formalize the difference between your question and $\mathsf{AlmostP}$; it's the order of quantifiers. $\mathsf{AlmostP} := \{L : Pr_R(L \in \mathsf{P}^R) = 1\}$, and the result you allude to is $\forall L\, L \in \mathsf{BPP} \iff Pr_R(L \in \mathsf{P}^R) = 1$. If I've understood ...
14
I don't know a reference, but I think both of these should be doable.
For your first oracle: for starters you'll want an oracle (call it $A_1$) that encodes exponentially-large $MAJORITY$ instances, and that thereby separates both $P^{A_1}$ and $NP^{A_1}$ from $PP^{A_1}$. Then you want a second oracle (call it $A_2$) that encodes the solutions to all $PH^{...
13
I had a vague recollection that I knew an excellent reference for such oracle separations. I finally found it.
A great reference for oracle separations (for classes between P and PSPACE) is the following paper:
Vereshchagin, N K (1994), "RELATIVIZABLE AND NONRELATIVIZABLE THEOREMS IN THE POLYNOMIAL THEORY OF ALGORITHMS", Russian Academy of Sciences. ...
13
Yes. Indeed, an oracle $A$ satisfies $\mathsf{NP}^A=\mathsf{NP}$ if and only if $A \in \mathsf{NP} \cap \mathsf{coNP}$. This class is called $\mathsf{Low(NP)}$ or sometimes $\mathsf{L_1 P}$ (see the link and the paper cited there for more of an explanation of the low hierarchy in general).
Your intuition about "determinism" is actually somewhat correct (...
13
You are exactly right. The relativization operation $B\mapsto B^A$ is not well defined.
P and PA are independently defined objects. The names are suggestive, but you cannot formally define PA from the set P. (You can define P from PA by setting A to be the empty set.)
Think of PA as being some kind of generalization of P, which equals P when A is empty, ...
12
For question 1, the BGS construction can be performed in exponential time, so you can construct such $B \in \mathsf{EXP}$.
(For question 2: Sasho Nikolov's answer was originally only for $\mathsf{\Sigma_k P}$-complete languages, and I pointed out that one can also take any $B' \in \mathsf{NP} \cap \mathsf{coNP}$, since $\mathsf{NP}^{\mathsf{NP} \cap \mathsf{...
11
Because one of the principal applications of Type Theory in formalizations has been to study programing languages and computation in general, a lot of thought has gone into ways of representing possibly non-terminating programs.
I won't make a complete survey here, but I'll try and give pointers to the main thrusts of different directions.
The "relational" ...
11
For question 2, you can take any $B' \in \mathsf{PH}$ (this means you cannot bring down the $B$ in the BGS result down from $\mathsf{EXP}$ to $\mathsf{PH}$ without resolving the big question).
Clearly for any $B'$, $P \subseteq \mathsf{P}^{B'} \subseteq \mathsf{NP}^{B'}$. Let $B' \in \Sigma_i^{\mathsf{P}}$. Recall that, by the definition of the Polynomial ...
11
This version of the answer incorporates feedback from Emil Jeřábek.
As far as I can see, the main twist is that there is a language in $\mathsf{EXP}^{\Sigma^\mathsf{P}_2}$ of exponential circuit complexity. In particular, fix a binary encoding of boolean circuits and define $L$ as the language defined by
$L_n$ is not decided by any circuit of size $2^{n/...
10
First, this result is listed in the complexity zoo: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N#npiconp. Alternatively, it's possible to prove without much trouble (which I do below).
We want to show that $P^{NP \cap coNP} = NP \cap coNP$. Clearly, one direction is obviously true: $NP \cap coNP \subseteq P^{NP \cap coNP}$. To prove the other ...
9
In the first bullet, we would need the oracle to answer
YES, if Arthur’s check succeeds with probability $1$ (assuming the MA protocol has perfect completeness),
NO, if Arthur’s check succeeds with probability $\le 1/2$.
This sounds like a coRP algorithm, but the catch is that there is no guarantee that one of these two conditions applies for every ...
9
Elaborating on Joe's earlier answer: note that $\textrm{FACTORING} \in \mathsf{NP \cap coNP}$. The latter is the second lowest class in the "low" hierarchy: which is to say that $\mathsf{NP^{NP \cap coNP} = NP}$. This implies in particular that $$\mathsf{P^{\textrm{FACTORING}} \subseteq NP^{\textrm{FACTORING}}} \subseteq \mathsf{NP}.$$
We may make similar ...
9
I believe if you trace through the argument given, e.g., in Section 4.1 of Ker-I Ko's survey, you get an upper bound of $\mathsf{DTIME}(2^{2^{O(n^2)}})$. In fact, we can replace $n^2$ here with any function $nf(n)$ where $f(n) \to \infty$ as $n \to \infty$. This isn't quite what was asked for, but it's close.
In particular, using the translation between ...
8
It seems your upper bound can be improved as follows: On input $x$ of length $n$, let $y_1,\dots,y_m$ be the oracle queries. Note that $|y_1|+\dots+|y_m| \leq c_1n^a$. The time to simulate the oracle machine to answer query $y_i$ is $c_2|y_i|^b$. Note now that $c_2(|y_1|^b+\dots+|y_m|^b) \leq c_2 (|y_1|+\dots+|y_m|)^b \leq c_2(c_1n^a)b = c_1c_2n^{ab}$. Thus ...
answered Nov 27 '12 at 9:59
Kristoffer Arnsfelt Hansen
3,9052 gold badges22 silver badges34 bronze badges
8
A definition of oracle access that works for small circuit complexity classes (the $AC^k$ and $NC^k$ hierarchies) as well as for logarithmic space classes, with the property that all known inclusions relativize, can be found in this paper:
Klaus Aehlig, Stephen Cook and Phuong Nguyen: Relativizing Small Complexity Classes and their Theories, CSL 2007, ...
8
The complexity zoo is your friend! As Robin said, you have half the answer: any EXP-complete problem collapses NP to P, and therefore BPP to P. Buhrman and Fortnow constructed an oracle relative to which P = RP but BPP is not equal to P. This is more than what you asked for; I suspect there are easier constructions that separate P from both RP and BPP.
8
Yes. Beigel CCC '89 showed $\mathsf{P} \neq \mathsf{UP} \neq \mathsf{NP}$ with probability 1. Combined with Rossman-Servedio-Tan, this gives the result you want. You should always try the Complexity Zoo for questions like this...
7
While the order of quantifiers between what you are asking and almost P differ,
it is not too hard to show that they are equivalent. First, for any fixed L,
the question of whether L \in P^O does not depend on any finite initial segment
of O. it follows that the probability that L \in P^R is either 0 or 1. From
the almost -P result, for each computable ...
7
$\mathsf{UP} \neq \mathsf{EXP}$ is open. A UP-generic oracle* should make $\mathsf{P} \neq \mathsf{UP} = \mathsf{EXP}$, and since $\mathsf{UP} \subseteq \mathsf{\oplus P} \subseteq \mathsf{EXP}$ relative to any oracle, this should resolve 1. (I say "should" because I haven't checked all the details...)
*UP-generic oracles are discussed, for example, by ...
7
The quoted Beigel, Buhrman, and Fortnow paper gives a solution to 2 in Theorem 1.8: there is an oracle relative to which $\mathrm{P=Mod_3P}$ (which implies $\mathrm{P=UP}$), and $\mathrm{\oplus P=NP=EXP}$ (which, together with the first equality, actually implies $\mathrm{EXP=ZPP}$).
7
$\mathsf{MA_{EXP}} \not\subseteq \mathsf{P/poly}$ but there is an oracle relative to which this is false; both were proved in
H. Buhrman, L. Fortnow, T. Thierauf. Nonrelativizing separations. CCC '98. (freely available author's version)
7
I think you may be misunderstanding the sentence "Note that the general notion of a reduction (i.e., Cook-reduction) seems inherent." This is not about reductions being inherent to self-reducibility (in the sense Goldreich uses it), but rather about Cook reductions being inherent to this notion, in the sense that they cannot be replaced by Karp reductions. ...
6
A nice description of an oracle that separates P and BPP is given by Greg Kuperberg in one of the comments of this interesting blog post, where Terence Tao describes Turing machines with oracles and complexity results relative to oracles in the form of an allegory.
6
(This is shameless self-promotion.) If you don’t mind either assuming the generalized Riemann hypothesis (for $L$-functions of quadratic Dirichlet characters) or using randomized polynomial time, then the following search problems work:
Given integers $n,a$ such that the Jacobi symbol $\left(\frac an\right)=1$, output either a square root of $a$ modulo $n$, ...
6
On popular request, here is my comment as an answer:
There is an oracle separating $\mathrm{PP}$ from $\mathrm{PSPACE}$: Jacobo Toran, A combinatorial technique for separating counting complexity classes, ICALP 1989. The best result for $\mathrm{P}^\mathrm{PP}$ that I know is a conditional result by Heribert Vollmer: Relating polynomial time to constant ...
6
The oracle you ask for has $P=NP\ne BQP=NEXP$, and therefore it has $BQP\ne PH$. Finding any oracle relative to which $BQP\ne PH$ was an open problem for twenty years until Raz and Tal [1] found such an oracle last year. In summary, the oracle you ask for currently is not known to exist, but people are looking. There are oracles relative to which $P\ne BPP=...
5
You can also prove the other direction, i.e. $DTIME(n^{ab})\subseteq DTIME(n^a)^{DTIME(n^b)}$ using a padding argument, consider any $L\in DTIME(n^a)$ via some machine $M$ running in time $O(n^{ab})$. Let $L_{\text{pad}}=\left\{1^{n^a}\#x | x\in L \right\}$, $L_{\text{pad}}$ is in $DTIME(n^b)$ via the following algorithm :
Remove $1^{n^a}\#$, and get $x$, ...
Only top voted, non community-wiki answers of a minimum length are eligible
