P vs. BPP

P vs. BPP

Definitions and mathematical statement

A language $L$ is in $\mathsf{BPP}$ if a randomized polynomial-time algorithm $A$ satisfies $\Pr[A(x)=1_L(x)]\ge2/3$ for every input $x$. Membership in $\mathsf P$ requires a deterministic polynomial-time decision algorithm with no errors. Determine whether \[ \forall L\in\mathsf{BPP},\quad L\in\mathsf P. \] The simulation must work in the ordinary uniform model, not merely through nonuniform advice or for most inputs.

Formulation and concept references: [S1].

Short English statement

Can randomness always be removed from an efficient bounded-error decision algorithm without losing polynomial-time efficiency?

Research attempt

Scope, process, and source check.

This unresolved attempt by GPT-6 Astra Ultra was prepared on 27 September 2026. The method was to isolate the randomness actually needed by a fixed bounded-error decider, derive sufficient replacement conditions, and test whether existential or limited-independence arguments meet those conditions. All inputs of a given length must be handled, and the deterministic simulator must be one finite uniform algorithm. Neither advice depending on the length nor an average-case guarantee is substituted for that requirement.

The pseudorandomness framework in Vadhan [S1] distinguishes short seed length, fooling guarantees, and efficient construction. Adleman's classical nonuniform simulation [E1] supplies the relevant warning: bounded-error randomness can be fixed separately at each input length without giving a uniform derandomization. Impagliazzo--Wigderson [E2], Theorem 2, prove $\mathsf P=\mathsf{BPP}$ under the hypothesis that some language in $\mathsf E=\mathsf{DTIME}(2^{O(n)})$ has worst-case circuit complexity $2^{\Omega(n)}$. That hypothesis is not proved here. The catalogue's recent result [S3] treats insensitive algorithms; no unrestricted simulation is inferred from its restricted algorithm class.

Attack plan and normalization.

Fix a BPP decider $A$ for a total language $L$. On inputs of length $n$, pad its random tape to a deterministic polynomial length $m(n)$; unused bits have no effect. Write $A(x;r)\in\{0,1\}$ for the resulting deterministic computation. Its time is polynomial for every $r$, not merely in expectation. A sufficiently good, uniformly generated polynomial-size collection of random tapes would permit deterministic enumeration. The main route is to state exactly what "sufficiently good" means, then compare that condition with what amplification and independence really provide.

The containment $\mathsf P\subseteq\mathsf{BPP}$ follows by ignoring random bits. Thus an upper-bound solution needs the reverse containment for every fixed BPP decider, with a polynomial runtime allowed to depend on that decider. A negative solution needs one total bounded-error language outside every uniform deterministic polynomial-time bound.

Lemma 27.1: a uniform short-seed condition is sufficient.

Suppose that for the fixed $A$ there is a deterministic algorithm computing \[ G_n:\{0,1\}^{d(n)}\longrightarrow\{0,1\}^{m(n)}, \qquad d(n)\le c\log_2(n+2), \] in time polynomial in $n$, where $d(n)$ is efficiently computable and $c$ is a constant. Suppose also that, for every $x\in\{0,1\}^n$, \begin{equation}\label{wsref-0-61-32-37-3a-66-6f-6f-6c-69-6e-67} \left|\Pr_{s}[A(x;G_n(s))=1]-\Pr_r[A(x;r)=1]\right|\le1/12. \end{equation} Then $L\in\mathsf P$.

Proof. Enumerate all $2^{d(n)}\le(n+2)^c$ seeds, compute their outputs, and count accepting simulations. On yes-inputs the fraction is at least $2/3-1/12=7/12$. On no-inputs it is at most $1/3+1/12=5/12$. Comparing the integer acceptance count with half the number of seeds therefore decides $L$ without error. The generator and each simulation take polynomial time, as does the number of seeds. Small input lengths are included by the displayed $(n+2)$ bound, or can be hardwired separately if the hypothesis begins only eventually.$\square$

