Search Results

From $P=RP$ extrapolation we might think $EXP=REXP$. What evidence do we have $BPP\subseteq REXP$? What consequence $REXP\subseteq BPP$ gives other than what $EXP\subseteq BPP$ gives?

Typically to show $P=NP$, one has to show an NP complete problem has a polynomial time solution and to show $P\neq NP$, has to show an NP complete problem has superpolynomial lower bound. These are br …

Particularly is there a notion of randomness there? If there is no such analogy, why is randomness in the resource bounded case special? Any references will be great. …

Where does complexity of intermediate problems stand in this case and utility of randomness stand in this case? What is scenario if $P= BPP\neq NP$ or $P\neq BPP=NP$ holds? …

Modifying following TedP We know that derandomizing width $5\leq k\in O(1)$ read many branching programs is equivalent to $BPNC^1=NC^1$ and derandomizing width $k\in\Omega(n)$ read once ordered branch …

Is there anything in physics that lets us avoid randomness? Statistical mechanics and hence entropy is founded on randomness. … Entropy, information and randomness are all related and in this case can physical principles show $P=BPP$ or $P\neq BPP$ let alone the harder $P$ versus $NP$? …

Let $\Pi$ be an $\mathsf{NP}$-complete problem. It is standard that $3SAT$ and $\Pi$ are reducible from each other. Let UnambiguousSAT, or USAT for short, denote the promise problem which is 3SAT but …

Kolmogorov and Uspenskii in this paper 'http://epubs.siam.org/doi/pdf/10.1137/1132060' speculate P=BPP in 1986. They do this without getting into circuit lower bounds and from a different view which f …

May be this is trivial but I do not know the answer. As far as we know $$\mathsf{BPP}\subseteq\mathsf{\Sigma}_2\cap\mathsf{\Pi}_2$$ holds. As far as we know $$\mathsf{NP}\cup\mathsf{coNP}\subseteq\m …

Is there any evidence for whether randomness helps or not helps depth akin to evidence for $P=BPP$? …