Tight majority formula completeness

For $L\in {\mathrm{L}\mathrm{C}\mathrm{H}}_{P,1}$, first tie-normalize its machine $M$ by [F1], then fix a linear integer clock $R(n)\ge 1$ for the resulting machine. Let $A$ be its accepting count among the $2^{R(n)}$ fair strings $y$, including ignored suffixes. By [F4] its deterministic branch predicate has $n{\log }^{O(1)}n$ time: source choices read $y$ sequentially, and normalized short input indices map to the $x$ subword with charged offset arithmetic. Apply [F2], obtaining $F_x(y,z)$ with exactly one $z$ per accepting $y$ and none per rejecting $y$. Put $k=\mathrm{\mid }z\mathrm{\mid }$ and define ${\psi }_x=(v\wedge F_x(y,z))\vee (\mathrm{\neg }v\wedge ({\bigvee }_i{z}_i\vee w))$. For fixed $y$, the $v=0$ branch has $2^{k+1}-1$ satisfying $(z,w)$ assignments, while $v=1$ adds two exactly when $y$ accepts. Each block is therefore one above or below half, and the total is at least half exactly when $A\ge 2^{R(n)-1}$. The source has no tie, so this is its strict-majority decision. This same gadget applies to a quasilinear clock whenever needed below, with quasilinear output length.

For $L\in {\mathrm{L}\mathrm{C}\mathrm{H}}_{P,2}$, take its linear-time oracle machine and tie-normalize the first-level oracle decider. For query $q_i$, let $R_i=O(\mathrm{\mid }{q}_i\mathrm{\mid }+1)\ge 1$ clock the chosen yes/no oracle machine, with ignored fair suffixes. A proposed answer is correct precisely when its tie-free yes/no machine has more than $2^{R_i-1}$ accepting strings. Then exactly one accepting string $w_i$ has exactly $2^{R_i-1}$ accepting strings lexicographically before it. Serialize all proposed queries, answers and witnesses with lengths and canonical zero padding; its length is $O(n)$ because ${\sum }_i(\mathrm{\mid }{q}_i\mathrm{\mid }+1)=O(n)$. On a record of length $N$, put $r_i=a_i-2^{R_i-1}$, where $a_i$ counts accepting strings before $w_i$. Let $\mathrm{b}\mathrm{a}\mathrm{d}$ indicate invalid syntax and ${\mathrm{i}\mathrm{n}\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{d}}_i$ indicate that the chosen witness path fails to accept. Then $G=\mathrm{b}\mathrm{a}\mathrm{d}+{\sum }_i(r_i^2+{\mathrm{i}\mathrm{n}\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{d}}_i)$ is nonnegative and is zero exactly when every answer has its unique rank witness. These are explicit differences of path counts: choose $i$ nondeterministically, assign zero gap to invalid padded indices, and use independent strings for products; expand $(a-b{)}^2=a^2+b^2-2ab$. A fixed number of these sums/products also gives $h=1-2G^2=A-B$, positive exactly when $G=0$. Deterministic syntax/witness tests give integer indicator counts; invalid syntax skips the remaining tests and sets $G=1$. Normalize each fixed basis component by [F4] before using it on a query subword; it then has no native subinput query, and short-offset access costs only polylogarithmic time. These count constructions thus take $N{\log }^{O(1)}N$ time, with no nondeterministic choices during deterministic interpreter work. Choose one common quasilinear choice bound $P$ and require unused suffix bits zero on accepting paths, preserving counts $A,B$ among $2^P$ choice strings. A leading fair bit selects $A$ on branch zero and the complement of $B$ on branch one. There are $2^P+(A-B)$ accepting choice strings out of $2^{P+1}$, so the transcript-validity language $C=\{h>0\}$ has a matching-profile quasilinear probabilistic decider. The original rank strings still have total linear length.

Normalize the original outer oracle machine by [F1] before this construction. Keep its original fixed-length fair-bit string $p$ separate from a guessed fixed-length transcript record $t$, whose unused suffix is canonically zero. Simulate the original machine on $p$ using the proposed answers in $t$, and record whether its queries match the listed queries and its final outcome accepts. Make a single final query to $C$ containing the record and this flag; extend $C$ to reject whenever the flag fails. There is exactly one correct answer/rank-witness record for each $p$ by step 1.2. Consequently exactly one $t$ gives a YES query when the original path accepts and none do when it rejects. The number of successful pairs $(p,t)$ is the original accepting-path count. No preservation of the acceptance probability after guessing $t$ is asserted; the next steps restore its threshold explicitly.

Let $q(p,t)$ be the deterministic final query from step 2.1, padded to fixed length $L$. Apply [F2] to its quasilinear-time computation using [F4] to obtain $D_x(p,t,q,z)$ with exactly one satisfying $(q,z)$ extension for every pair $(p,t)$. Apply the same unique-witness/majority gadget of step 1.1 with the quasilinear clock for $C$ on the variable input $q$, retaining $q$ as free Boolean variables, to obtain ${\mathrm{\Psi }}_C(q,u)$ whose inner at-least-half test is true exactly when $q\in C$. Form the outer matrix ${\mathrm{\Phi }}_x=(v\wedge D_x(p,t,q,z)\wedge {\mathrm{\Psi }}_C(q,u))\vee (\mathrm{\neg }v\wedge ({\bigvee }_i{t}_i\vee {\bigvee }_j{q}_j\vee {\bigvee }_k{z}_k\vee w))$. Here $w$ is one outer padding bit; the inner block $u$ has a fixed length independent of the value of $q$. All deterministic computations have quasilinear time in their input length in the selected profile, so [F2] gives total formula size $n{\log }^{O(1)}n$, logarithmic workspace and the claimed bit-generation and sequential-streaming interfaces.

Fix the original fair string $p$, and put $H=\mathrm{\mid }t\mathrm{\mid }$, $k=\mathrm{\mid }z\mathrm{\mid }$. Among $v=0$ outer assignments, the fallback is false at exactly one $(t,q,z,w)$ tuple, so $2^{H+L+k+1}-1$ assignments give a residual inner formula true on at least half of $u$. Among $v=1$ assignments, $D_x$ has exactly one $(q,z)$ extension for each $t$, and precisely one $t$ has $q(p,t)\in C$ if and only if the original path accepts. Its two choices of $w$ contribute two additional successful outer assignments. Thus each fixed-$p$ block contributes one below half on a rejecting original path and one above half on an accepting original path. Summing the equal-sized $p$ blocks makes outer at-least-half true exactly when at least half of the original fair strings accept; outer tie normalization in step 2.1 makes this the original strict-majority language.

Step 1.1 proves the first-level reduction, and step 1.2 and step 2.1 and step 3.1 and step 4.1 prove the second-level reduction in either fixed profile. All added blocks have $O(n)$ length before the near-linear formula encoding, and only a fixed number of these encodings are composed. The explicit clause order of [F2] preserves the sequential streaming property; the direct-input bit generator has the claimed polylogarithmic time and logarithmic workspace. This proves both reductions.