This lemma asks only to fool the tests $r\mapsto A(x;r)$ associated with one decider, not every Boolean function on the random tape. The generator may depend on $A$, but its algorithm is fixed before seeing $x$. It is the uniformity and simultaneous guarantee for all $x$ that will be missing below. A generator with seed length $(\log n)^2$ would instead give the enumeration cost $2^{O((\log n)^2)}$, which is not a polynomial bound. A short seed is also insufficient if evaluating one generator output takes superpolynomial time. These costs cannot be hidden inside the name "pseudorandom."

Lemma 27.2: fixing randomness does give polynomial advice.

For each length $n$ there is a list of \[ R=12(n+2)+1 \] random tapes such that majority vote among the corresponding executions of $A$ is correct on every length-$n$ input.

Proof. Select the $R$ tapes independently and uniformly. Fix an input $x$ and let $X_i$ indicate an incorrect answer on tape $i$. The variables are independent and satisfy $\Pr[X_i=1]\le1/3$. Therefore \[ \mathbb E\,2^{\sum_i X_i} =\prod_i\mathbb E\,2^{X_i}\le(4/3)^R. \] Markov's inequality gives \[ \Pr\left[\sum_iX_i\ge R/2\right] \le\left(\frac4{3\sqrt2}\right)^R <(8/9)^{6(n+2)}<2^{-(n+2)}. \] The last inequality uses $(8/9)^6<1/2$, or equivalently $2\cdot8^6<9^6$. As $R$ is odd, majority is unambiguous. There are $2^n$ possible inputs, so the union bound makes the probability of any wrong majority less than $1/4$. At least one list has no wrong majority at all. Its length is $Rm(n)$, a polynomial in $n$.$\square$

Hardwire such a list at each length and simulate the fixed algorithm by polynomial-size circuits. This proves the familiar containment $\mathsf{BPP}\subseteq\mathsf{P/poly}$. The displayed estimate was derived explicitly to make its exact scope visible. The list is independent of the particular input, but its existence proof does not tell a uniform algorithm which list to print. Brute-force enumeration of candidate lists followed by checking all $2^n$ inputs is not a polynomial-time construction; checking correctness also requires knowing the correct language answers. No efficient replacement for that verification is supplied here.

The two lemmas consequently do not combine automatically. Lemma 27.1 has an effective generator hypothesis, while Lemma 27.2 provides only existential length-dependent data. Treating the latter as a subroutine would introduce precisely the nonuniform advice forbidden in the target statement.

An exact test of the limited-independence repair.

One might try to construct replacement tapes by ensuring that all small sets of random bits are independent. The following example shows that even a very strong version of that property does not fool every polynomial-time algorithm.

For $m\ge2$, let $D_m$ be uniform over pairs $(u,v)\in\{0,1\}^m\times \{0,1\}^m$ such that both blocks have even parity. It is efficiently sampled: choose the first $m-1$ bits of each block freely and set the last bit to their XOR. Every set of at most $m-1$ coordinates in the full $2m$-bit string is uniformly distributed. Indeed, in each block any prescribed values on fewer than $m$ coordinates have exactly $2^{m-t-1}$ even-parity completions, where $t$ coordinates were prescribed. The two blocks are independent, so the joint marginal is also uniform.

Now consider the algorithm that accepts exactly when both blocks have even parity. With fully independent fair bits its acceptance probability is $1/4$. It is therefore a valid BPP decider for the empty language, with success $3/4$ on every input; choose $m$ polynomial in input length and ignore the input contents. Under $D_m$ it accepts with probability $1$ and is wrong on every input. Repeating executions with independently drawn $D_m$ tapes preserves this certain error.

