# Tag Info

Accepted

### Oracle Construction for Grover's Algorithm

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: ...
Accepted

### Is there a good notion of non-termination and halting proofs in type theory?

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 ...
Accepted

### Is $\sf{P^{NP \cap coNP}} = \sf{NP \cap coNP}$?

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 ...
Accepted

### What is the minimum complexity oracle that separates PSPACE from the polynomial hierarchy?

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 ...
Accepted

### Is $UP\not=NP$ with respect to random oracle?

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 ...
Accepted

### Is there a simplex-like algorithm that can be used with a separation oracle?

I'm not sure if you would consider the algorithms I'll discuss here "Simplex-like" (but see the comment about column generation at the end). If you have a weak separation oracle for a ...
Accepted

### It is known that $L \subsetneq PH$?

This is equivalent to $LOGSPACE≠NP$ (which is obviously open). The proof of that equivalence relativizes (at least under the usual oracle models). And there are oracles making $LOGSPACE = NP$ (the ...
Accepted

### Why is the "general notion of a reduction [...] inherent to the notion of self-reducibility"?

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 (...
Accepted

### Lower bounds for nonuniform circuits and oracles separating complexity classes

Yes, yes, and yes. The basic idea is to consider the characteristic function of a language $L$ (the oracle you're constructing) at length $n$ as a string of length $2^n$ that will be an input to a ...
Accepted

### How to prove $P^{Halt} = PSPACE^{Halt}$

Using $n$ calls to the halting oracle and time $O(n^2)$, you can compute the first $n$ bits of the Chaitin's constant. Using the $n$ bits of the Chaitin's constant and unbounded time, all queries to ...
Accepted

### What are examples of complexity classes that have contradictory relativizations but they were proven to be either equal or unequal?

$\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 '...

Accepted

### Young Diagrams and distinguishing between two distributions

Even relaxing the "computationally efficient" requirement, it is information-theoretically impossible. We will use the following "folklore" fact, which can be viewed as a ...
Accepted

### Recursive generic oracles

I think the point is that every notion of genericity has uncountably many generic oracles in it (see, e.g., Fenner-Fortnow-Kurtz-Li Lemma 3.12), but there are only countably many computable sets, so ...
Accepted

### Oracle-Decidability of Algebraic Independence

The answer is no; interestingly, the problem is harder to state satisfactorily in my opinion than it is to resolve! Roughly speaking, the subtlety which complicates the posing of the problem is that ...
Accepted

### Given oracle for Max-3SAT compute clauses that cannot be satisfied

Given an instance of 3SAT with $m$ clauses, you can find the set of clauses that are not satisfied in some optimal assignment with $O(m)$ calls to the oracle. The algorithm: Call the oracle on the ...

### Using an oracle to find a vector $b$ for which $Ax=b$ has a solution

We can make one observation: adaptive access to the oracle doesn't help. You might as well fix in advance the set of queries you plan to make to the oracle. So, the condition is that there has to ...

### Compressing information about the halting problem for oracle Turing machines

Let $J^A(e)$ be the output of the $e$th Turing machine equipped with oracle $A$, on input $e$. Here $J$ stands for "jump". (In case of non-halting, $J^A(e)$ is undefined.) An oracle $A$ is jump-...