Answer: Polynomial-time computable in \(m,\tau,K,L\) with the prescribed exact arithmetic-circuit output.
Theorem 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe worst-case complexity of computing PEQA is O(nK). 6. Welfare Under Costly Reliability In this section, we extend our analysis to how PEQA deals with social welfare in a world where increasing reliability is costly to the grader. We calculate student welfare by subtracting the total reliability-cost from the sum of the grading-accuracy of all exams. We show that a modification of the grading performance score t∗of PEQA implements the student welfare- optimal level of costly reliability.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a rational distribution \(\mu\) over complete student types, where each type fixes its own paper type, its \(K\)-paper grading bundle and reports, and the incoming reviewer profiles for its papers, compute the probe estimates, PEQA paper scores, and per-capita bonuses from the leave-one-reviewer-out accuracy calculation. Require the repeated incidence pattern to be realizable by the paper’s \(\texttt{computeG}\) rule; return type-wise and mass-weighted outputs using binary-rational inputs and the paper’s squared-error reward.
A society is given by its support: the list of the \(\tau\) complete student types with positive binary-rational masses \(\mu_a\), summing to \(1\); \(\tau\) is the support size, not the number of possible types. Let \(L\) be the total input bit length.
There are \(m\) paper profiles. Profile \(p\) specifies probe status, a true score \(y_p\in\mathbb Q\), a regrading-request indicator \(q_p\in\{0,1\}\), and a list \(H_p\) of incoming reviewer slots, each recording a student type and rational report. Type \(a\) specifies its own paper profile \(p(a)\) and its \(K\) outgoing grading incidences, referencing paper profiles and incoming slots; repeated profiles represent distinct papers or reviewers, not merged incidences.
Let \(h=K/2\), with even \(K\ge4\). Each bundle contains \(h\) probes and \(h\) non-probes. Inputs promise reciprocal incidence consistency and a finite realization with \(n\mu_a\) students of each type and \(h+1\le\ell\le n/(h+1)\) probes, using the following assignment construction; finding or checking a realization is outside the problem.
Order probe owners and non-probe owners cyclically. Each probe owner grades the next \(h\) probes; each other student grades \(h\) consecutive probes. Each non-probe owner grades the next \(h\) non-probes; probe owners receive \(h\) non-probes apiece, with these additional bundles pairwise disjoint. No student grades her own paper. The realization must reproduce every specified profile, report, slot, and bundle.
Input prior mean \(\eta\in\mathbb Q\), prior precision \(\gamma\in\mathbb Q_{>0}\), and bonus multiplier \(\alpha\in\mathbb Q_{>0}\). For type \(a\), let \(P_a\) and \(N_a\) denote its probe and non-probe outgoing incidences, with report \(z_e\) and target profile \(p(e)\).
Define \(b_a=h^{-1}\sum_{e\in P_a}(z_e-y_{p(e)})\), \(v_a=\sum_{e\in P_a}(z_e-y_{p(e)}-b_a)^2>0\), and estimated reliability \(\rho_a=(h-1)/v_a\).
For a non-probe profile and any subset of its incoming slots, define \(r_p(S)=(\sqrt\gamma\,\eta+\sum_{e\in S}\sqrt{\rho_{a(e)}}(z_e-b_{a(e)}))/(\sqrt\gamma+\sum_{e\in S}\sqrt{\rho_{a(e)}})\). Set \(r_p=r_p(H_p)\); probes receive \(r_p=y_p\).
Requests satisfy \(q_p=1\Rightarrow r_p<y_p\). For non-probes, set \(g_p=q_py_p+(1-q_p)r_p\), the final paper score and the reference score used for bonuses; probes have \(g_p=y_p\).
With squared-error reward \(R(x,y)=-(x-y)^2\), the per-capita bonus of type \(a\) is \(t_a=\alpha\sum_{e\in N_a}[R(r_{p(e)},g_{p(e)})-R(r_{p(e)}(H_{p(e)}\setminus\{e\}),g_{p(e)})]\); deletion removes only the designated reviewer slot and leaves estimates and reference scores fixed.
Compute the type-wise estimates, tentative and final own-paper scores, and bonuses, together with each output's mass-weighted mean \(\sum_a\mu_a X_a\). Exact numerical outputs are represented by arithmetic circuits with binary-rational constants and arithmetic and positive-square-root gates.
Is this promised continuous PEQA evaluation problem computable in polynomial time in \(m,\tau,K,L\), or is it NP-hard?
For finite populations, PEQA evaluation is stated to require \(O(nK)\) arithmetic operations; this does not establish a binary-input bit-complexity bound. [Verified source](https://www.cse.iitb.ac.in/~swaprava/papers/peergrading.pdf).
No result settling this precise distribution-over-complete-types problem was located in the literature search.
The promised problem is computable in polynomial time in \(m,\tau,K,L\) with the prescribed exact circuit output.
Here arithmetic gates are \(+,-,\times,\div\), together with positive-square-root gates. The algorithm constructs circuits without expanding their algebraic values. All divisions and square roots used below are well-defined on every promised input.
For each type \(a\) and each probe incidence \(e\in P_a\), construct
\[
\]
\(d_{a,e}=z_e-y_{p(e)}.\)
Then construct the following gates, in order:
\(b_a=\dfrac{1}{h}\sum_{e\in P_a}d_{a,e},\qquad v_a=\sum_{e\in P_a}(d_{a,e}-b_a)^2,\qquad \rho_a=\dfrac{h-1}{v_a},\qquad w_a=\sqrt{\rho_a}.\)
Squaring uses a multiplication gate. The factor \(1/h\) can be implemented by division by the integer constant \(h\), so no computed rational constant needs to be expanded.
These expressions agree with the stipulated estimates. Moreover, \(K\ge 4\) implies \(h\ge 2\), and the promise gives \(v_a>0\). Consequently, every division here is valid and \(\rho_a>0\).
Construct also \(w_0=\sqrt{\gamma}>0\). Estimation requires \(O(\tau K)\) gates and \(\tau+1\) square-root gates in total.
For each incoming slot \(j\in H_p\) of a non-probe profile \(p\), let \(a(j)\) be its recorded reviewer type and \(z_j\) its report. Construct
\(c_{p,j}=w_{a(j)}(z_j-b_{a(j)}),\)
and then
\(A_p=w_0\eta+\sum_{j\in H_p}c_{p,j},\qquad D_p=w_0+\sum_{j\in H_p}w_{a(j)}.\)
Set
\(r_p=A_p/D_p,\qquad g_p=q_py_p+(1-q_p)r_p.\)
For a probe profile, set \(r_p=g_p=y_p\).
These are exactly the required tentative and final profile scores. Because \(q_p\) is supplied as an input bit, constructing \(g_p\) requires no comparison between \(r_p\) and \(y_p\). The implication \(q_p=1\Rightarrow r_p<y_p\) is a promise, not a condition the evaluation algorithm must check.
For each incoming slot \(j\) of a non-probe profile, construct
\(u_{p,j}=\dfrac{A_p-c_{p,j}}{D_p-w_{a(j)}}.\)
Subtracting the contribution of that particular slot gives
\(A_p-c_{p,j} =w_0\eta+\sum_{i\in H_p\setminus\{j\}}w_{a(i)}(z_i-b_{a(i)}),\)
and
\(D_p-w_{a(j)} =w_0+\sum_{i\in H_p\setminus\{j\}}w_{a(i)}.\)
Therefore,
\(u_{p,j}=r_p(H_p\setminus\{j\}).\)
This deletion leaves every estimate and reference score fixed, as required. Its denominator is at least \(w_0>0\); the full denominator \(D_p\) is also positive. Thus all profile-score and deletion divisions are valid, including when deleting the only incoming slot.
All sums are over slot identities. Equal reviewer types or reports do not cause slots to be merged.
Let \(j(e)\) denote the incoming slot referenced by an outgoing non-probe incidence \(e\). Construct
\(B_e= \bigl(u_{p(e),j(e)}-g_{p(e)}\bigr)^2 -\bigl(r_{p(e)}-g_{p(e)}\bigr)^2.\)
The squared-error reward gives
\(R(r_{p(e)},g_{p(e)}) -R(u_{p(e),j(e)},g_{p(e)})=B_e.\)
Hence the required type bonus is
\(t_a=\alpha\sum_{e\in N_a}B_e.\)
Every outgoing incidence appears separately in this sum. Repeated profile references therefore preserve their required multiplicity, even when their numerical contributions coincide.
For type \(a\), output its own-paper scores
\(s_a=r_{p(a)},\qquad f_a=g_{p(a)},\)
together with \(b_a,\rho_a,t_a\). The statistic \(v_a\) can also be output without additional computation.
For each output family \(X\), construct its mass-weighted mean
\(\overline X=\sum_{a=1}^{\tau}\mu_aX_a.\)
This requires \(O(\tau)\) additional gates per family. In particular, the mean reliability is \(\sum_a\mu_a\rho_a\); the algorithm averages the already constructed type-wise outputs.
Fix any finite realization supplied by the promise.
All students of type \(a\) have the specified outgoing probe incidences and reports. Thus their estimates are precisely the constructed \(b_a,v_a,\rho_a\).
Each paper with profile \(p\) has the specified incoming reviewer slots, types, and reports. Since each reviewer’s estimate depends only on her complete type, its tentative score equals the constructed \(r_p\). Its probe status and request indicator then give final score \(g_p\).
Reciprocal incidence consistency ensures that every outgoing incidence identifies the appropriate incoming slot. The deletion identity proved above therefore gives exactly the stipulated score with that reviewer slot removed. Summing the reward differences over all outgoing non-probe incidences gives \(t_a\).
Finally, the realization has \(n\mu_a\) students of type \(a\). Since each output is constant within a type, its population mean is
\(\dfrac{1}{n}\sum_{a=1}^{\tau}(n\mu_a)X_a =\sum_{a=1}^{\tau}\mu_aX_a.\)
Consequently, the circuits compute all requested outputs and means for every promised realization. Finding a realization or enumerating its students is unnecessary.
Let
\(M=\sum_{p=1}^{m}|H_p|,\qquad C=1+m+\tau K+M.\)
The construction uses:
Thus a shared circuit with designated output gates has \(O(C)\) gates.
Its rational leaves can reference the input constants directly. Apart from those constants, only constants such as \(0,1,h,h-1\) are needed. Their total additional encoding length is polynomially bounded. Each gate has constant arity and uses \(O(\log(C+1))\) bits for its operand indices. The total circuit encoding length is therefore
\(O\bigl(L+C\log(C+1)\bigr).\)
Both incoming slots and outgoing incidences are explicitly listed in the input, so \(M\) and \(\tau K\) are bounded by the explicit input length, up to encoding constants. In particular, this encoding length is polynomial in \(m,\tau,K,L\).
A deterministic algorithm generates the circuit by traversing those lists and recording gate indices. Even implementing all reference lookups by linear scans gives polynomial bit time. No intermediate algebraic value, algebraic comparison, or expanded rational numerator or denominator must be computed. If separate circuits are required for individual outputs, copying the shared circuit for each output still gives polynomial total size and construction time.
The finite-population arithmetic bound appears in Theorem 3 and Appendix B.4 of the [PEQA paper](https://www.cse.iitb.ac.in/~swaprava/papers/peergrading.pdf). The argument above establishes the additional binary-input bound for this explicitly supported, circuit-output formulation.
⟨structured verdict parsed — rendered above⟩
The prover resolves the requested problem: the prescribed exact outputs can be constructed in polynomial bit time. No mathematical or complexity gap was found. There is one minor formatting defect.
The formulas for \(d_{a,e}\), \(b_a\), \(v_a\), and \(\rho_a\) match USER_TASK exactly. Each probe incidence is processed separately. Since \(h=K/2\ge2\) and the input promises \(v_a>0\), division by \(h\) and \(v_a\) is valid, and \(\rho_a>0\). The square-root gates for \(w_a=\sqrt{\rho_a}\) and \(w_0=\sqrt{\gamma}\) therefore have strictly positive arguments.
The claimed \(O(\tau K)\) gate count and \(\tau+1\) square-root gates are correct.
The constructed numerator \(A_p\) and denominator \(D_p\) reproduce the stipulated weighted average. In particular, the prior contribution is \(w_0\eta\), and each incoming slot contributes its reviewer type’s debiased report with weight \(w_{a(j)}\).
The denominator satisfies \(D_p\ge w_0>0\). Probe scores and the formula \(g_p=q_py_p+(1-q_p)r_p\) also match the task. Treating the request implication as a promise is legitimate: evaluation requires no algebraic comparison or verification of that implication.
Subtracting \(c_{p,j}\) and \(w_{a(j)}\) removes precisely the designated slot from the numerator and denominator. The two displayed subtraction identities are correct.
The remaining denominator is at least \(w_0>0\), including when the deleted slot was the only incoming slot. Estimates and reference scores remain fixed. The explicit use of slot identities correctly preserves repeated reviewer types, equal reports, and repeated profile references.
With \(R(x,y)=-(x-y)^2\), the required reward difference is
\[
\]
\(R(r,g)-R(u,g)=(u-g)^2-(r-g)^2.\)
Thus the prover’s \(B_e\) has the correct sign, and multiplying its incidence-wise sum by \(\alpha\) gives exactly \(t_a\). Repeated outgoing incidences retain their multiplicity.
The outputs \(b_a,\rho_a,s_a,f_a,t_a\) cover the requested estimates, tentative and final own-paper scores, and bonuses. The optional output \(v_a\) is already constructed.
The formula \(\overline X=\sum_a\mu_aX_a\) correctly computes each requested mean, including mean reliability. The finite-realization calculation is valid because each output is constant within a complete type and the realization contains \(n\mu_a\) students of that type.
The argument uses the realization promise only to identify the listed types, paper profiles, reports, and reciprocal slot references with their realized counterparts. Every computed quantity depends on that specified data. No reconstruction of the cyclic assignment or enumeration of students is required.
With \(M=\sum_p|H_p|\) and \(C=1+m+\tau K+M\), the claimed \(O(C)\) shared gate count is correct. Each deletion requires constant additional work after constructing the profile aggregates; each bonus incidence likewise requires constant additional work.
Input rational constants can be copied into the circuit without evaluating intermediate values. The additional integer constants have polynomial encoding length, and gate references require \(O(\log(C+1))\) bits each. Consequently, the stated circuit encoding bound \(O(L+C\log(C+1))\) is justified.
Explicit listing bounds the numbers of slots and incidences by the input length. Traversing the lists, assigning gate indices, and even using linear scans for references therefore takes polynomial bit time. Copying the shared circuit for each of the polynomially many outputs also preserves polynomial total size.
This establishes the required bound for circuit construction, without assuming unit-cost evaluation of potentially large algebraic values.
The attribution of the finite-population \(O(nK)\) bound to Theorem 3 and Appendix B.4 is accurate. The prover’s binary-input conclusion rests on its own circuit-construction argument, so no application of the paper’s theorem is needed. [PEQA paper](https://www.cse.iitb.ac.in/~swaprava/papers/peergrading.pdf).
Minor — Section 1, immediately before the definition of \(d_{a,e}\): The empty display-math block is a formatting artifact. Remove it. No mathematical clarification or additional lemma is needed.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.