This is a counterexample to a proposed universal derandomization rule, not a hard language: the empty language has the trivial deterministic rejecting algorithm. It shows that many-wise independence constrains local marginals while a linear-time parity test can inspect a global correlation. The proof of a pseudorandom generator must control the actual computational tests in (a27:fooling); replacing that proof by an independence count is invalid. Restricted algorithms that cannot detect such correlations may admit different positive results, with their hypotheses retained.

Why an input-dependent seed search is not yet an algorithm.

There is a second quantifier trap in asking for one fixed logarithmic-seed generator to fool all polynomial-time tests at once. Suppose its output length is $m(n)=n$ and its range has at most $(n+2)^c$ strings. The test "is $r$ in the range of $G_n$?" enumerates every seed and compares its generated output with $r$. If the generator is polynomial-time, this test is also polynomial-time. It accepts generator outputs with probability $1$, but accepts a uniform $n$-bit string with probability at most $(n+2)^c/2^n$, eventually less than $1/3$. On those lengths it is itself a valid randomized decider for the empty language; finitely many smaller lengths can simply reject. Thus that fixed generator fails this particular efficient test.

This does not obstruct Lemma 27.1: its generator may depend on the decider or on a specified circuit-size bound. Increasing the test's polynomial exponent may require increasing the seed constant or the generator's work. The support-membership test proves that those dependencies cannot be erased by asserting one fixed polynomial budget that works for every polynomial budget. It is also another counterexample to a proposed universal replacement rule, not evidence that the empty language needs randomness.

For a yes-input, many tapes lead to acceptance; for a no-input, many lead to rejection. Finding an accepting tape alone therefore does not identify the answer. A BPP machine may have accepting tapes on both sorts of input. Likewise, finding a tape on which repeated runs agree is insufficient unless that agreement is certified to reflect the true majority over all tapes. The two-sided error convention must remain in the argument.

A useful exact restricted case is $m(n)=O(\log n)$: enumerate every original random tape and compare the true acceptance fraction with $1/2$. No generator is needed, and the result is a uniform polynomial-time decider. The missing step for arbitrary BPP is thus not amplification alone. It is a method of replacing polynomially many random bits by logarithmically many effectively enumerable bits while preserving the decision gap, or another simulation achieving the same effect.

One cannot choose a successful tape list for each input by an unrestricted existential quantifier and then call that choice a deterministic computation. Nor can the list be fixed once for all input lengths: its tape lengths and coverage obligations change with $n$. Lemma 27.2 addresses each finite input length separately, as nonuniform circuit complexity allows.

Verification, remaining gap, and outcome.

The companion script checks the amplification bound using exact rational binomial probabilities at the boundary failure probability $1/3$, verifies $2\cdot8^6<9^6$, and tests all coordinate marginals of $D_m$ through $m=5$. It confirms acceptance $1/4$ under uniform tapes and $1$ under the replacement. These are finite checks of the displayed claims; their all-length versions follow from the proofs. No heuristic randomness test is treated as a proof that a generator fools all polynomial-time computations.

UNRESOLVED. The strongest uniform conclusion proved here is exact derandomization for logarithmic randomness, and the conditional short-seed lemma. The all-input tape-fixing argument remains nonuniform, and the proposed limited-independence replacement has an explicit failing decider. The first remaining gap is a uniform polynomial-time construction meeting the necessary all-input gap guarantee for an arbitrary BPP decider. A lower-bound solution would instead need one BPP language outside every deterministic polynomial bound. Neither is established, and no novelty is claimed for the elementary or classical calculations.

Sources

