{"topic":"p-vs-np","tier":"stated","total":197,"limit":50,"offset":0,"claims":[{"claim_id":2599509,"arxiv_id":"2608.12976","paper_version":1,"claim_text":"The paper's core claim is that Fortune's theorem can be made discoverable: students who know only basic programming can, in groups, find the two rules that turn an exponentially large self-reducibility tree into a polynomially large one. The first rule, drawn from the framework Fortune inherited from Berman, is to trim every node at a level whose S-label has already appeared to the left, keeping only the leftmost node for each distinct label. The second rule, Fortune's own contribution, is a pigeonhole bail-out: if a level retains more than $p(r(|F|))$ nodes after pruning, where $p$ bounds the sparse set's density and $r$ bounds the reduction's runtime, then at least one surviving node has a label outside the sparse set, which forces the root formula to be satisfiable. The paper argues that with the right scaffolding, students can reach exactly these insights, and it reports that groups often succeed partially or completely.","claim_key":"core","tier":"stated","source":"verdict_pith","method":"signals","confidence":0.85,"assigned_at":"2026-08-17T03:37:10.112263+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"Fortune's Bounty: Taming Complexity by Trimming Trees --- A Hands-On Problem-Solving Experience in Advanced Complexity Suitable for Introductory Students","paper_submitted_at":"2026-08-13T08:56:06+00:00"},{"claim_id":2604845,"arxiv_id":"2608.12955","paper_version":1,"claim_text":"The paper claims Theorem 1: LA-MAPF is PSPACE-complete. Membership in PSPACE comes from storing only the current configuration and using the classical theorem that nondeterministic polynomial space equals deterministic polynomial space, avoiding the need to store the exponentially long configuration history. Hardness comes from a polynomial-time reduction from Restricted Sliding Tokens: contract each token triangle to a macro-vertex, keep token edges as two-port wires, and route the resulting degree-at-most-three planar graph orthogonally on a grid scaled by $100r$. Each link edge becomes a wire with at most four vertices and exactly one hole; because agents cannot pass each other in the narrow corridor, the hole acts as a faithful physical transmission of the exclusion constraint, while blocking vertices near ports use disk overlap to forbid simultaneous occupation. The paper concludes that LA-MAPF remains PSPACE-complete even for plane graphs with only axis-aligned movements.","claim_key":"core","tier":"stated","source":"verdict_pith","method":"signals","confidence":0.85,"assigned_at":"2026-08-17T03:37:10.112263+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"PSPACE-Completeness of Multi-Agent Path Finding for Large Agents","paper_submitted_at":"2026-08-13T08:34:03+00:00"},{"claim_id":2231821,"arxiv_id":"2608.11181","paper_version":1,"claim_text":"On the paper's own terms, the main theorem is that Model-Consistency---given circuits $P$ and $Q$ over a query universe of size $2^{\\ell(d+1)+d}$, is there a distribution $\\mu$ over $n = 2^d$ Boolean variables with $\\mathrm{Inc}_{P,Q}(\\mu) \\le \\tau$---admits a polynomial-time interactive PCP. The verifier's protocol (Algorithm 6) runs one encoding-proximity test, two sum-checks, two marginal checks, and three direct circuit evaluations; it reads only $\\mathrm{poly}(\\ell, d, B, \\log(1/\\varepsilon_{\\mathrm{gap}}), 1/\\varepsilon_{\\mathrm{sound}})$ symbols of an oracle of length $|F|^{O(\\ell d + B)}$ and exchanges polynomially many field elements with a single untrusted prover. The oracle encodes a sparse witnessing distribution, whose existence comes from a Carathéodory argument: any consistent collection of $m$ claims has a witness supported on $m+1$ points, and the paper proves the weights can be taken rational with polynomially many bits (Proposition 8 gives logarithmic-precision weights at the cost of an additive gap; Proposition 9 places the exact version in NP with certificate length $O(mn + \\log B)$, the verifier solving for the weights itself). The completeness guarantee requires the model to be $(\\tau - \\varepsilon_{\\mathrm{gap}})$-consistent, and soundness rejects every model with inconsistency above $\\tau$ except with probability $\\varepsilon_{\\mathrm{sound}}$.","claim_key":"core","tier":"stated","source":"verdict_pith","method":"signals","confidence":0.85,"assigned_at":"2026-08-17T03:37:10.112263+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"How to Verify Consistency of Probabilistic Claims","paper_submitted_at":"2026-08-11T17:41:39+00:00"},{"claim_id":2292996,"arxiv_id":"2608.10874","paper_version":1,"claim_text":"The central claim, stated as Theorem 3 and built from Theorems 1 and 2, is that for every $k\\ge 3$, PCF $k$-colorability is NP-complete on perfect elimination bipartite graphs. The proof reduces from $k$-colorability: for $k=3$ it applies an earlier gadget construction that replaces each vertex by an even cycle with half-edges and each edge by a 2-vertex; for $k\\ge 4$ it subdivides edges, attaches pendants to each original vertex and to each clique vertex, and connects each copy $x_i$ of a vertex to a $k$-clique through common 2-neighbors $z_i^j$, then asserts that the resulting bipartite graph admits a perfect edge elimination ordering. A separate construction that adds two universal vertices to an arbitrary graph is used to prove that $\\chi_{\\mathrm{pcf}}$ cannot be approximated within $O(n^{1-\\varepsilon})$ unless P=NP. The positive half of the paper proves exact linear-time algorithms: block graphs are colored through their cut-trees with $\\omega(G)$ colors unless a cut vertex lies in two maximum cliques, proper interval graphs through a bi-compatible elimination order with $\\omega(G)$ or $\\omega(G)+1$ colors according to a similar two-maximum-cliques condition, chain graphs with at most 4 colors via nested neighborhoods, and pseudo-split graphs with $\\omega(G)+1$ colors when a $C_5$ part is present. Exact characterizations are given for when the $\\omega(G)+1$ case occurs.","claim_key":"core","tier":"stated","source":"verdict_pith","method":"phrase","confidence":0.9,"assigned_at":"2026-08-17T03:36:39.451502+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"Complexity and algorithms for proper conflict-free coloring in graphs","paper_submitted_at":"2026-08-11T12:52:28+00:00"},{"claim_id":2222884,"arxiv_id":"2608.09070","paper_version":1,"claim_text":"The paper's central claim is Theorem 1.1: every depth-4 circuit computing the n-bit Majority function requires at least $2^{n^{1/3-o(1)}}$ gates. The proof follows the three-step top-down template of the recent depth-four Parity lower bound: greedily choose a sub-circuit that maximizes the rejected zero-side set, construct a mirror set on the one-side, pass to the q-local limits, and reach a contradiction with a top clause. The new mirror-set construction uses the slice $X_1 = \\{x : \\|x\\|_0 = \\lfloor n/2 \\rfloor + m\\}$ and shifts it by a small vector $a'$ of weight at most $m^{1-\\delta}$, producing $x'$ that still lies in $Maj^{-1}(1)$. For these $x'$, the set $Y_1 - x'$ is $(m^{1+\\Theta(\\log\\log m/\\log m)}/n,\\, o(1))$-satisfying, which is exactly what lets a random block flip land in the rejected set. The proof states without loss that the circuit has an AND gate at the top, i.e. it is of type $\\wedge\\circ\\vee\\circ\\wedge\\circ\\vee$, and builds the contradiction from the size estimates at each greedy step.","claim_key":"core","tier":"stated","source":"verdict_pith","method":"signals","confidence":0.85,"assigned_at":"2026-08-17T03:37:10.112263+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"A Top-Down Depth-Four Circuit Lower Bound for Majority","paper_submitted_at":"2026-08-10T03:20:15+00:00"},{"claim_id":2354807,"arxiv_id":"2608.08993","paper_version":1,"claim_text":"The central claim is that standard derandomization hardness can replace the random oracle in proofs of space. Under the hypothesis that E=DTIME[$2^{{O(n)}}$] is hard for exponential-size nondeterministic circuits, together with a semi-universal SNARG for P, Construction 1 is sound against every time-τ prover storing at most n − C n log log n / √log n bits, with negligible accepting probability (Corollary 5); under the same derandomization assumption plus collision-resistant hash functions, a Kilian-style instantiation is sound against provers storing at most $N^{{1/c}}$ bits (Corollary 6). The proof works by showing that any prover state of size m that lets a cheating prover answer random position queries must contain enough information to reconstruct almost all of y=f(x) in time t, via an extraction lemma that uses an explicit hitting set generator to find a short sequence of “good” queries; this contradicts the assumed (t,s)-incompressibility of f.","claim_key":"core","tier":"stated","source":"verdict_pith","method":"signals","confidence":0.85,"assigned_at":"2026-08-17T03:37:10.112263+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"A Complexity-Theoretic Approach to Proofs of Space","paper_submitted_at":"2026-08-10T01:28:01+00:00"},{"claim_id":2355277,"arxiv_id":"2608.08760","paper_version":1,"claim_text":"The central discovery is that the weak rank principle WRank_m^n(A)—the family of polynomial equations ∑_k x_{i,k} y_{k,j} = A_{i,j} with m>n and rank(A)>n—admits exponential PCR_F2 refutation lower bounds that are independent of m. In the strongest bamboo-tree encoding, every refutation of BTRank_m^n(A) has size $2^{{Ω(n)}}$, for every matrix A over F2; the algebraic encoding and a perfect-matching encoding satisfy analogous bounds. Consequently the product map (X,Y) ↦ XY is a proof complexity generator from 2mn bits to $m^{2}$ bits, and an iterated tree-structured variant is a function generator with stretch $2^{{n^{Ω(1)}}$}. The same principle yields a Sherali–Adams generator via a new pseudoexpectation whose support requires linearly independent rows and columns, and, through the iterated generator, shows that PCR_F2 cannot efficiently prove statements like NP ⊈ P/poly. Finally, the paper shows WRank is needed to prove $NC^{2}$ lower bounds and that the theory V0(p)+WRank_p proves the $AC^{0}$[p] lower bound of [78].","claim_key":"core","tier":"stated","source":"verdict_pith","method":"signals","confidence":0.85,"assigned_at":"2026-08-17T03:37:10.112263+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"The Weak Rank Principle: Lower Bounds and Applications","paper_submitted_at":"2026-08-09T15:20:03+00:00"},{"claim_id":2356479,"arxiv_id":"2608.08578","paper_version":1,"claim_text":"The central claim is that three algebraically different target problems share one witness-selection skeleton with colored subgraph isomorphism, and that the correspondence is computation-free: a depth-zero projection replaces every target input bit by a constant or a negated source bit, so any circuit computing a target would compute the source at the same depth and size. For a simple pattern $P$ with $k-1$ edges the paper constructs projections $P\\text{-SUB}_N \\to k$-OV at dimension $O(k\\log n)$ with host size $N=\\lfloor\\sqrt{n}\\rfloor$, and $P\\text{-SUB}_N \\to$ odd-$k$ $k$-XOR and $P\\text{-SUB}_N \\to k$-SUM (both parities) at row or bit budgets $O(k\\log(en/k))$ with host size $N=\\lfloor\\sqrt{(n-1)/(k-1)}\\rfloor$; each projection realizes five witness roles — selection rigidity, an edge-presence guard, shared-label consistency at pattern vertices, dummy purge, and pairwise distinctness for $k$-OV — inside the target's own algebra. Combined with the published fixed-pattern lower bound for colored subgraph isomorphism, whose source exponent is the parameter $\\kappa(P)$, and with the padded expander family satisfying $\\kappa(P^{\\exp}_k) \\ge c_\\kappa(k-1)$, this yields, for every fixed depth $d$ and fixed $k$, size at least $n^{\\beta(k-1)}$ for $k$-OV and $(n/k)^{\\beta(k-1)}$ for odd-$k$ $k$-XOR and $k$-SUM, with one universal constant $\\beta$. The paper further proves a growing-$k$ floor $n^{\\Omega_d(\\min\\{\\sqrt{k},\\log n\\})}$ at every fixed depth by switching to a padded clique pattern that imports a uniform small-clique lower bound, and proves the depth-two exponent $n^{\\Omega(k)}$ for both gate orientations by direct counting: every colored copy is a distinct minimal positive input forcing one DNF term, and $2^N$ minimal transversals force distinct CNF clauses. The parity asymmetry is isolated as a selection phenomenon — $F_2$ equations cannot exclude an even-multiplicity anchor-free branch, which is why the direct $k$-XOR projection requires odd $k$, while $k$-SUM's signed large-base packing is parity-free — and the depth-three and higher-depth linear-in-$k$ statements are conditional on a pattern-uniform strengthening (Conjecture 26) that the paper does not claim to prove.","claim_key":"core","tier":"stated","source":"verdict_pith","method":"signals","confidence":0.85,"assigned_at":"2026-08-17T03:37:10.112263+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"Fine-Grained AC$^0$ Lower Bounds for $k$-OV, $k$-XOR, and $k$-SUM via Colored Subgraph Isomorphism","paper_submitted_at":"2026-08-09T08:43:25+00:00"},{"claim_id":2078306,"arxiv_id":"2608.07800","paper_version":1,"claim_text":"The paper shows that the Gaussian rounding algorithm of Makarychev and Makarychev, when combined with random assignment, satisfies every clause with probability at least alpha_k (k/2^k) ||z_C||^2, where alpha_k = 1 - O(log k/k). Summing over clauses and using the SDP upper bound on OPT gives the approximation guarantee (1 - O(log k/k)) k/2^k. This matches, asymptotically, the hardness results of Austrin–Mossel, De–Mossel, and Chan, which rule out approximations better than (1+o(1))k/2^k under UGC (and, for infinitely many k, unconditionally assuming P != NP).","claim_key":"core","tier":"stated","source":"verdict_pith","method":"phrase","confidence":0.9,"assigned_at":"2026-08-17T03:36:39.451502+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"Sharp Analysis of Gaussian Rounding for Boolean Max k-CSP","paper_submitted_at":"2026-08-07T22:45:27+00:00"},{"claim_id":1992921,"arxiv_id":"2608.06820","paper_version":1,"claim_text":"The central claim is Theorem 3.11: for every normalized Horn CNF $\\Gamma$ on variables $X$, one can construct in $O(\\|\\Gamma\\|_{\\mathrm{inc}})$ time a normalized hypergraph $C(\\Gamma)$ of rank at most three, with $L(C(\\Gamma))=O(\\|\\Gamma\\|_{\\mathrm{inc}})$, such that every false-variable set of a model of $\\Gamma$ extends uniquely to a nonempty stopping set of $C(\\Gamma)$, and this correspondence is an inclusion-order isomorphism. Equivalently, the model poset of $\\Gamma$ is isomorphic to the proper-model poset of the hypergraph Horn function $\\Phi_{C(\\Gamma)}$, so maximal models map bijectively to coatoms. The representation transfers the maximal-Horn-model lower bound of Kavvadias, Sideri, and Stavropoulos: enumerating coatoms from a hypergraph incidence list is not in OutputP unless P=NP, even when every hyperedge has size two or three; after incidence splitting, the same lower bound holds with maximum element frequency at most three, and a local replacement makes the hard hypergraphs three-uniform. The paper also proves the matching positive endpoints: rank at most two and maximum element frequency at most two admit output-linear total-time enumeration, with a polynomial-delay, polynomial-space algorithm in the frequency-two case, while coatom extension is NP-complete already for three-uniform hypergraphs in which every element has frequency exactly two.","claim_key":"core","tier":"stated","source":"verdict_pith","method":"phrase","confidence":0.9,"assigned_at":"2026-08-17T03:36:39.451502+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"Coatom Enumeration in Hypergraph Horn Functions: Rank-Three Representations of Horn Model Posets","paper_submitted_at":"2026-08-07T05:20:16+00:00"},{"claim_id":1819514,"arxiv_id":"2608.05613","paper_version":1,"claim_text":"The central claim is Theorem 6: the aggregate language MIS belongs to NP but not to P. On the paper's own terms, MIS accepts a valid aggregate tuple $U_i = (u_1, \\dots, u_m)$ over a stage domain $D_i$ exactly when at least one component is accepted by the stage language $C_i$. The non-P direction runs through the Bridge Theorem: a polynomial-time decider for MIS would let one construct, for every stage $i$, a machine $G(i)$ that decides $C_i$ by padding the input with inert sentinels and calling the decider; the Slice Theorem guarantees $L(G(i)) = C_i$. This is asserted to contradict the Predictor Impossibility Theorem, which says no machine $P_k$ can satisfy $L(P_k) = C_k$. The NP direction supplies the accepting component as a witness, verified in $O(q \\log q)$ steps under the paper's runtime and aggregate growth assumptions.","claim_key":"core","tier":"stated","source":"verdict_pith","method":"signals","confidence":0.85,"assigned_at":"2026-08-17T03:37:10.112263+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"Predictor-Impossibility Theorem and Applications","paper_submitted_at":"2026-08-06T05:25:33+00:00"},{"claim_id":1829307,"arxiv_id":"2608.05468","paper_version":1,"claim_text":"The central claim is Theorem 1.1: for every $\\varepsilon\\in(0,1)$, assuming P≠NP, no polynomial-time algorithm approximates A-design or E-design under partition constraints within factor $2^{poly(d)+(1-\\varepsilon)B}$. The reduction builds $d=m+n+1$ dimensions and a partition matroid with $d$ singleton-or-pair parts; bases correspond exactly to 0/1 vectors $x$ indexed by triples. A perfect three-dimensional matching exists iff $Ax=\\mathbf{1}_m$, and the gadget embeds the residual vector $R^2(Ax-\\mathbf{1}_m)$ as a block of $V_x^{-1}$. Thus yes-instances have $A(x)\\le 2dR^2$ while no-instances have $E(x)\\ge R^4$, giving a separation ratio $R^2/(2d)$ that is tuned to be exponential in $B$.","claim_key":"core","tier":"stated","source":"verdict_pith","method":"phrase","confidence":0.9,"assigned_at":"2026-08-17T03:37:10.112263+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"Hardness of A/E-Design under Partition Constraints","paper_submitted_at":"2026-08-05T23:33:19+00:00"},{"claim_id":1832334,"arxiv_id":"2608.05431","paper_version":1,"claim_text":"On the paper's own terms, the central claim is a uniform 'one algebra, many classes' theorem family. Starting from $\\mathrm{ACDL} = \\mathrm{FAC}^0$, the schemas $\\mathrm{ODE}^{\\lor}$ (existential bounded search), $\\mathrm{ODE}^{\\land}$ (universal bounded search), and $\\mathrm{ODE}^{\\#}$ (summation) are the only ingredients needed to move up the polynomial and counting hierarchies: Theorem 5 states $\\mathrm{PH} \\equiv \\mathrm{SDL} = [\\mathrm{ACDL}; \\circ, \\mathrm{ODE}^{\\lor}]$ with $\\Sigma^p_{n+1} \\equiv [\\mathrm{SDL}_n; \\circ_0, \\mathrm{ODE}^{\\lor}]$, and Theorem 6 states $\\mathrm{FCH} \\equiv \\mathrm{CDL} = [\\mathrm{ACDL}; \\circ, \\mathrm{ODE}^{\\#}]$ with $\\mathrm{FCH}_{n+1} = [\\mathrm{CDL}_n; \\circ_0, \\mathrm{ODE}^{\\#}]$. Theorem 7 gives $\\mathrm{FMod}_m\\mathrm{P} \\cup \\mathrm{FAC}^0 = [\\mathrm{ACDL}; \\circ_0, \\mathrm{ODE}^{\\mathrm{cmod}\\text{-}m}]$, Theorem 9 gives $\\mathrm{FPSPACE} = [B; \\circ, \\ell\\text{-}\\mathrm{ODE}^1, \\mathrm{bODE}]$, and Theorem 11 gives $\\mathrm{FP} = [\\mathrm{ACDL}; \\circ, \\ell\\text{-}\\mathrm{ODE}^1]$. The unified mechanism is that an $\\mathrm{FAC}^0$ function recognizes accepting computation paths of a machine, and the ODE schemas then search over or count those paths, with linearity restrictions keeping the search or count bounded.","claim_key":"core","tier":"stated","source":"verdict_pith","method":"signals","confidence":0.85,"assigned_at":"2026-08-17T03:37:10.112263+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"Towards a Characterization of Counting and Alternating Classes via Discrete Ordinary Differential Equations","paper_submitted_at":"2026-08-05T21:54:03+00:00"},{"claim_id":1397449,"arxiv_id":"2608.05029","paper_version":1,"claim_text":"Relative to a random oracle $H$, the countable collection $\\mathcal C^*$ of graph languages $L_b=\\{\\langle\\lambda,i,H(b,i)\\rangle:i\\in\\mathbb N\\}$, with $b\\in\\{0,1\\}^\\lambda$, has closure dimension zero almost surely. On that same oracle an unbounded generator makes zero mistakes on every target $L_b$ under every complete distinct enumeration, the empty-history output being secured by an infinite all-row agreement among the $2^\\lambda$ seeds of a length. Yet every uniform polynomial-query oracle generator $G$ has a constant $c_G>0$ such that at all sufficiently large $\\lambda$ some seed $b$ incurs $\\mathbb E_G[\\mathrm{mist}_{<W_G(\\lambda)}(G,L_b,\\sigma_b)]>2^{c_G\\lambda}$ expected mistakes within $W_G(\\lambda)=2(\\lceil 2^{c_G\\lambda}\\rceil+1)$ outputs under the canonical enumeration; Section 4 extends this to every precommitted index schedule. The exponential floor is not eventual failure: it is the cumulative cost of searching for fresh target values before an efficient generator can find them.","claim_key":"core","tier":"stated","source":"verdict_pith","method":"signals","confidence":0.85,"assigned_at":"2026-08-17T03:37:10.112263+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"On Computational Hardness of Mistake-Bounded Language Generation: A Random-Oracle Query Separation","paper_submitted_at":"2026-08-05T16:34:12+00:00"},{"claim_id":1424933,"arxiv_id":"2608.04883","paper_version":1,"claim_text":"On its own terms, the paper proves Theorem 1.1: there is no polynomial-time algorithm that always returns a cluster deletion set within a factor of $\\sqrt{2}-\\epsilon$ of optimal unless P = NP, and no algorithm within a factor of $2-\\epsilon$ unless the Unique Games Conjecture is false. These match the existing 2-approximation, so the approximation threshold for Cluster Deletion coincides with that of Vertex Cover. The engine is an approximation-preserving reduction showing that any c-approximation for Cluster Deletion on N-vertex graphs yields a c-approximation for Vertex Cover on n-vertex graphs with $N = O(c' n^2)$. The reduction encodes a Vertex Cover instance in the complement graph, joins it with a large clique of universal vertices, and shows that an optimal cluster deletion set must keep the universal vertices together with a maximum clique of the complement, so its cost is governed by the vertex cover number. A secondary result answers an open question by exhibiting a 31-vertex unweighted graph whose Cluster Editing optimum strictly exceeds its Bad Triangle Transversal optimum, so the two objectives are not identical.","claim_key":"core","tier":"stated","source":"verdict_pith","method":"phrase","confidence":0.9,"assigned_at":"2026-08-17T03:36:39.451502+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"Cluster Deletion is as Hard to Approximate as Vertex Cover","paper_submitted_at":"2026-08-05T14:08:53+00:00"},{"claim_id":1425985,"arxiv_id":"2608.04871","paper_version":1,"claim_text":"The paper's central claim is that a new operation, bounded step recursion along the generalized inverse of a fixed increasing function, produces a three-parameter hierarchy $H^m_{n,l}$ refining the Grzegorczyk hierarchy, and that for $n,n'\\ge2$ the inclusion order is completely classified by Theorem 56: $$H^a_{n,l}\\subseteq H^b_{n',l'} \\iff a\\le b \\text{ and } \\begin{cases} \\text{no further condition}, & n>n',\\\\ b\\ge n \\text{ or } l'\\mid l, & n=n',\\\\ b\\ge n'+1, & n<n'. \\end{cases}$$ The equal-row case is the paper's striking point: below the collapse threshold the strides are ordered by reverse divisibility, so $H^m_{n,6}\\subseteq H^m_{n,2}$ and $H^m_{n,6}\\subseteq H^m_{n,3}$ while strides 2 and 3 are incomparable. The paper further claims that row zero coincides with the ordinary classes $E^m$, that for the doubling row $g_1(x)=2x+1$ one has $H^m_{1,l}=E^m$ for every $m\\ge3$, that the first vertical bridge $H^2_{2,*}\\subsetneq H^2_{1,*}$ holds at basis 2, and that $H^2_{1,l}\\subsetneq FP$ with $H^2_{1,l}=E^2$ implying $P=NP$.","claim_key":"core","tier":"stated","source":"verdict_pith","method":"phrase","confidence":0.9,"assigned_at":"2026-08-17T03:36:39.451502+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"Step Recursion: A Three-Parameter Refinement of the Grzegorczyk Hierarchy","paper_submitted_at":"2026-08-05T14:01:07+00:00"},{"claim_id":1594731,"arxiv_id":"2608.04484","paper_version":1,"claim_text":"The central claim is that parity-based bit-counting classes B_{|0|⊕P} and B_{|1|⊕P} are Turing-equivalent to PP in the deterministic polynomial-time setting: P^PP = $P^{{B_{|0|⊕P}}$} = $P^{{B_{|1|⊕P}}$}. The paper proves this by showing a deterministic polynomial-time machine with either oracle can recover all bits of any #P value A(x). The recovery pads A(x) to X(x)=2^n + A(x), and for each bit position r queries the parity of the bit-count sequences at X(x)+j2^r for j=0,1,2,3; the four consecutive value theorem for the sequences s and t turns these answers into one bit of the quotient Q_r(x)=⌊X(x)/2^r⌋. Since deciding a language in PP reduces to comparing A(x) against $2^{{p(|x|)-1}}$, recovering A(x) puts PP inside both oracle classes, and the same recovery puts #P inside $FP^{{B_{|0|⊕P}}$} and $FP^{{B_{|1|⊕P}}$}.","claim_key":"core","tier":"stated","source":"verdict_pith","method":"signals","confidence":0.85,"assigned_at":"2026-08-17T03:37:10.112263+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"Even more properties of parity based bit-counting complexity classes","paper_submitted_at":"2026-08-05T06:17:41+00:00"},{"claim_id":2523483,"arxiv_id":"2608.01256","paper_version":1,"claim_text":"On the paper's own terms, the discovery is that identical numerical catalogues do not eliminate the hardness of numerical three-dimensional matching. A unary polynomial reduction replaces the three asymmetric source classes by three labeled copies of one weighted occurrence set, then forces, through a finite role filter and degree equations, exactly one main incidence per port; those main incidences re-encode the original matching. For the optimization version, the paper claims a quantitative reverse implication—$13n-d$ symmetric triples yield at least $n-21d$ source triples—which transfers a hard perfect-completeness gap to Max-SN3DM. For standard approximation-preserving hardness, the paper claims an exact affine optimum identity $\\mathrm{OPT}_{\\mathrm{SN}} = 36m + r + \\mathrm{OPT}_{\\mathrm{3DM}}$ on a deliberately separated image family, yielding an L-reduction with $\\alpha=764$, $\\beta=1$ and hence APX-completeness. The intended moral is that symmetry of the input data is a red herring for tractability.","claim_key":"core","tier":"stated","source":"verdict_pith","method":"signals","confidence":0.85,"assigned_at":"2026-08-17T03:37:10.112263+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"Symmetric Numerical Three-Dimensional Matching: Intractability and Inapproximability","paper_submitted_at":"2026-08-02T14:06:22+00:00"},{"claim_id":1362521,"arxiv_id":"2608.01059","paper_version":1,"claim_text":"Frank's formula relates the largest join of a connected graphic matroid to the minimum number of even lobes in an ear decomposition: $\\mu(M)=\\eta(M)$, where $\\eta(M)=(r(M)+\\varphi(M))/2$. The paper establishes that this exact identity is a graphic phenomenon. It fails for cographic matroids—the dual of $K_{4,4}$ has $\\mu=4$ but $\\eta=5$—and the two parameters can go in either direction in general. Algorithmically the join side is hard: maximum join is NP-hard for cographic matroids, inapproximable within $519/520$ unless P = NP, and NP-hard for sparse paving matroids given by their bases. The main positive theorem is that the parameters remain quantitatively locked on regular matroids: for e","claim_key":"core","tier":"stated","source":"verdict_pith","method":"phrase","confidence":0.9,"assigned_at":"2026-08-17T03:36:39.451502+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"Joins and ear decompositions beyond graphic matroids","paper_submitted_at":"2026-08-02T07:51:24+00:00"},{"claim_id":1362545,"arxiv_id":"2608.00958","paper_version":1,"claim_text":"The paper's central claim, stated in its own terms, is that a single argument shape — locate the silent assumption behind an accepted result, promote it to a variable, and prove what happens once it is allowed to vary — recurs across cryptography, the semantics of derivations, special relativity, the space of physical laws, and algorithmic randomness, and that in one instance it produces a contradiction forcing $\\mathsf{P}\\neq\\mathsf{NP}$. Its formal core is the Dynamic Syntactic Invariance Principle: if a dynamic rewriting system is generated by an opacity-preserving update — one that keeps the Skolem constants $a,b$ untouched at every step and that, when $a$ and $b$ are swapped throughout","claim_key":"core","tier":"stated","source":"verdict_pith","method":"signals","confidence":0.75,"assigned_at":"2026-08-17T03:37:10.112263+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"What Syntax Cannot See: The Dynamic Syntactic Invariance Principle and Several Instances of the Same Hidden Assumption, and a Contradiction","paper_submitted_at":"2026-08-02T03:10:44+00:00"},{"claim_id":1127522,"arxiv_id":"2608.00283","paper_version":1,"claim_text":"The central discovery is that the function classes defined by median outputs and by k-th outputs (or witnesses) coincide up to a single adaptive oracle query: FP^#P equals FP^C[1] for every C among the multiplicity median class MedP, the set median class MidP, the witness median class MedP, and the corresponding k-th output classes KthWitness(FP), KthWitness(FP^#P), KthOutput(FP), KthOutput(FP^#P), KthOutput_seq(FP), and KthOutput_seq(FP^#P). For the witness-median class MedP, it proves the outright equality MedP = MaxMCP = KthOutput_seq(FP) = KthOutput_seq(#P), not just Turing equivalence. It also gives language-class characterizations: NPSV_t ⊆ MaxP ⊆ FP^NP with properness iff NP ≠ coNP, a","claim_key":"core","tier":"stated","source":"verdict_pith","method":"signals","confidence":0.85,"assigned_at":"2026-08-17T03:37:10.112263+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"On the Complexity of Computing Outputs of a Metric Turing Machine","paper_submitted_at":"2026-07-31T20:41:40+00:00"},{"claim_id":1051402,"arxiv_id":"2607.29576","paper_version":1,"claim_text":"An annulment structure numbers distinctions with a semidecidable manifestation predicate; an adjudicator annuls, exempts, or stays silent on each. The core result is a trichotomy: a fixed computable map d produces, for every index a, a distinction δ_a that manifests exactly when a annuls it, so every adjudicator fails exactly one of totality, exhaustiveness, or soundness at that point. Adding one nullary 'ask' gate—a construct by which a distinction queries the verdict on the system containing it—makes the same trichotomy uniform: one fixed distinction defeats every adjudicator, and no decidable domain that is ask-closed for its own correct total adjudicator exists (Theorem 4.7). Bounded sel","claim_key":"core","tier":"stated","source":"verdict_pith","method":"signals","confidence":0.8,"assigned_at":"2026-08-17T03:37:07.768278+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"The gate of self-address: where decidable adjudication ends","paper_submitted_at":"2026-07-31T16:03:03+00:00"},{"claim_id":1065715,"arxiv_id":"2607.29386","paper_version":1,"claim_text":"The central claim is Theorem 1: for any instance of MIQP whose objective is bounded below on the feasible region and any rational epsilon in (0,1], there is a Turing-machine algorithm that either proves infeasibility or finds an epsilon-approximate solution in time polynomial in the instance size, size(epsilon), and 1/epsilon, provided p and k_- are fixed. The paper also proves that, unless P=NP, fixing both p and k_- is necessary: allowing p to grow would decide integer feasibility in polynomial time, and allowing k_- to grow would solve 3SAT in polynomial time already with p=0. The algorithmic novelty is a rational simultaneous diagonalization: a rational nonsingular change of basis that m","claim_key":"core","tier":"stated","source":"verdict_pith","method":"phrase","confidence":0.9,"assigned_at":"2026-08-17T03:36:39.451502+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"Rational Jacobi Rotations and the Complexity of Approximating Mixed Integer Quadratic Programming","paper_submitted_at":"2026-07-31T13:06:43+00:00"},{"claim_id":902824,"arxiv_id":"2607.27277","paper_version":1,"claim_text":"The paper establishes Theorem 1.1: Ashg-Strong-Popularity is PCW-complete. The membership direction is argued by encoding each agent's additive utility as a Boolean circuit, reducing the problem to Ckt-Condorcet. The hardness direction constructs an ASHG from an arbitrary Ckt-Condorcet instance, using assignment, gate, and And-gadgets with one-way replicas that serve as weight multipliers, so that a partition is strongly popular if and only if the corresponding string is a Condorcet winner.","claim_key":"core","tier":"stated","source":"verdict_pith","method":"signals","confidence":0.85,"assigned_at":"2026-08-17T03:37:07.768278+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"Complexity of Strong Popularity in Additively Separable Hedonic Games","paper_submitted_at":"2026-07-29T12:59:05+00:00"},{"claim_id":867172,"arxiv_id":"2607.25723","paper_version":1,"claim_text":"The paper's central claim is the parameterized classification depicted in its Figure 1. For GreedyAV and GreedyCost, destructive control by deleting projects is W[1]-hard when parameterized by the number $r$ of deleted projects or by the number $q$ of unaffected projects, even if there are only $n=2$ voters, and constructive control by deleting projects is W[1]-hard for $r$ even with $n=3$ voters. In contrast, both constructive and destructive deletion control are fixed-parameter tractable for the combined parameter $c+n$, where $c$ is the number of distinct project costs and $n$ the number of voters, provided ties are broken so that projects of equal score and equal cost are processed consecutively (e.g., cheaper-first); the same problems are FPT for $c+r$ and for $q+c$ without that tie-breaking condition, and XP when parameterized by $c$ alone. For the optimization versions of deletion control, no polynomial-time algorithm can achieve an approximation factor of $m^{1-\\epsilon}$ for any $\\epsilon>0$ unless P=NP, and an $m/c$-approximation always exists, making the bound essentially tight. The broader claim, covering addition of projects as well, is that the trivial XP and FPT observations for the number of projects $m$, the number of controlled projects $r$, and the number of unaffected projects $q$ cannot be improved in general, but combined cost-structure parameters unlock exact algorithms.","claim_key":"core","tier":"stated","source":"verdict_pith","method":"phrase","confidence":0.9,"assigned_at":"2026-08-17T03:36:39.451502+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"Algorithms for Candidate Control in Greedy Participatory Budgeting Rules","paper_submitted_at":"2026-07-28T13:48:39+00:00"},{"claim_id":897809,"arxiv_id":"2607.20804","paper_version":1,"claim_text":"The central claim is Theorem 4: for any circuit architecture satisfying the standard average-case #P-hardness conjecture for ideal RCS, no polynomial-time classical sampler can approximately simulate noisy RCS within inverse-polynomial total variation distance at local depolarizing noise strength γ* = O(log n/(nd)), unless the polynomial hierarchy collapses to a finite level. The hardness is inherited from the ideal case without any additional conjectural or architecture-specific assumption. The supporting results are Theorem 2, which shows that estimating noisy output probabilities at input noise strengths γ ∈ [γ*, 1] is #P-hard when γ* = O(log n/(nd)), and Theorem 3, a monotonicity reducti","claim_key":"core","tier":"stated","source":"verdict_pith","method":"signals","confidence":0.8,"assigned_at":"2026-08-17T03:37:07.768278+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"Hardness and Complexity Transition of Noisy Random Circuit Sampling","paper_submitted_at":"2026-07-23T00:23:18+00:00"},{"claim_id":910248,"arxiv_id":"2607.19573","paper_version":1,"claim_text":"The central claim is that structural generalization, once defined as unbounded evaluation of a finite compositional rule system, is not learnable by a pure Transformer. The argument splits each compositional rule into a syntactic face and a semantic face. The semantic face is bottom-up tree evaluation, which encodes the Boolean Formula Value Problem and is therefore NC¹-hard. The learnability ceiling for chain-of-thought Transformers under finite alphabets is TC⁰. Under the standard conjecture TC⁰ ≠ NC¹, the two classes are disjoint, so the true compositional evaluation function lies outside what any pure Transformer can learn with length generalization. What a Transformer can produce is a '","claim_key":"core","tier":"stated","source":"verdict_pith","method":"signals","confidence":0.8,"assigned_at":"2026-08-17T03:37:07.768278+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"On the Computational Complexity of Structural Generalization","paper_submitted_at":"2026-07-21T21:00:32+00:00"},{"claim_id":923039,"arxiv_id":"2607.18168","paper_version":1,"claim_text":"The paper establishes that the expander-based INW generator with spectral expansion λ = ε/(32w^3) is an ε-PRG for permutation read-once branching programs of length n and width w, with seed length O((log(1/ε) + log w)·log n). The proof works by defining, for each interval of the program, a forward weight and a backward weight that measure how much the program's layers mix test vectors. The central estimate shows the error of one seed-recycling step is bounded by the product of the forward and backward weights times the expander's spectral expansion, and an induction then shows the total error stays bounded by O(λ) times the product of the total forward and backward weights, each at most 2w t","claim_key":"core","tier":"stated","source":"verdict_pith","method":"signals","confidence":0.85,"assigned_at":"2026-08-17T03:37:07.768278+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"A Forward-Backward Weight Analysis of INW for Permutation Branching Programs","paper_submitted_at":"2026-07-20T17:11:02+00:00"},{"claim_id":946934,"arxiv_id":"2607.15881","paper_version":1,"claim_text":"For every listed function, the paper constructs a verifier machine that reads the input in unary, reads a witness string once from left to right, and accepts exactly the intended set of objects (subsets, Dyck paths, domino sequences, ballot sequences, partitions, tableaux, or a compressed representation of them). The main technical novelty is the treatment of the hook-length formula: using Legendre's formula and p-adic valuations, the rational formula for #SYT(λ) is rewritten as a product over primes of p^{v_p(n!) - v_p(hooks)}, and each exponent is shown to be log-space computable, so the whole count is in #L even for unbounded shapes. The deepest result is the log²-space verifier for Hermi","claim_key":"core","tier":"stated","source":"verdict_pith","method":"signals","confidence":0.85,"assigned_at":"2026-08-17T03:37:07.768278+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"Counting in logarithmic space","paper_submitted_at":"2026-07-17T11:50:18+00:00"},{"claim_id":961490,"arxiv_id":"2607.14375","paper_version":1,"claim_text":"The central claim is Theorem 1: if there existed a sound and complete exact algorithm whose expected bit-running time is polynomial in network size, bit complexity, and inverse noise level for every adversarial base instance with 2^{-B} ≤ σ, then NP ⊆ BPP. Equivalently, under NP not in BPP, no such verifier exists. The result already holds for one-hidden-layer ReLU networks on the unit box, hidden fan-in at most three, base coefficients in [-1,1], 4m+1 hidden units, and fixed noise σ⋆ = 2^{-11}. The engine is an exact gap embedding: every E3SAT formula Φ with m clauses maps to a network satisfying max_{x∈[0,1]^n} g_Φ(x) = (m-unsat(Φ))/3, and coordinatewise threshold rounding never decreases","claim_key":"core","tier":"stated","source":"verdict_pith","method":"signals","confidence":0.85,"assigned_at":"2026-08-17T03:37:07.768278+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"Random Parameter Noise Does Not Make Exact ReLU Verification Easy","paper_submitted_at":"2026-07-15T21:26:20+00:00"},{"claim_id":968692,"arxiv_id":"2607.13540","paper_version":1,"claim_text":"The central claim is that, under the assumptions that the base theory T is true and contains enough arithmetic, that (A,B) is a NIWI pair, and that a p-time sequence of tautologies Ψ is hard for the proof system P(T*), the prover Prover[A,B,Ψ] is ZK relative to T. Concretely, for every c,e ≥ 1 and all sufficiently large n, there is no T-proof of size at most n^e of the sentence asserting that no circuit of size at most n^d is a simulator for the prover. The proof uses a model-theoretic equivalence: if Ψ is not provable in P(T*), then a non-standard model can be extended to one where Ψ is false, and in that extension a simulator circuit can be built. The paper also proves that this definition","claim_key":"core","tier":"stated","source":"verdict_pith","method":"signals","confidence":0.85,"assigned_at":"2026-08-17T03:37:07.768278+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"A proof complexity perspective on effectively zero-knowledge proofs","paper_submitted_at":"2026-07-15T07:43:08+00:00"},{"claim_id":776617,"arxiv_id":"2607.09963","paper_version":1,"claim_text":"There is a language in smart-E^{prMA}/1 that requires Boolean circuits of size Ω(2^n/n). Equivalently, there is an infinitely-often smart FP^{prMA}/1 algorithm that, given any polynomial-size circuit C:{0,1}^n → {0,1}^{n+1}, outputs a string outside the range of C.","claim_key":"core","tier":"stated","source":"verdict_pith","method":"signals","confidence":0.85,"assigned_at":"2026-08-17T03:37:07.768278+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"Near-Maximum Circuit Lower Bounds for Exponential Time with Merlin-Arthur Queries","paper_submitted_at":"2026-07-10T20:33:08+00:00"},{"claim_id":659214,"arxiv_id":"2607.08559","paper_version":1,"claim_text":"Access to catalytic memory that must be restored to its initial state enables exact multi-pass streaming algorithms for every frequency moment F_k that use only O(k log m) clean space, and therefore also exact induced-subgraph counting for any fixed pattern using O_H(log n) clean space; the same resource is useless for one-pass algorithms.","claim_key":"core","tier":"stated","source":"verdict_pith","method":"signals","confidence":0.8,"assigned_at":"2026-08-17T03:37:07.768278+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"Computing over Data Streams using Catalytic Space","paper_submitted_at":"2026-07-09T14:51:52+00:00"},{"claim_id":164,"arxiv_id":"2607.06956","paper_version":1,"claim_text":"The paper's central claim is that a language MIS can be shown to lie in NP but not in P, by connecting a recursion-theoretic impossibility result (no effective predictor family for an activation hierarchy, proved via Kleene's Recursion Theorem) to a complexity-theoretic bridge (a polynomial-time decider for the aggregate language MIS would produce such a predictor family). The activation operator Φ is the key mechanism: it defines stage languages as the complement of machine languages within their domains, and this semantic linkage between a machine and its own language creates the self-referential structure that the diagonal argument exploits.","claim_key":"core","tier":"stated","source":"verdict_pith","method":"signals","confidence":0.85,"assigned_at":"2026-08-17T03:37:07.768278+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"Fixed Points, a Predictor-Impossibility Theorem, and Applications","paper_submitted_at":"2026-07-08T03:31:15+00:00"},{"claim_id":1216,"arxiv_id":"2607.05944","paper_version":1,"claim_text":"There exists an explicit Boolean function f on n variables such that every read-once parity branching program computing f has size Õ(Ω(n^{2})). The previous best lower bound was Õ(Ω(n^{1.5})). The proof proceeds by reduction to a lower bound in algebraic circuit complexity.","claim_key":"core","tier":"stated","source":"verdict_pith","method":"signals","confidence":0.85,"assigned_at":"2026-08-17T03:37:07.768278+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"A Lower Bound for Read-Once Parity Branching Programs","paper_submitted_at":"2026-07-07T07:43:30+00:00"},{"claim_id":687457,"arxiv_id":"2607.04027","paper_version":1,"claim_text":"When the number of allowed offers is known in advance, any set of buyer-price pairs should be executed in decreasing-price order; under that canonical order the expected-revenue objective becomes monotone and submodular subject to a partition matroid, so continuous greedy plus pipage rounding yields a (1-1/e)-approximation that is optimal unless P=NP. Parallel constant-factor and logarithmic-factor algorithms are obtained for random horizons by imposing reverse-time submodular order, solving a mixed-integer upper bound and attenuating it, or taking the best of many deterministic greedy solutions.","claim_key":"core","tier":"stated","source":"verdict_pith","method":"phrase","confidence":0.9,"assigned_at":"2026-08-17T03:36:39.451502+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"Sequential Pricing with Deadlines and Correlated Buyers","paper_submitted_at":"2026-07-04T20:53:58+00:00"},{"claim_id":687785,"arxiv_id":"2607.07723","paper_version":1,"claim_text":"Any admissible generator-verifier pair for a non-trivial semantic property of programs induces a total Turing-computable decider for that property; Rice's theorem therefore rules out every such pair. Applied to the two semantic properties that would constitute a formal settlement of P versus NP (or of cryptographic hardness), this yields the Double Bind: no admissible method settles either direction inside the standard Turing model.","claim_key":"core","tier":"stated","source":"verdict_pith","method":"phrase","confidence":0.9,"assigned_at":"2026-08-17T03:37:07.768278+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"Limits of Uniform Certification in the Standard Turing Model -- Semantic Invariants and Admissible Methods","paper_submitted_at":"2026-07-04T18:17:36+00:00"},{"claim_id":17937,"arxiv_id":"2607.00878","paper_version":1,"claim_text":"We present an algorithm for Parallel Task Scheduling that achieves an approximation ratio of (4/3)OPT + p_max with running time O(n log n). For Multiple Cluster Scheduling we improve the running time of the 2-approximation and generalize the 9/4 approximation to arbitrary numbers of clusters. The 2-approximation for MCS is tight since one cannot hope for an approximation ratio better than 2 unless P=NP.","claim_key":"core","tier":"stated","source":"verdict_pith","method":"phrase","confidence":0.9,"assigned_at":"2026-08-17T03:36:39.451502+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"Improved Approximation Algorithms for Parallel Task Scheduling and Multiple Cluster Scheduling","paper_submitted_at":"2026-07-01T12:43:36+00:00"},{"claim_id":626842,"arxiv_id":"2606.31370","paper_version":1,"claim_text":"Witness complexity gam(x) is defined as the minimum running time over near-shortest descriptions of x on a universal Turing machine. The paper proves that low KC can coexist with high gam, with invariance up to polynomial factors, a conditional separation assuming P ≠ NP, an unconditional lower bound from the incomputability of KC, a biconditional characterization of P = NP via gP, and polynomial-time tractability for structured NP families. This positions gam as a metric for the usability of keys and certificates in time-bounded protocols.","claim_key":"core","tier":"stated","source":"verdict_pith","method":"phrase","confidence":0.9,"assigned_at":"2026-08-17T03:37:05.666359+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"Witness Complexity of Short Descriptions: A Cryptographic Perspective","paper_submitted_at":"2026-06-30T09:02:35+00:00"},{"claim_id":483956,"arxiv_id":"2606.27139","paper_version":1,"claim_text":"This work makes the implicit full-observation assumption explicit in Impagliazzo's five worlds and relaxes it via the observational axis. It proves the collapse P^{O_prof} = NP^{O_prof} ⊂ P holds unconditionally in every one of the five worlds, establishing that observational blindness and computational hardness are independent. The paper defines the Observer World W_O, classifies all world-observer pairs, identifies labeled cells, and introduces the parametric family W_O^ε for partial violations of observational invariants.","claim_key":"core","tier":"stated","source":"verdict_pith","method":"signals","confidence":0.8,"assigned_at":"2026-08-17T03:37:05.666359+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"The Observer World: A Cryptographic Extension of Impagliazzo's Five Worlds","paper_submitted_at":"2026-06-25T15:13:44+00:00"},{"claim_id":550178,"arxiv_id":"2606.04257","paper_version":1,"claim_text":"The paper's central claim is a proposed exact converse to a known proof-complexity mechanism. It is known that if a weak base theory EA proves Con_S→Con_{S+φ}, then S has polynomial-size proofs of Con_{S+φ}(n), i.e., S simulates S+φ. The paper's Higher Relative Consistency (HRC) / Feasible Reflection principle asserts the converse: no polynomial-size proof family for a true extension exists without such an EA-level explanation. Specializing to φ being a true statement 'x∈R' (x is Kolmogorov-random), this becomes Kolmogorov Hardness (KH): a sound theory cannot efficiently prove consistency of adjoining an inaccessible random fact. The paper then shows that finite-scale and hierarchy-level str","claim_key":"core","tier":"stated","source":"verdict_pith","method":"signals","confidence":0.85,"assigned_at":"2026-08-17T03:37:05.666359+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"Hardness as an Information Constraint: A Unifying Meta-Complexity Assumption","paper_submitted_at":"2026-06-02T22:18:38+00:00"},{"claim_id":556198,"arxiv_id":"2606.02408","paper_version":1,"claim_text":"MSA-S-DEC is NP-complete for a broad class of fixed pairwise string scoring schemes, and MSA-S-OPT(lambda) admits no PTAS even for k=2 under the canonical unit scheme unless P=NP.","claim_key":"core","tier":"stated","source":"verdict_pith","method":"phrase","confidence":0.9,"assigned_at":"2026-08-17T03:36:39.451502+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"Structure-Informed Multiple Sequence Alignment: A Formal Model and Hardness Results","paper_submitted_at":"2026-06-01T15:52:22+00:00"},{"claim_id":596438,"arxiv_id":"2605.25100","paper_version":1,"claim_text":"The feasibility problem of k-level LP is Σ^p_{k-1}-complete for k ≥ 2. Without linking constraints and unbounded variables, it is polynomial-time solvable for k ≤ 4 but becomes Σ^p_{k-1}-complete for k ≥ 5. The existence of an optimal solution is DP-complete when k=2 and Δ^p_k-complete for k ≥ 3; without linking constraints it remains polynomial for k ≤ 3 but Δ^p_k-complete thereafter. Computing the optimal objective value is FΔ^p_k-complete for every k ≥ 2, even without linking constraints or bounded variables. These thresholds imply that polynomial-time Turing reductions from coupled to uncoupled bilevel instances cannot exist unless P=NP, while such reductions do exist for all k ≥ 5.","claim_key":"core","tier":"stated","source":"verdict_pith","method":"phrase","confidence":0.9,"assigned_at":"2026-08-17T03:36:39.451502+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"Price of Coupling in Multilevel Linear Programming","paper_submitted_at":"2026-05-24T14:30:03+00:00"},{"claim_id":275722,"arxiv_id":"2605.13488","paper_version":1,"claim_text":"We prove that the Gallai Vertex Problem is Θ₂^p-complete via a polynomial-time reduction from a known complete problem for the class. Consequently the longest-path transversal number—the minimum size of a vertex set hitting all longest paths—cannot be approximated in polynomial time within a factor better than 2 unless P=NP. For any constant C, if graphs with transversal number C exist then no polynomial-time algorithm approximates the number to a factor better than C unless P=NP; analogous statements hold for longest-cycle transversals.","claim_key":"core","tier":"stated","source":"verdict_pith","method":"phrase","confidence":0.9,"assigned_at":"2026-08-17T03:36:39.451502+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"The Gallai Vertex Problem is $\\Theta_2^p$-Complete","paper_submitted_at":"2026-05-13T13:14:10+00:00"},{"claim_id":250906,"arxiv_id":"2605.10010","paper_version":1,"claim_text":"We give an approximation algorithm for this problem on satisfiable instances and show that it is optimal for certain S assuming P≠NP. This natural predicate is one of the very few known predicates that are approximation resistant on almost satisfiable instances, assuming P≠NP, but admits a non-trivial approximation algorithm on satisfiable instances.","claim_key":"core","tier":"stated","source":"verdict_pith","method":"phrase","confidence":0.9,"assigned_at":"2026-08-17T03:36:39.451502+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"Optimal Inapproximability of Generalized Linear Equations over a Finite Group","paper_submitted_at":"2026-05-11T05:36:16+00:00"},{"claim_id":119200,"arxiv_id":"2604.27787","paper_version":1,"claim_text":"The central claim is that simulation between arithmetic theories is governed by relative consistency as provable in the weak base theory Elementary Arithmetic. For sound finitely axiomatized sequential S, the paper proves unconditionally that EA⊢Con_S→Con_{S+φ} implies S n^{O(1)}-proves Con_{S+φ}(n), via the standard interpretability criterion for finitely axiomatized sequential theories and polynomial-time proof translation. It also proves that any true extension S+φ that S fails to simulate yields, for all sufficiently large k, failure to simulate S^1_2+φ_BB(k), where φ_BB(k) asserts the exact k-state Busy Beaver value. The proposed characterization — Higher Relative Consistency — is that","claim_key":"core","tier":"stated","source":"verdict_pith","method":"signals","confidence":0.85,"assigned_at":"2026-08-17T03:37:01.456144+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"Toward a Characterization of Simulation Between Arithmetic Theories","paper_submitted_at":"2026-04-30T12:29:58+00:00"},{"claim_id":167776,"arxiv_id":"2605.05233","paper_version":1,"claim_text":"When all knapsacks share an identical capacity the authors give a deterministic polynomial-time algorithm whose minimum knapsack profit is at least (2/3 − ε) times the optimum; for arbitrary capacities they give a (1/2 − ε)-approximation and prove that no better ratio than (1/2 + ε) is possible unless P = NP.","claim_key":"core","tier":"stated","source":"verdict_pith","method":"phrase","confidence":0.9,"assigned_at":"2026-08-17T03:36:39.451502+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"Near-Tight Approximation Algorithms for Bottleneck Multiple Knapsack Problems","paper_submitted_at":"2026-04-30T08:25:10+00:00"},{"claim_id":126982,"arxiv_id":"2604.25873","paper_version":1,"claim_text":"For weights w in A_∞ with [w]_{A_∞} close to 1, there is an explicit embedding into A_p with p depending on the distance to 1, together with bounds on the BMO norm of log w; this yields a quantitative weighted Poincaré-Sobolev inequality that recovers the unweighted classical exponent p* = np/(n-p) as [w]_{A_∞} approaches 1 from above.","claim_key":"core","tier":"stated","source":"verdict_pith","method":"phrase","confidence":0.9,"assigned_at":"2026-08-17T03:36:39.451502+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"Asymptotically sharp embedding of $A_\\infty$ into $A_p$ for flat weights and applications to Poincar\\'e-Sobolev inequalities","paper_submitted_at":"2026-04-28T17:10:47+00:00"},{"claim_id":213154,"arxiv_id":"2604.10418","paper_version":1,"claim_text":"The paper shows that Cantor's contributions to set theory and infinite cardinalities were prerequisites for Turing's halting problem and related undecidability results. It proposes a measure of undecidability based on the probability distribution of input data, extends Turing's oracle machines and infinite logics to super-Turing models, and introduces the U-complete, D-complete, and H-complete classes for problems unsolvable by Turing machines. The central result is a negative resolution, for the U-complete class, of the question analogous to whether P is not equal to NP.","claim_key":"core","tier":"stated","source":"verdict_pith","method":"signals","confidence":0.75,"assigned_at":"2026-08-17T03:37:01.456144+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"Turing or Cantor: That is the Question","paper_submitted_at":"2026-04-12T02:33:00+00:00"},{"claim_id":271746,"arxiv_id":"2604.02395","paper_version":1,"claim_text":"The central discovery is a complexity cliff: directed acyclicity does not help. For p=1/2, DIFR is NP-complete on directed grids; for every rational p∈(0,1), p-DIFR is NP-complete and W[2]-hard parameterized by k on bipartite DAGs. Hence neither a polynomial algorithm on DAGs (unless P=NP) nor an FPT algorithm by k or by combined solution size plus distance-from-acyclicity parameters (unless FPT=W[2]) is possible. The paper's positive results show that the hardness is not uniform: polynomial-time algorithms exist for trees, cycles, outward grids, and λ-outerplanar graphs, and FPT algorithms exist parameterized by treewidth with bounded maximum deficiency and by the number of vertices under p","claim_key":"core","tier":"stated","source":"verdict_pith","method":"phrase","confidence":0.9,"assigned_at":"2026-08-17T03:36:39.451502+00:00","lean_module":null,"lean_decl":null,"lean_status":null,"reality_plus_commit":null,"paper_title":"Complexity of Eliminating (Majority) Illusion in Directed Networks","paper_submitted_at":"2026-04-02T13:14:08+00:00"}]}