• S1 S. Vadhan, 'Pseudorandomness', Foundations and Trends in Theoretical Computer Science 7$1-3$:1-336, 2012. https://people.seas.harvard.edu/~salil/pseudorandomness/pseudorandomness-Aug12.pdf. Formulation source.
• S2 CS 6810: Theory of Computing, Lecture 15, March 17, 2026. https://www.cs.cornell.edu/courses/cs6810/2026sp/lec15.pdf. Further reference; not a proof endorsement.
• S3 Pseudorandomness Beating the Hybrid Argument for Insensitive Algorithms. https://eccc.weizmann.ac.il/report/2026/082/. Further reference; not a proof endorsement.
• E1 Leonard M. Adleman, Two Theorems on Random Polynomial Time, Proceedings of FOCS 1978, pp. 75--83. https://doi.org/10.1109/SFCS.1978.37. https://mikael-monet.net/share/papers/adleman1978.pdf. Primary nonuniform-simulation reference; consulted 27 September 2026. The explicit amplification and tape-fixing calculation is given above.
• E2 Russell Impagliazzo and Avi Wigderson, P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma, Proceedings of STOC 1997, pp. 220--229, Theorem 2. https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/IW97/proc.pdf. https://doi.org/10.1145/258533.258590. Conditional hardness-versus-randomness result; consulted 27 September 2026. Its circuit-hardness assumption is not asserted here.

P vs. BPP

Definitions and mathematical statement

A language $L$ is in $\mathsf{BPP}$ if a randomized polynomial-time algorithm $A$ satisfies $\Pr[A(x)=1_L(x)]\ge2/3$ for every input $x$. Membership in $\mathsf P$ requires a deterministic polynomial-time decision algorithm with no errors. Determine whether \[ \forall L\in\mathsf{BPP},\quad L\in\mathsf P. \] The simulation must work in the ordinary uniform model, not merely through nonuniform advice or for most inputs.

Formulation and concept references: [S1].

Short English statement

Can randomness always be removed from an efficient bounded-error decision algorithm without losing polynomial-time efficiency?

Research attempt

Current frontier.

A central established conditional result is that exponential circuit hardness in $\mathsf E$ at all sufficiently large lengths suffices for $\mathsf{BPP}=\mathsf P$. The all-length and nonuniform-hardness qualifications cannot be removed from that implication. Vadhan gives this in Corollary 7.64 and discusses the infinitely-often distinction immediately afterward. [S1]. Doron--Moshkovitz--Oh--Zuckerman's May 2026 manuscript improves generator and hitting-set parameters for algorithms satisfying specified insensitivity properties, within the hardness-versus-randomness program; it does not establish unconditional derandomization of arbitrary BPP machines. [S3], [E1]. The paper's abstract and parameter scope, and the recent course account [S2], were checked. The argument below does not assume the hard function or the insensitivity property for every machine.

Attack route.

The probabilistic method gives a short list of random tapes that is good for every input of a fixed length. The missing step is generating such a list uniformly. I combine this finite existence proof with a robust conditional-expectation selection rule, asking exactly what an efficiently computable pessimistic quantity would have to provide. The competing approach replaces the tapes with a bounded-independence distribution; an explicit BPP acceptance predicate tests whether that alone suffices. Nonuniform derandomization and conditional expectations are classical techniques treated separately in [S1], Sections 3.2 and 3.4; the following calculation puts their computational gap in one place.

Attempt.

Fix a BPP machine $A$ for a total language $L$. On inputs of length $n$, pad its randomness to exactly $r(n)\ge1$ bits, with $r(n)$ polynomially bounded and computable. Every input $x$ has error probability at most $1/3$. Take $k=24(n+2)+1$ independent tapes $R_1,\ldots,R_k$, so $k$ is odd, and let $A^{[k]}$ return their majority vote.

Lemma 27.1 (a simultaneously good polynomial-length tape list). There is a fixed tuple $s_n=(R_1,\ldots,R_k)$ such that $A^{[k]}(x;s_n)=1_L(x)$ for every $x\in\{0,1\}^n$.

Proof. For fixed $x$, let $S$ count erroneous independent runs. Since each has error probability at most $1/3$, $\mathbb E2^S\le(4/3)^k$. Markov's inequality gives \[ \Pr[S\ge k/2]\le\left(\frac{2\sqrt2}{3}\right)^k=\rho^k. \] As $k$ is odd, majority error is included in this event. Also $\rho^2=8/9$ and $(8/9)^{12}<1/4$ (an exact rational inequality). The expected number of inputs on which the majority errs is at most \begin{equation}\label{wsref-0-72-32-37-3a-73-6d-61-6c-6c-70-6f-74-65-6e-74-69-61-6c} 2^n\rho^k<2^n4^{-(n+2)}\le1/16. \end{equation} If every tuple were bad on some input, that integer-valued count would always be at least one. Hence a tuple with no errors exists.$\square$

The tuple has $kr(n)=\operatorname{poly}(n)$ bits. Hardwiring one such tuple for each $n$ proves a nonuniform circuit simulation, not the desired uniform algorithm. The proof has made no choice rule for $s_n$.

Lemma 27.2 (a robust conditional-expectation criterion). Write $B=kr(n)$ and regard the tape tuple as a uniform $B$-bit string $S$. Let \[ Z(S)=\#\{x\in\{0,1\}^n:A^{[k]}(x;S)\ne1_L(x)\}, \qquad W(p)=\mathbb E[Z(S)\mid S\text{ extends }p]. \] Suppose that, for this fixed machine, a uniform deterministic polynomial-time procedure computes on every prefix $p$ a rational number $\widetilde W(p)$ such that \begin{equation}\label{wsref-0-72-32-37-3a-65-73-74-69-6d-61-74-65} |\widetilde W(p)-W(p)|\le\frac1{8B}. \end{equation} Then $L\in\mathsf P$.

Proof. Starting at the empty prefix, compute the estimates for $p0,p1$ and append the bit with smaller estimated value. Since $W(p)=(W(p0)+W(p1))/2$, at least one true child value is at most $W(p)$. The chosen true value is at most this smaller true value plus $2/(8B)$. After $B$ choices the resulting string $s_n$ therefore satisfies \[ Z(s_n)=W(s_n)\le W(\varnothing)+1/4<1. \] The nonnegative integer $Z(s_n)$ must be zero. Generating the tuple takes $2B$ polynomial-time estimation calls; the majority of the $k$ runs is also polynomial time. The construction is uniform at every length, including small lengths, and uses no advice.$\square$

This is a genuine sufficient algorithmic condition, but not an independently established estimator. In particular, $W$ is defined using the unknown correct language bits. On a full string it counts errors over $2^n$ inputs. Rewriting it as a finite sum does not make it polynomial-time computable. Replacing the language bits by majority over all random tapes merely inserts further exponentially large sums. The conditional-expectation identity proves an advantageous child exists; it does not by itself identify that child efficiently.

The absolute accuracy in (r27:estimate) is only inverse-polynomial for the unnormalized count $W$, but $W$ sums over $2^n$ inputs. An inverse-polynomial error for the normalized average $2^{-n}W$ is far too coarse for the same selection proof: after rescaling it could hide exponentially many bad inputs. This is another precise difference between an almost-everywhere simulation and the total-language target.

Testing whether bounded independence repairs the selection gap. Let $r\ge2$ and let $D$ be uniform on the even-parity strings $u\in\{0,1\}^r$, with an additional independent uniform bit $b$. Any $r-1$ coordinates among the $u$ bits are uniform and independent: once they are fixed, exactly one last bit satisfies the parity equation. Consequently $(u,b)$ is $(r-1)$-wise independent. Nevertheless, the polynomial-time acceptance predicate \begin{equation}\label{wsref-0-72-32-37-3a-70-61-72-69-74-79} A_*(u,b)=\operatorname{Parity}(u)\ \lor\ b \end{equation} has probability $3/4$ under fully uniform bits and probability $1/2$ under $D$. As a machine ignoring its ordinary input, $A_*$ is a valid BPP decider for the all-yes language with error $1/4$. The bounded- independence replacement loses the required acceptance margin, even though its independence order grows linearly with the tape length. The companion script verifies the marginals and the two probabilities exactly for small $r$.

This does not prove a separation: the all-yes language has a trivial deterministic decider. Nor does it refute bounded-independence generators for restricted circuit classes. It refutes the specific proposed universal inference that high independence of random coordinates alone preserves every BPP acceptance gap. Enumeration of that particular support and a tie rule is not a general replacement for a proof of pseudorandomness against the algorithm being simulated.

A second sufficient condition, with its seed length exposed. Suppose instead that for every BPP machine $A$ there is a uniform polynomial-time computable map \[ G_{A,n}:\{0,1\}^{d(n)}\longrightarrow\{0,1\}^{r(n)}, \qquad d(n)\le C_A\log_2(n+2), \] whose output changes $A$'s acceptance probability by less than $1/12$ on every input of length $n$. Enumerating all seeds then computes an acceptance fraction that is at least $7/12$ on yes-inputs and at most $5/12$ on no-inputs. Comparison with $1/2$ decides $L$ deterministically in polynomial time. This elementary conversion is the reason the logarithmic seed length and uniform generator evaluation matter. [S1], Chapters 3 and 7. A polynomial-length seed yields an exponential enumeration, and a different hardwired generator for each length yields only advice unless uniformly generated.

Stress test.

The existence proof and both conditional simulations handle a total language, not a promise on a favorable set of inputs. They permit the polynomial exponent to depend on $A$ but not on the individual input. The amplification probability uses independent runs of $A$; it is not applied to the parity-conditioned tapes as though they were independent. Lemma 27.2 explicitly budgets every approximation error, so no exact real-arithmetic oracle is hidden in the final selection rule. Its hypothetical estimator must output ordinary polynomial-bit rationals.

The hard-function theorem in the frontier would imply the generator condition using much deeper machinery, but its circuit lower bound is not proved here. The insensitivity result also has additional hypotheses, not a theorem that every BPP machine meets them. [E1]. Neither the small good list nor failure of the parity replacement gives an unconditional class separation. The companion finite tests check the amplification constants and the parity example only; a numerical test cannot verify all BPP machines.

\Needspace{8\baselineskip}

Outcome.

Outcome: Conditional reduction.

The attempt proves a uniform derandomization criterion based on an accurate conditional-error-count estimator, including a quantitative error budget, and records the short-generator alternative with every parameter explicit. It also demonstrates why nonconstructive short lists and high-order independence do not themselves meet these conditions. No polynomial-time estimator or general short generator is constructed unconditionally. The remaining gap is computational, not the existence of a good tuple. The constituent techniques are classical, and no historical novelty or complete resolution of $\mathsf P=\mathsf{BPP}$ is claimed.

Sources

• S1 S. Vadhan, 'Pseudorandomness', Foundations and Trends in Theoretical Computer Science 7$1-3$:1-336, 2012. https://people.seas.harvard.edu/~salil/pseudorandomness/pseudorandomness-Aug12.pdf. Catalogue formulation source.
• S2 CS 6810: Theory of Computing, Lecture 15, March 17, 2026. https://www.cs.cornell.edu/courses/cs6810/2026sp/lec15.pdf. Catalogue research/status reference; not a proof endorsement.
• S3 Pseudorandomness Beating the Hybrid Argument for Insensitive Algorithms. https://eccc.weizmann.ac.il/report/2026/082/. Catalogue research/status reference; not a proof endorsement.
• E1 Dean Doron, Dana Moshkovitz, Justin Oh and David Zuckerman, Pseudorandomness Beating the Hybrid Argument for Insensitive Algorithms, ECCC TR26-082, revision 1, 17 May 2026. https://eccc.weizmann.ac.il/report/2026/082/. Version-specific supplement to [S3]. Abstract, generator parameters, and extra insensitivity hypotheses consulted 27 September 2026; not an unconditional BPP derandomization theorem.