P versus NP

Formal claims (Lean)

1. The paper's central claim is that the solvable sliding-tile configurations form a polynomial-sized set, not a factorial-sized one. Theorem 4 asserts that for $n \ge 3$, $|S_n(\mathbb{N} \cup \{\emptyset\})| \le 4(n^2 - n - 4)$, and the proof obtains this by adding the legal moves available from each position of the empty square: $8$ from the four corners, $12(n-2)$ from the non-corner edge positio

   arxiv:2501.10480 · lean · ArxivClaims.Y2501.P250110480::central_claim · confidence 0.80 (signals)

Stated claims

1. 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).

   arxiv:2608.07800 · Sharp Analysis of Gaussian Rounding for Boolean Max k-CSP · confidence 0.90 (phrase)

2. 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.

   arxiv:2608.06820 · Coatom Enumeration in Hypergraph Horn Functions: Rank-Three Representations of Horn Model Posets · confidence 0.90 (phrase)

3. 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.

   arxiv:2608.05613 · Predictor-Impossibility Theorem and Applications · confidence 0.85 (signals)

4. 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$.

   arxiv:2608.05468 · Hardness of A/E-Design under Partition Constraints · confidence 0.90 (phrase)

5. 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.

   arxiv:2608.05431 · Towards a Characterization of Counting and Alternating Classes via Discrete Ordinary Differential Equations · confidence 0.85 (signals)

6. 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.

   arxiv:2608.05029 · On Computational Hardness of Mistake-Bounded Language Generation: A Random-Oracle Query Separation · confidence 0.85 (signals)

7. Theorem 56 gives the complete inclusion criterion for all n,n' at least 2: H^a_{n,l} is a subset of H^b_{n',l'} if and only if a is at most b and, when n>n' there is no further condition, when n=n' either b is at least n or l' divides l, and when n<n' then b is at least n'+1. Beyond the main classification, the paper proves H^2_{1,l} is a proper subset of FP and that equality H^2_{1,l}=E^2 would imply P=NP.

   arxiv:2608.04871 · Step Recursion: A Three-Parameter Refinement of the Grzegorczyk Hierarchy · confidence 0.90 (phrase)

8. 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

   arxiv:2608.01059 · Joins and ear decompositions beyond graphic matroids · confidence 0.90 (phrase)

9. 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

   arxiv:2608.00958 · What Syntax Cannot See: The Dynamic Syntactic Invariance Principle and Several Instances of the Same Hidden... · confidence 0.75 (signals)

10. 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

    arxiv:2608.00283 · On the Complexity of Computing Outputs of a Metric Turing Machine · confidence 0.85 (signals)

11. 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

    arxiv:2607.29576 · The gate of self-address: where decidable adjudication ends · confidence 0.80 (signals)

12. 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

    arxiv:2607.29386 · Rational Jacobi Rotations and the Complexity of Approximating Mixed Integer Quadratic Programming · confidence 0.90 (phrase)

13. 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.

    arxiv:2607.27277 · Complexity of Strong Popularity in Additively Separable Hedonic Games · confidence 0.85 (signals)

14. 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

    arxiv:2607.20804 · Hardness and Complexity Transition of Noisy Random Circuit Sampling · confidence 0.80 (signals)

15. 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 '

    arxiv:2607.19573 · On the Computational Complexity of Structural Generalization · confidence 0.80 (signals)

16. δ-Dispersion is poly-APX-complete for every δ>2, and APX-complete for every δ<2 that is not of the form 1/x or 2/x (Theorems 21 and 24). For δ∈(1,2) and δ∈(2/3,1), there are polynomial-time constant-factor approximations whose ratio approaches 1 as δ approaches the solvable endpoints, except that no algorithm can have ratio approaching 1 as δ→2/3+ (unless P=NP).

    arxiv:2607.19053 · Approximating δ-Dispersion · confidence 0.90 (phrase)

17. 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

    arxiv:2607.18168 · A Forward-Backward Weight Analysis of INW for Permutation Branching Programs · confidence 0.85 (signals)

18. 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

    arxiv:2607.15881 · Counting in logarithmic space · confidence 0.85 (signals)

19. 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

    arxiv:2607.14375 · Random Parameter Noise Does Not Make Exact ReLU Verification Easy · confidence 0.85 (signals)

20. 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

    arxiv:2607.13540 · A proof complexity perspective on effectively zero-knowledge proofs · confidence 0.85 (signals)

21. 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.

    arxiv:2607.09963 · Near-Maximum Circuit Lower Bounds for Exponential Time with Merlin-Arthur Queries · confidence 0.85 (signals)

22. 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.

    arxiv:2607.08559 · Computing over Data Streams using Catalytic Space · confidence 0.80 (signals)

23. 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.

    arxiv:2607.06956 · Fixed Points, a Predictor-Impossibility Theorem, and Applications · confidence 0.85 (signals)

24. 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.

    arxiv:2607.05944 · A Lower Bound for Read-Once Parity Branching Programs · confidence 0.85 (signals)

25. 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.

    arxiv:2607.04027 · Sequential Pricing with Deadlines and Correlated Buyers · confidence 0.90 (phrase)

26. 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.

    arxiv:2607.07723 · Limits of Uniform Certification in the Standard Turing Model -- Semantic Invariants and Admissible Methods · confidence 0.90 (phrase)

27. 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.

    arxiv:2607.00878 · Improved Approximation Algorithms for Parallel Task Scheduling and Multiple Cluster Scheduling · confidence 0.90 (phrase)

28. 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.

    arxiv:2606.31370 · Witness Complexity of Short Descriptions: A Cryptographic Perspective · confidence 0.90 (phrase)

29. 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.

    arxiv:2606.27139 · The Observer World: A Cryptographic Extension of Impagliazzo's Five Worlds · confidence 0.80 (signals)

30. 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

    arxiv:2606.04257 · Hardness as an Information Constraint: A Unifying Meta-Complexity Assumption · confidence 0.85 (signals)

31. 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.

    arxiv:2606.02408 · Structure-Informed Multiple Sequence Alignment: A Formal Model and Hardness Results · confidence 0.90 (phrase)

32. 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.

    arxiv:2605.25100 · Price of Coupling in Multilevel Linear Programming · confidence 0.90 (phrase)

33. 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.

    arxiv:2605.13488 · The Gallai Vertex Problem is Theta₂^p-Complete · confidence 0.90 (phrase)

34. 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.

    arxiv:2605.10010 · Optimal Inapproximability of Generalized Linear Equations over a Finite Group · confidence 0.90 (phrase)

35. 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

    arxiv:2604.27787 · Toward a Characterization of Simulation Between Arithmetic Theories · confidence 0.85 (signals)

36. 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.

    arxiv:2605.05233 · Near-Tight Approximation Algorithms for Bottleneck Multiple Knapsack Problems · confidence 0.90 (phrase)

37. 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.

    arxiv:2604.25873 · Asymptotically sharp embedding of A_infty into A_p for flat weights and applications to Poincar\'e-Sobolev inequalities · confidence 0.90 (phrase)

38. 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.

    arxiv:2604.10418 · Turing or Cantor: That is the Question · confidence 0.75 (signals)

39. 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

    arxiv:2604.02395 · Complexity of Eliminating (Majority) Illusion in Directed Networks · confidence 0.90 (phrase)

40. The difficulty is structural: estimating a network's Lipschitz constant requires knowing which hidden states are reachable, and reachability is NP-hard. If P!=NP, then reachability is a barrier to any polynomial-time algorithm. Through explicit constructions, SDP-based bounds inherit the same qualitative failures as the trivial bound. The difficulties afflict every instance, so SDP is not sufficient. However, the trivial bound can be made tight by optimizing removable parameterization pathologies, demonstrated in a linear model and with trigonometric layers.

    arxiv:2603.28113 · Demystifying Lipschitz verification: positive matrices, negative results · confidence 0.90 (phrase)

41. Assuming P ≠ NP, among fractionally-polynomial maximization problems the new FFPTAS notion sits strictly between polynomial-time solvability and classical FPTAS: every poly-time problem has an FFPTAS, every problem with an FFPTAS has an FPTAS, yet there exist problems with an FFPTAS but no poly-time algorithm and problems with an FPTAS but no FFPTAS.

    arxiv:2603.17489 · An approximation notion between P and FPTAS · confidence 0.90 (phrase)

42. On its own terms, the paper establishes that the semantically defined logics CK* and WK* — which interpret □* via the reflexive-transitive closure of the composed relation (≼;R) and ♢* as a constructive 'eventually' — are EXPTIME-complete and have the exponential-size model property. The upper bound follows from a validity-preserving translation τ into classical PDL, where □* becomes [(i*;m)*] and ♢* becomes [i*]⟨m*⟩. The lower bound comes from a converse translation ι that relativizes a classical K*-formula to the hypothesis that every subformula satisfies excluded middle, embedding K* into the diamond-free fragment CK*_box. As the paper notes, this settles the conjecture for the diamond-fr

    arxiv:2603.05131 · The Complexity of the Constructive Master Modality · confidence 0.80 (signals)

43. The fractional-logarithmic Laplacian and its inhomogeneous counterpart generate logarithmic Bessel potentials whose associated function spaces embed compactly into L^{p*} (p* = np/(n-2sp)) whenever n > 2sp, recovering compactness at the borderline Lebesgue exponent—a phenomenon that does not hold for classical Sobolev or Bessel spaces.

    arxiv:2603.04879 · The Fractional-Logarithmic Laplacian: Potentials, Regularity, and Critical Compact Embeddings · confidence 0.90 (phrase)

44. The paper places RNN families in the circuit-complexity hierarchy. It shows that any LRNN over Q recognizes a language in PNC1—log-depth bounded-fan-in arithmetic circuits with a positivity check—and hence, by Corollary 5, in boolean NC circuits of depth O(log n log* n). Conversely, a one-layer MLP RNN with polynomial precision is Turing-complete (P-complete), and a log-precision one solves sorted deterministic graph connectivity, an L-complete problem. Within LRNNs, diagonal-plus-low-rank parameterizations (DeltaNet, RWKV-7) can express iterated 3x3 matrix multiplication, a PNC1-complete problem, while permutation-diagonal LRNNs stay in NC1; one-layer LRNNs simulate weighted finite automata

    arxiv:2603.03612 · Why Are Linear RNNs More Parallelizable? · confidence 0.85 (signals)

45. The central claim is that NESTEDCOLLISION separates the adaptive and non-adaptive black-box closures of PWPP. NESTEDCOLLISION is defined by two shrinking functions f and g, with solutions being a collision (x,y) in f followed by a collision (u,v) in the restricted function g(x,y,·). Because the second collision depends on the first, the problem can be solved by two sequential adaptive queries to a COLLISION oracle. The paper proves that any many-one decision-tree reduction to COLLISION must fail: on a random instance, there exists a collision between two 'good' inputs whose joint query transcript does not yet contain a full NESTEDCOLLISION solution, and since the backward decision tree is sh

    arxiv:2602.23809 · Black-Box PWPP Is Not Turing-Closed · confidence 0.85 (signals)

46. The central claim is Theorem 1.1: LOP is not in StrongAvoid^dt, meaning there is no polylog-complexity decision-tree reduction from the Linear Ordering Principle to Strong Avoid. The technical engine is Theorem 4.1: a degree n/300 Σ2-pseudo-expectation exists for the LOP axioms. By Lemma 3.4, such a pseudo-expectation precludes any degree-n/300 Σ2-unary-Sherali-Adams refutation; by the characterization theorem from the authors' companion paper, reducibility to Strong Avoid is equivalent to the existence of a polylog-degree Σ2-unary-Sherali-Adams proof, so the pseudo-expectation rules out the reduction. The same construction yields Corollary 5.1, that LOP is not reducible to any TFΣ2 problem

    arxiv:2602.16810 · Separations above TFNP from Sherali-Adams Lower Bounds · confidence 0.85 (signals)

47. On its own terms, the paper's discovery is that the feasible-graph machinery from the earlier framework can be turned into a closed, executable algorithm: the author defines explicit deterministic verifier machines for SAT (an input-dependent variant and a fixed-state variant) and Subset-Sum, gives improved definitions of cover/ex-cover edges and a queue-driven 'step-pendant' edge-removal procedure for computing feasible graphs, and then presents a routine SimulateVerifierForAllCertificates() that repeatedly verifies candidate edge extensions until an accepting walk is found or no extensions remain. The paper claims this routine runs in O(n^19 log n) time for both problems (with width and he

    arxiv:2602.10991 · Implementation of Polynomial NP-Complete Algorithms Based on the NP Verifier Simulation Framework · confidence 0.80 (signals)

48. The central claim is a computational view of RL policies: a deterministic policy is identified with a time-bounded Turing machine, so the policy class Π_t contains all policies computable within t(n) steps on inputs of length n. The Policy Hierarchy Theorem then states that for any time-constructible g(n) ∈ o(t(n)/log t(n)), there is an MDP whose optimal policy lies in Π_{O(t(n))} while every g-bounded policy earns arbitrarily lower return. The Long-Horizon Generalization Theorem states that in some goal-conditioned MDP, the best g-bounded policy matches the optimal value function on the finite training-task distribution but is arbitrarily worse on infinitely many longer-horizon test tasks.

    arxiv:2602.05999 · On the Role of Computation in Reinforcement Learning · confidence 0.80 (signals)

49. For rooted unordered trees of height at most 2, we give a polynomial-delay algorithm for enumerating closed frequent trees. On the other hand, for rooted ordered trees of height at most 2, we show that an output-polynomial time algorithm for enumerating closed frequent trees would imply an output-polynomial time algorithm for Dualization. For maximal frequent tree enumeration, we prove that no output-polynomial time algorithm exists unless P = NP already for rooted ordered trees of height at most 2 and for rooted unordered trees of height at most 3.

    arxiv:2602.03436 · The Complexity of Maximal/Closed Frequent Tree Mining for Bounded Height Trees · confidence 0.90 (phrase)

50. The core discovery is a reduction: uniform effective interpolation of G*_1 forces the same property on every normal proof system. The mechanism is the .3-property, a modal splitting principle that lets one prove, for any two formulas, a disjunction of the two implications between their provability statements, with a polynomial-time witness when interpolation is assumed. The paper shows .3 transfers from G*_1 to any system that simulates G*_1 with polynomial overhead and respects the logic of polynomial provability, and that in such a normal system .3 can be converted back into uniform effective interpolation. This transfer is then applied to an enlarged proof system built by adding, for a di

    arxiv:2601.02821 · Effective Disjunction and Effective Interpolation in Suffciently Strong Proof Systems · confidence 0.80 (signals)

51. The paper establishes exact complexity classifications for computing Strahler numbers. The central claim is that the decision problem St≥^term — given a binary tree as a term and a threshold k, is the Strahler number at least k? — is complete for uniform NC^1. The upper bound works by first balancing the input tree into a tree straight-line program of logarithmic depth using a known uTC^0-computable construction, then showing that every context in the Strahler algebra induces a unary function of the form [ℓ,h](x)=h if x<ℓ, h+1 if ℓ≤x≤h, and x if x>h; these functions compose according to a four-case rule, which lets the proof wire a bounded-fan-in circuit of logarithmic depth for each compari

    arxiv:2512.19060 · On the complexity of computing Strahler numbers · confidence 0.85 (signals)

52. The paper asserts 'It is NP-hard to approximate problem 2 within a factor of 1.165' (Theorem 2): unless P=NP, no polynomial-time algorithm can always find k squares of side length below 1.165×OPT covering a simple polygon. It also asserts Theorem 4, NP-hardness within 1.25 for the restricted-center square variant.

    arxiv:2512.18268 · On The Computational Complexity of Minimum Aerial Photographs for Planar Region Coverage · confidence 0.90 (phrase)

53. The central claim is that the two optimal prover strategies for QSZK's complete problems—the Holevo–Helstrom measurement (GapQSD) and the Uhlmann transform (GapF²Est)—can be approximated to additive error 2^{-n} using only O(n) quantum space and 2^{O(n)} time. The approximations are built from space-efficient QSVT: a degree-2^{O(n)} sign-function polynomial whose coefficients are computable in O(n) space, applied to exact block-encodings of (ρ0−ρ1)/2 and Tr_A(|ψ0⟩⟨ψ1|). The class-level consequence is QSZK ⊆ QIP(2) ∩ co-QIP(2) with a quantum linear-space honest prover, and NIQSZK ⊆ qq-QAM with the same prover bound.

    arxiv:2512.11597 · A slightly improved upper bound for quantum statistical zero-knowledge · confidence 0.85 (signals)

54. The paper's central claim is that the bounded-depth monotone formula complexity of the colored isomorphism polynomial ColIso_H is governed exactly by a new graph parameter, λ_Δ(H). A baggy elimination tree for H is a rooted tree in which each node carries a bag of vertices of H and every edge of H has its two endpoints in the same bag or in ancestor-descendant bags; the product depth is the maximum number of internal nodes on a root-to-leaf path (excluding leaves that contain only pendant vertices), and the cost of a path is the sum of its bag sizes. λ_Δ(H) is the minimum possible cost of any such tree with product depth at most Δ. Theorem 1 proves that the Δ-product depth monotone formula s

    arxiv:2511.03388 · Monotone Bounded Depth Formula Complexity of Graph Homomorphism Polynomials · confidence 0.85 (signals)

55. The central claim is Theorem 1.2: if u is a non-negative, non-trivial local weak solution to Delta_p u + u^{p^*-1}=0 in R^n with 1<p<n and u is bounded, then u equals one of the explicit p-bubbles of the form (1.2). The same rigidity holds if u belongs to L^q(R^n) for some q at or above the Sobolev exponent p^*=np/(n-p) (Theorem 1.3), and also under a moderate polynomial growth condition with a dimension-dependent exponent (Theorem 1.4). The proof first shows that any such solution lies in L^{p^*-1}(R^n) (Theorem 1.1), then interpolates to obtain L^{p^*} and hence finite energy, reducing the classification to the known classification of finite-energy solutions; a parallel argument via the P-

    arxiv:2510.23243 · Classification results for bounded positive solutions to the critical p-Laplace equation · confidence 0.90 (phrase)

56. The paper's core discovery is that the semantic class UΣ2P, despite being unlikely to have complete problems, contains three robustly identifiable syntactic layers, and all three are strictly easier than the enclosing class. PTW is defined by reductions to the problem of finding a source in an exponentially large weak tournament whose edge relation is a Boolean circuit; PCW is defined by reductions to finding a Condorcet string among polynomially many circuit voters; PMA is defined by reductions to finding a vertex adjacent to all vertices on one side of a sparse bipartite graph whose edge count is syntactically bounded below twice the number of vertices on the other side. The paper proves Δ

    arxiv:2510.19084 · Complexity of Unambiguous Problems in Sigma^P₂ · confidence 0.85 (signals)

57. We present a proof architecture for P ≠ NP based on an upper-lower clash in polytime-capped conditional description length. We construct an efficiently samplable family of SAT instances Y such that every satisfying witness for Y yields the same global message M(Y). If P=NP, then a standard polynomial-time SAT self-reduction recovers M(Y) from Y, so K_poly(M(Y)|Y)=O(1). The lower-bound side shows the opposite: for the same ensemble, no fixed polynomial-time observer can gain substantial predictive advantage on a linear number of selected message coordinates. A normalization theorem classifies every target-relevant non-neutral evidence leaf as either a safe-buffer observation or a hidden-gauge

    arxiv:2510.08814 · A Quantale-Weakness Route to P neq NP via CD Evidence Normalization and Gauge-Buffered Locked Ensembles · confidence 0.90 (phrase)

58. The paper's central claim is that probabilistic membership mirrors a grammar's ambiguity structure: with at most one parse tree per word, summing probabilities of derivation trees is exact and runs in polynomial time; once ambiguity is allowed, the problem can become #P-hard, already for a union of two linear unambiguous grammars. The paper develops a circuit calculus—×,⊎-circuits with decomposable products, deterministic disjoint unions, and optional complementation—that represents the length-n slice of a language as a factorized set of assignments, so the desired probability is computed by a single bottom-up pass of multiplications, additions, and complements. This calculus subsumes poly-s

    arxiv:2510.08127 · On the Complexity of Language Membership for Probabilistic Words · confidence 0.80 (signals)

59. The central claim is that the linear preprocessing bound in the definition of CstPP is not a delicate parameter. Theorems 5 and 6 show the class is unchanged when preprocessing is relaxed to N^c for any fixed c>1 or tightened to N^epsilon for any epsilon>0, as long as the primitive operations include +, div, and mod. By contrast, Theorem 8 shows that reducing preprocessing to N^{o(1)} collapses the class: even multiplication is no longer constant-time computable with addition only. The paper also shows that a constant-time procedure can be compressed to a single addition expression (a return instruction), and that an exponentially growing function and its inverse are in CstPP together (Theor

    arxiv:2509.10188 · Constant Time with Minimal Preprocessing, a Robust and Extensive Complexity Class · confidence 0.85 (signals)

60. The central claim is Theorem 21: for both para-AC⁰ and para-AC⁰↑, the classes of parameterized problems decided by linear-BD-uniform, logtime-D-uniform, and FO-D-uniform circuit families coincide. In other words, the three parameterized uniformity conditions — defined here for the first time in a unified way — are interchangeable at the level of complexity classes for shallow families. The paper also proves the analogous statement for extended uniformity notions (logtime-E-uniform and FO-E-uniform), where the connection language contains paths, and derives the self-uniformity corollary that (FO-D-uniform para-AC⁰↑)-uniform para-AC⁰↑ equals FO-D-uniform para-AC⁰↑. The authors intend this as a

    arxiv:2509.09657 · Uniformity within Parameterized Circuit Classes · confidence 0.85 (signals)

61. The central claim is that satisfiability of Q=21MLc sentences in the monodic guarded fragment GF=21MLc over K_n and S5_n is 2ExpTime-complete (Theorem 21), and in the monodic two-variable counting fragment C2_21MLc is coNExpTime-complete (Theorem 27), with the same bounds for constant and expanding domains. The technical content is an equivalence: a sentence is satisfiable iff there exists a weak quasimodel of at most exponential size (Lemmas 13 and 14), where quasistates are multisets of types and domain elements are multisets of runs, with a prototype function witnessing saturation. Counting and equality are handled by the multiplicities, and the existing decision procedures for the underl

    arxiv:2509.08165 · Decidability in First-Order Modal Logic with Non-Rigid Constants and Definite Descriptions · confidence 0.80 (signals)

62. On the paper's own terms, the central discovery is that quantum statistical witness indistinguishability is robust across all reasonable definitions of the class: hvQSWI, QSWI, and pubQSWI are equal, and every honest-verifier QSWI proof can be transformed into a 3-message proof in which the verifier sends only random bits and cannot distinguish between any two valid witnesses even when malicious. The transformation chain — round compression following Kitaev and Watrous, private-coin to public-coin conversion following Marriott and Watrous, and malicious-verifier security via Watrous-style rewinding, all adapted from Kobayashi's QSZK framework — preserves the honest prover's efficiency and in

    arxiv:2509.01945 · Quantum Statistical Witness Indistinguishability · confidence 0.85 (signals)

63. The central claim is Theorem 1 plus Corollary 1: the PSPACE-complete language KNAPSACK-GAME has a 2QCFA verifier with perfect completeness, and therefore every PSPACE language does. The verifier runs an endless loop of passes over the input; in each pass it encodes the chosen universal values into quantum amplitudes, lets the prover choose the existential values, and at the right end-marker accepts or rejects based on whether the accumulated values sum to S. Any wrong branch either vanishes or is overwhelmed by rejection probability at least 8/9, and honest members are never rejected, so acceptance happens with probability 1. A streaming simulation of the log-space reduction then feeds the r

    arxiv:2508.21020 · QIP subseteq AM(2QCFA) · confidence 0.85 (signals)

64. The central claim is Theorem 1: let the generators g_n be invertible, with an inverse that a classical algorithm can evaluate in polynomial time and that is Lipschitz continuous, and let the latent distributions P_{z_n} belong to the quantum-hard class Q. Then the pushforward distributions P_{g_n(z_n)} are not in C, the class of distributions approximable by polynomial-time classical sampling. The proof is a reduction in the contrapositive: if the pushforward were in C, sampling from it classically and then applying g^{-1} (with rounding, since the quantum latents are discrete) would produce samples within a constant factor of the allowed Wasserstein error of P_{z_n}, which would place P_{z_

    arxiv:2508.19857 · Quantum latent distributions in deep generative models · confidence 0.80 (signals)

65. The central load-bearing assertion is that for each family considered, the NCCC graph is a complete multipartite graph with the exact spectral formulas listed, e.g., Theorem 2.3: Spec(ΓG) = {[0]^{(p+1)(n-1)}, [-n]^p, [np]^1}, L-spec = {[0]^1, [np]^{(p+1)(n-1)}, [(p+1)n]^p}, Q-spec = {[np]^{(p+1)(n-1)}, [n(p-1)]^p, [2np]^1}, with all three energies equal to 2np. If the paper is correct, these tables and the derived integrality and energy classifications are exact.

    arxiv:2508.19616 · Various spectral aspects of NCCC-graphs of certain finite non-abelian groups · confidence 0.90 (phrase)

66. The authors establish NP^PP-completeness for the constructive and destructive control-by-deleting problems in weighted voting games under the Penrose-Banzhaf index. That is, deciding whether deleting up to k players can make a given player's power exceed (or fall below) a target threshold—or keep it above a threshold—is exactly as hard as the class NP^PP. The proof combines an existential guess of the deletion set (the NP part) with a PP oracle that evaluates the probabilistic Banzhaf power comparison. This resolves the open case left by the corresponding control-by-adding results and, because NP^PP contains NP, the lower bound is optimal in the sense that no smaller deterministic or nondete

    arxiv:2508.13868 · Control by Deleting Players from Weighted Voting Games Is NP^PP-Complete for the Penrose-Banzhaf Power Index · confidence 0.80 (signals)

67. The central discovery is a topological gap between 2-SAT and 3-SAT. Represent the satisfying assignments of a CNF formula as a cubical complex inside the Boolean hypercube; then the paper proves every 2-SAT instance produces a contractible complex, so all higher Betti numbers vanish. In contrast, 3-SAT families—both random and explicit—can have second Betti numbers exponential in the number of variables, i.e., exponentially many independent voids. The paper further argues that these voids are preserved under standard reductions and that removing them is itself NP-hard, so any algorithm that solves 3-SAT must navigate or erase an exponentially void-rich topology. It concludes that $b_2$ is an

    arxiv:2508.13200 · An Intrinsic Barrier for Resolving P = NP (2-SAT as Flat, 3-SAT as High-Dimensional Void-Rich) · confidence 0.85 (signals)

68. The paper's central claim is that the bit-preservation problem for C-Q channels is QCMA-complete. The proof rests on a matrix-analysis lemma giving a complete characterization of optimal witnesses: for any C-Q channel $\Phi$, the minimum over orthogonal input states $|u\rangle, |v\rangle$ of the Hilbert-Schmidt overlap $\mathrm{Tr}(\Phi(|u\rangle\langle u|)\,\Phi(|v\rangle\langle v|))$ is always attained by computational basis states, and the maximum is always attained by $|+\rangle, |-\rangle$ on a single basis pair. This characterization directly supplies the witnesses needed for the QCMA upper bound and the reduction from a QCMA-complete problem, and it also yields QCMA-completeness for t

    arxiv:2508.10664 · Deciding Whether a C-Q Channel Preserves a Bit is QCMA-Complete · confidence 0.85 (signals)

69. On its own terms, the paper claims that incorporating average acceleration into the MeanFlow objective is feasible, expressive, and efficient. Feasibility comes from a generalized consistency condition satisfied by the average acceleration field, which ensures that a single-step sampling scheme is stable and that the loss function is tractable. Expressivity is characterized by showing that, under mild assumptions, the Second-Order MeanFlow sampling process can be implemented by uniform threshold circuits within $TC^{0}$, implying very shallow parallelism. Efficiency is established by a proof that attention operations in the architecture can be approximated to within 1/poly(n) error in time n^{2+

    arxiv:2508.07102 · Towards High-Order Mean Flow Generative Models: Feasibility, Expressivity, and Provably Efficient Criteria · confidence 0.80 (signals)

70. The paper's central claim is Theorem 30: the algorithm SimulateVerifierForAllCertificates() decides every NP language in deterministic polynomial time, so P = NP. The argument models each tape cell of a verifier Turing machine as a stack of computation nodes (a node records cell index, current state, current symbol, last state, last symbol, and a tier counting how many times the cell was visited), and draws an edge between nodes whenever a single transition moves the head from one cell to the next. Running the verifier on all certificates at once, the walks crowd onto a shared graph, and the paper claims the overlap keeps the edge count polynomial. A certificate-oblivious verifier, whose head movements do not depend on certificate contents, is introduced to force all walks to align their transitions. A feasible graph is then defined by pruning step-pendant edges while preserving every walk that ends in a chosen final edge, and VerifyExistenceOfWalk() checks in polynomial time whether any such walk reaches a target edge; the main algorithm repeatedly extends the visited graph boundary with verified edges until an accepting state is reached or no extension exists. The paper concludes with a polynomial bound of O($h^{12}$ $w^{5}$) on the whole simulation, with width w and height h of the graph.

    arxiv:2508.13166 · Graph-Based Deterministic Polynomial Framwork for NP Problems · confidence 0.90 (phrase)

71. The paper's central claim is that simulation is provable: a decoder-only Transformer with chain-of-thought can step through the recurrence of an LCG and the state-update plus tempering of the Mersenne Twister, so the Transformer's output can be made to equal the PRNG's sequence. The authors then draw a complexity conclusion: because these generators can be simulated in this setting, the log-precision decoder-only Transformer can represent non-uniform $\text{AC}^0$ — constant-depth, unbounded fan-in Boolean circuit families of polynomial size — and is therefore not confined to weaker uniform circuit classes sometimes assumed for fixed-depth attention. In practice they find that sequences from Transformer-based PRNGs pass the majority of NIST randomness tests, show clear statistical randomness in heat maps, and they report experiments that assess whether generated numbers can be forecast by a prediction attack. The paper thus presents the Transformer as both a theoretical model of PRNG computation and a practical random-number source inside LLM pipelines.

    arxiv:2508.01134 · Transformers in Pseudo-Random Number Generation: A Dual Perspective on Theory and Practice · confidence 0.80 (signals)

72. The central discovery is the Verifier Trade-off Theorem (Theorem 4.1). For a language L with two certificate-based verifiers, V1 using b1-bit certificates with language-level verification time $\Omega$(f(n)) and V2 using b2-bit certificates with verification time O(g(n)) where f(n) >= c g(n), the theorem asserts b2(n)-b1(n) = $\Omega$(log(f(n)/g(n))). The proof constructs a deterministic solver that fixes a shortest valid V1 certificate w1 and enumerates all 2^(b2-b1) possible extensions d, simulating V2 on each candidate (w1,d); the solver's runtime O(2^(b2-b1) g(n)) must respect V1's lower bound, forcing the logarithmic gap. The paper then derives a solver-verifier corollary (b(n) >= $\Omega$(log(f/g)) when b1=0), applies it to EXPTIME-complete languages and to 3-SAT under ETH, and uses it to argue that certificates of constant or sub-linear size for NP-complete problems would collapse P and NP or violate ETH, while linear certificates would prove P != NP.

    arxiv:2507.23504 · A Verifier Hierarchy · confidence 0.90 (phrase)

73. The central claim is Theorem 3.3: for computably enumerable theories extending $S_2^1$, $S$ proves that $S$ efficiently interprets $S+\phi$ if and only if $S$ proves that $S$ p-simulates $S+\phi$. The forward direction formalizes a strengthened version of Jeřábek's simulation theorem (Theorem 3.2), which rewrites any proof so every line is itself a theorem and then applies the interpretation, giving a polynomial-time map from $S+\phi$-proofs to $S$-proofs. The reverse direction argues that p-simulation on bounded $\Pi^b_1$ sentences lets $S$ prove each bounded instance $\forall n\le b\,\psi(n)$, and then, by a uniformity step that is the paper's load-bearing premise, concludes that $S$ proves the unbounded $\forall n\,\psi(n)$, which by Lindström's theorem gives interpretability.

    arxiv:2507.13576 · A Proposed Characterization of p-Simulation Between Theories · confidence 0.85 (signals)

74. For every time-constructible growth function p(n) ≥ n, there is an n-variate concept class C with VCdim(C) = 1 that is learnable to error ε using O(1/ε) samples in $2^{{O(p(n))}}$ time and using O(p(n)/ε) samples in O(p(n)/ε) time. Crucially, any algorithm that learns C with m(n) samples in time t(n) would imply NTIME(p(n)) ⊆ RTIME($2^{{O(m(n))}}$ t(n) log t(n) poly(p(n))). Consequently, a class that is information-theoretically learnable from one sample can require Θ(p(n)) samples for time-efficient learning, and under RP ≠ NP, O(log n) samples force superpolynomial time. Each concept is a decision tree of size O(p(n)), and the lower bound applies even to improper learners.

    arxiv:2507.13222 · Computational-Statistical Tradeoffs from NP-hardness · confidence 0.85 (signals)

75. On the paper's own terms, the discovery is Theorem 13: if $\varphi$ is a pure graph motif parameter, that is, a rational linear combination $\varphi(G)=\sum_i \alpha_i\,\#\mathrm{Ind}(H_i\to G)$ in which every pattern $H_i$ has no isolated vertices, then $\mathrm{Eval}_\varphi$ lies in $\mathrm{Pr}\text{-}\#\mathrm{P}$ if and only if all coefficients $\alpha_i$ are nonnegative integers. The forward direction is immediate, since such sums count induced occurrences with multiplicity. The theorem's content is the converse: a nonnegative-integer-valued pure parameter with a negative coefficient cannot be computed by any nondeterministic polynomial-time oracle machine, even though parameters like $(n-1)^2$ show that nonnegativity of the function does not force nonnegativity of the coefficients. The proof constructs, for any allegedly computing machine, a padded oracle graph on which the machine's accepting-path count must disagree with the value of $\varphi$.

    arxiv:2507.12244 · Which graph motif parameters count? · confidence 0.85 (signals)

76. On the paper's own terms, the central discovery is a complexity dichotomy: with one processor and a fixed task order, an optimal carbon-minimizing schedule can be computed in polynomial time via a dynamic program that only needs to consider task end times aligned with interval boundaries (E-schedules); with at least two processors, the problem is strongly NP-complete, so no polynomial exact algorithm exists unless P=NP. In the hard regime, the paper's CaWoSched framework combines slack- and pressure-based greedy scores, refined interval subdivisions, and local search to produce schedules whose carbon cost is close to the best known and, on small workflows, close to the ILP optimum.

    arxiv:2507.08725 · Carbon-Aware Workflow Scheduling with Fixed Mapping and Deadline Constraint · confidence 0.90 (phrase)

77. The central claim is a pair of bracketing results. On the algorithmic side, if a finite-domain constraint language Γ is preserved by the dual discriminator operation—the ternary operation that returns the majority label when a majority exists and otherwise the first argument—then every satisfiable MinCostCSP(Γ) instance admits a polynomial-time |D|-approximation, via either a greedy algorithm that fixes variables one at a time and pays at most |D| times the per-iteration optimum, or an LP-rounding algorithm based on the basic linear programming relaxation that discards labels of LP probability below 1/|D|. On the hardness side, if MinCostCSP(Γ) has any constant-factor approximation, then Pol(Γ) must contain a conservative near-unanimity operation, unless P = NP: unbounded-width languages reduce from Nearest Codeword through a first-power pp-interpretation of affine equations over a finite abelian group, while bounded-width languages without an NU polymorphism reduce from k-uniform hypergraph vertex cover. For languages containing all permutation relations the two sides close into a dichotomy (Theorem 1.3). A separate construction, a ternary relation with a conservative majority polymorphism whose MinCostCSP reduces from Min UnCut, shows that the NU condition alone is not sufficient under the Unique Games Conjecture.

    arxiv:2507.08693 · On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems · confidence 0.90 (phrase)

78. The paper's central discovery is that the Modal Split Problem is intractable in a very robust sense and that its tractable parts are exactly the ones reducible to knapsack. Theorem 3.2 proves NP-completeness of MSP even with $w(e)=1$, $m=1$, $D(u,v)=1$ for all $u\neq v$, and $\eta_1=\tau_1=1$, by reducing the directed network design problem DiNDP to MSP; this is the strongest possible parameter collapse short of making the problem empty. Theorem 3.4 proves that for any polynomial-time computable function $\alpha(|V|)$, the optimisation version with $a=\infty$ is not $\alpha(|V|)$-approximable unless P=NP, via a reduction from Directed Steiner Tree in which a large demand $\lceil\alpha(n)(|E|+1)\rceil$ forces any approximation to separate feasible from infeasible Steiner instances. Section 4 shows NP-completeness persists when the passenger flow is fixed, when the graph is tree-like, and even when the graph is a single edge, and derives a PTAS/FPTAS for fixed-flow MSP from known approximation schemes for multidimensional and ordinary knapsack. The paper also proves that for instances whose mode parameters satisfy a slope-ordering condition, a specific line segment in the objective space lies on the Pareto frontier of a continuous relaxation, and every integral layout on it is Pareto-optimal for the original problem.

    arxiv:2507.07894 · Complexity Analysis of a Bicriteria Directed Multimodal Transportation Network Design Problem · confidence 0.90 (phrase)

79. The paper's central claim is that enumeration problems that are easy on directed graphs become conditionally intractable on directed hypergraphs. It asserts (Theorems 6 and 8) that the 'another solution' versions of induced s-t hyperpath and minimal s-t separator enumeration are NP-complete on B-hypergraphs even with every tail of size at most two, so output-polynomial enumeration would imply P=NP. It further asserts (Theorem 10) that output-polynomial s-t hyperpath enumeration on BF-hypergraphs would yield output-polynomial enumeration of minimal transversals, and (Theorem 13) that all S-T hyperpaths in B-hypergraphs can be listed with $O(m^2 \cdot \|A\|)$ delay and $O(m \cdot \|A\|)$ space. The framing is that B-hypergraphs are the tractable boundary for forward-chaining reachability, while allowing F-hyperarcs reconnects the problem to longstanding dualization.

    arxiv:2507.07528 · On the Complexity of Hyperpath and Minimal Separator Enumeration in Directed Hypergraphs · confidence 0.90 (phrase)

80. The central claim is Theorem 1: given a prompt of length N that includes a computational task of complexity O(n³) or higher, with the task's size parameter n smaller than N, an LLM or LLM-based agent will unavoidably hallucinate in its response. The proof relies on the time-hierarchy theorem, which guarantees that some problems require asymptotically more time than others, and on the known O(N²·d) cost of the transformer's self-attention computation. Because the LLM's operations per prompt are bounded by this cost, any task whose minimal execution requires more operations cannot be carried out within the model's budget; the authors count even an accidentally correct answer as a hallucination, since the computation was not actually performed. They extend this conclusion to agentic settings and to verification: a second LLM agent checking a solution faces the same-or-larger complexity, so exact verification is also out of reach.

    arxiv:2507.07505 · Hallucination Stations: On Some Basic Limitations of Transformer-Based Language Models · confidence 0.80 (signals)

81. The central claim is that INFERENCE for Nonogram is co-NP-complete. A negative instance is certified by giving, for every cell, two consistent fillings of the board with opposite values in that cell. Co-NP-hardness is shown by reducing Boolean unsatisfiability: a fresh variable is added to the input formula, a Boolean circuit is built, and the circuit is translated into Nonogram gadgets so that the board has an inferable cell exactly when the circuit is unsatisfiable. Empirically, the paper finds that the average fraction of filled cells whose value is logically forced rises from almost zero to almost one when filled-cell density passes roughly 0.39 to 0.42, and that average solver propagation counts peak in the same region.

    arxiv:2507.07283 · Nonogram: Complexity of Inference and Phase Transition Behavior · confidence 0.85 (signals)

82. The paper's discovery is that the equivalence between computational hardness and pseudoentropy can be witnessed by one function at once for an entire family of entropy measures. Formally, for every family $\Phi$ of convex functions $\varphi : \Delta_L \to \mathbb{R}$ whose subgradients lie in $[-1,1]^L$ and can be computed to $\ell^\infty$ accuracy $\varepsilon/4$ in nonuniform time $T_\Phi$, and for every target $g^* : \{0,1\}^n \to \Delta_L$, there is a single simulator $s$ that is $(T,\varepsilon)$-indistinguishable from $g^*$, computable in time $T' = O((T+T_\Phi)\log L / \varepsilon^2 + L\cdot\operatorname{poly}(1/\varepsilon, \log L))$, and satisfies $H_\varphi(s) - H_\varphi(g^*) \geq D_\varphi(g^*\|s) - \varepsilon$ for every $\varphi \in \Phi$. Thus the pseudoentropy gap and the Bregman-divergence hardness gap coincide up to $\varepsilon$, achieved by the same function $s$, for every entropy notion in the family simultaneously. The matching converse shows every achievable pseudoentropy gap is at most the best efficient divergence approximation plus $\varepsilon$. The paper further establishes that the efficiency hypothesis is load-bearing: an exponential-in-$L$ lower bound holds even against a single trivial distinguisher when the subgradient of one convex function is not efficiently computable, and this forces the doubly exponential dependence on $\ell$ for multicalibration and calibrated multiaccuracy.

    arxiv:2507.05972 · Generalized and Unified Equivalences between Hardness and Pseudoentropy · confidence 0.85 (signals)

83. On the paper's own terms, the central discovery is that lowness for counting function classes is captured by the total single-valued function classes $\mathrm{UPSV}_t$ and $\mathrm{NPSV}_t$, and that closure under feasible left composition forces collapse. A language is low for $\mathrm{TotP}$ exactly when it is in $\mathrm{P}$. A function is low for $\#\mathrm{P}$ exactly when it belongs to $\mathrm{UPSV}_t$, and low for $\mathrm{SpanP}$ exactly when it belongs to $\mathrm{NPSV}_t$; the low function classes for $\mathrm{GapP}$ and $\mathrm{GapP}_+$ are both $\mathrm{FP}^{\mathrm{SPP}}$, and $\mathrm{Low}_f(\mathrm{TotP})=\mathrm{FP}$. For $\#\mathrm{P}$, $\mathrm{GapP}$, $\mathrm{GapP}_+$, $\mathrm{TotP}$, and $\mathrm{SpanP}$, the paper shows that closure under left composition with $\mathrm{FP}_+$ is equivalent to equality with the corresponding low function class, and hence to $\mathrm{PP}=\mathrm{UP}$, $\mathrm{PP}=\mathrm{SPP}$ (twice), $\mathrm{PP}=\mathrm{P}$, or $\mathrm{PP}=\mathrm{NP}$. The paper further proves $\mathrm{SpanP}\subseteq\mathrm{GapP}$ iff $\mathrm{NP}\subseteq\mathrm{SPP}$, and that $\mathrm{GapP}_+\subseteq\mathrm{SpanP}$ implies $\mathrm{PH}=\Sigma_2^{\mathrm{P}}$.

    arxiv:2507.04110 · Low Sets and Closure Properties of Counting Function Classes · confidence 0.85 (signals)

84. The paper's central claim is that the defining structural property behind deep learning's success is compositional sparsity. A function is compositionally sparse when it can be written as at most polynomially many sparse constituent functions, each depending on a small constant number of inputs. Theorem 3.2 asserts that every efficiently Turing-computable function — every function in the complexity class FP — is compositionally sparse: a polynomial-time Turing machine expands into a polynomial-size Boolean circuit, and rebinarizing all high-fan-in gates yields a fan-in-2 DAG with only polynomial overhead. Combined with the known result that deep networks can approximate such functions with $O(d\varepsilon^{-2})$ parameters while shallow networks require $O(\varepsilon^{-d})$, the paper derives Corollary 3.4: any efficiently Turing-computable function, Boolean or real-valued, is approximable by a deep sparse network with polynomial complexity, avoiding the curse of dimensionality.

    arxiv:2507.02550 · Position: A Theory of Deep Learning Must Include Compositional Sparsity · confidence 0.80 (signals)

85. The paper's central claim is Theorem 1: $N=1$. The proof works from the geometric-series identity $\sum_{N=0}^{\infty} 1/2^N = \sum_{N=0}^{\infty} N/2^N$, cancels the capital sigmas and the denominators from both sides, and thereby obtains $1=N$. The argument is then re-expressed with the injective map $f(x)=\sum_{N=0}^{\infty} x/2^N$, so that $f(1)=f(N)$ forces $N=1$. The identity itself is ordinary and true: both sums converge to $2$. The 'new twist' is not in the series but in the manipulation, and the paper's intended content is the parody of proof, not a mathematical fact.

    arxiv:2507.13365 · A Million-dollar Proof · confidence 0.75 (signals)

86. On the paper's own terms, the central discovery is that two standard hardness notions of distribution learning exactly match the two central assumptions of quantum cryptography. Theorem 1.1 states that OWPuzzs exist if and only if proper quantum distribution learning is average-case hard: one direction builds a puzzle whose puzzling part is a batch of samples $x_1,\dots,x_t$ from $D(z)$ and whose unbounded verifier performs maximum likelihood over the parameter $z$ before checking statistical closeness of the claimed answer, and the other direction goes through non-uniform quantum pseudorandom generators, constructing a family $D(\mu,b)$ whose samples carry the hidden seed $\mu$ and either a pseudorandom or uniform string, so that learning the family amounts to distinguishing the generator from uniform. Theorem 1.3 states that $PP \ne BQP$ if and only if agnostic quantum distribution learning with respect to KL divergence is hard, with worst-case hardness of quantum maximum likelihood estimation as the intermediate object and the equality $PP = PostBQP$ as the lever: from the postselecting machine of a $PP$ language one builds a two-hypothesis family whose likelihood ratio is at least 3 exactly on the language, so a QML solver would decide the language in $BQP$. Theorem 1.5 then shows that hardness of agnostic quantum distribution learning with respect to statistical distance against PPT learners with a $\Sigma_3^P$ oracle implies $SampBQP \ne SampBPP$, which the paper notes is the first sampling-based quantum advantage derived from a worst-case hardness assumption on a standard learning framework.

    arxiv:2507.01292 · Hardness of Quantum Distribution Learning and Quantum Cryptography · confidence 0.85 (signals)

87. Theorem 2: For some fixed constant delta > 0, if for every Boolean circuit of size n, there is a q-query PCPP construction with proximity parameter delta, soundness 1-epsilon and randomness O(log n), then for some alphabet Sigma of constant size, Gap_{1,1-epsilon} (q+1)-CSP_Sigma Reconfiguration is PSPACE-hard. If the PCPP hypothesis holds, the soundness gap in CSP reconfiguration matches the PCPP soundness with only one extra query.

    arxiv:2507.01192 · PCPP-Based Reconfiguration Inapproximability: Query Complexity vs. Soundness Gap Trade-offs · confidence 0.85 (signals)

88. The central discovery is that the linear length-ODE schema, written as f(x+1,y)=f(x,y)+(ℓ(x+1)−ℓ(x))·(A(x,y,h,f)·f(x,y)+B(x,y,h,f)) and abbreviating the derivative along ℓ, stratifies the small circuit classes according to which calls to the defined function f are allowed and how the coefficient functions are constrained. When no calls to f are allowed, the schema captures FTC0; when coefficients and the added term are restricted to {0,1}, with A=−1 and B depending on f only through sign tests, it captures FACC[2]; allowing B to be any nonnegative expression with f only under sign tests captures FNC1. The paper proves that the algebra built from basic arithmetic, composition, ℓ-ODE1, ℓ-ODE3, and ℓ-b0ODE equals exactly FACC[2], that the algebra built from ℓ-pODE and ℓ-bODE equals exactly FNC1, and that the full linear ℓ2-ODE schema, deriving along ℓ∘ℓ, is computable in FNC1.

    arxiv:2506.23404 · Characterizing Small Circuit Classes from FAC⁰ to FAC¹ via Discrete Ordinary Differential Equations · confidence 0.85 (signals)

89. The central claim is Theorem 1.1: over a field of characteristic zero, constant-depth algebraic circuits and algebraic formulas are closed under taking factors. If $f$ has degree $d$ and is computed by a circuit of size $s$ and depth $\Delta$, then every factor $g$ of $f$ is computed by a circuit of size $\mathrm{poly}(s,d,n)$ and depth $\Delta+O(1)$; if $f$ is computed by a formula of size $s$, then $g$ is computed by a formula of size $\mathrm{poly}(s,d,n)$. The proof first shows that truncations of a power-series root $\varphi(t)$ of $P(t,y)$, with $\varphi(0)=0$ and $\partial_y P(0,0)\ne 0$, are computable by the same kind of small circuit as $P$, using $\varphi(t)=\sum_{m\ge 1}\frac{1}{m}\,[y^{m-1}](y-P(t,y))^m$. It then combines these algebraic-closure roots into a factor over the base field with small constant-depth circuits for elementary symmetric polynomials of root evaluations. For finite fields the paper proves a weaker statement: if $g$ divides $f$ with multiplicity $p^\ell e$ and $\gcd(p,e)=1$, then $g^{p^\ell}$ has a poly-size constant-depth circuit over the algebraic closure.

    arxiv:2506.23214 · Closure under factorization from a result of Furstenberg · confidence 0.85 (signals)

90. The central load-bearing assertion: the paper shows that PF is #P-hard in (a) the single-stranded case with pseudoknots under the BPS model, and (b) the multi-stranded unpseudoknotted case under the BPM model. This matches Table 1, Theorems 33 and 38, though the Section 1.2 contribution bullet swaps the two energy model names. Equivalently, computing Z = sum_S exp(-DeltaG(S)/k_B T) is as hard as counting solutions to an NP problem in both settings. If the paper is correct, no polynomial-time exact algorithm exists for these problems unless #P is contained in P^NP and the polynomial hierarchy collapses.

    arxiv:2506.19756 · Algorithmic hardness of the partition function for nucleic acid strands · confidence 0.90 (phrase)

91. The paper's main claim is Theorem 2 / Corollary 3: $\mathsf{QCL} \subseteq \mathsf{EQP}$. For any quantum catalytic Turing machine with $s$ qubits of work space and polynomial catalytic space, for every fixed input the machine's runtime is a fixed value $t$ independent of the initial catalytic state, and that value is at most $2^{O(s)}$; for $s = O(\log n)$ this gives a polynomial-time, error-free simulation. The proof proceeds by showing that the runtime distribution is an observable that can be estimated from a single copy of the catalytic state, so two initial states that yielded different runtime distributions would have to be perfectly distinguishable (trace distance 1); a convexity argument then forces the runtime to be constant. With this runtime bound, the paper establishes that quantum catalytic Turing machines and quantum catalytic circuits define the same complexity classes, and derives the further containments $\mathsf{TC}^1 \subseteq \mathsf{QCL}$, $\mathsf{BQ_UCL} \subseteq \mathsf{DQC1}$, and $\mathsf{CL} \subseteq \mathsf{DQC1}$.

    arxiv:2506.16324 · Quantum Catalytic Space · confidence 0.80 (signals)

92. On the space $L^p(T,1)$ of $p$-integrable complex functions on the unit circle with $\|f\|_p \le 1$ and fixed $1<p<\infty$, let the $L^p$-modulus $\mu(n)$ be the least shift precision needed to keep the $L^p$ distance between $f$ and its $\delta$-shift below $2^{-n}$; let the step rate $\sigma(n)$ be the least $K$ such that a $K$-level step function approximates $f$ to error $2^{-n}$; and let the Fourier rate $\varphi(n)$ be the least order of a Fourier partial sum achieving the same error. Theorem 16 proves the four inequalities $\varphi(n) \le \mu(n+O(1)) + n + O(1)$, $\mu(n) \le 2\varphi(n+O(1)) + n + O(1)$, $\sigma(n) \le \mu(n+O(1))$, and $\mu(n) \le \sigma(n+O(1)) + pn + O(1)$. Corollary 17 then yields $O(\varphi(n+O(1)) + n) = O(\mu(n+O(1)) + n) = O(\sigma(n+O(1)) + n)$, so the three parameters induce the same second-order linear and polynomial time complexity. This extends the continuous-function parameterization and answers the stated question of how to cover $L^p$ by compact sets parameterized by a modulus.

    arxiv:2506.11210 · Second-Order Parameterizations for the Complexity Theory of Integrable Functions · confidence 0.85 (signals)

93. The central claim is that the hardness boundary for k-planarity testing sits much lower than previously known. Testing 1-planarity is NP-complete even when the input graph is near-planar (planar plus one edge), has feedback vertex set number at most 3, and has pathwidth at most 4. Separately, the local crossing number cannot be approximated within any constant factor in polynomial time unless P = NP, even for graphs whose feedback vertex set number is at most 2. On the positive side, the paper proves fixed-parameter tractability for treedepth plus k, for feedback edge set number, and for $P_t$-free graphs parameterized by $t+k$, and gives polynomial kernels for vertex cover number and neighborhood diversity. It also proves W[1]-hardness for treedepth alone, twin cover number, and distance to path forest, so the positive treedepth result is tight in requiring $k$ as part of the parameter.

    arxiv:2506.10717 · Structural Parameterizations of k-Planarity · confidence 0.90 (phrase)

94. On the paper's own terms, the discovery is that fairness repair is tractable despite the NP-hardness of fair variants of most clustering objectives. For equal red and blue counts, an optimal nearest fair clustering exists and can be found in $O(n\log n)$; for any unequal ratio $p:q$, no optimal repair can be found in polynomial time unless P = NP, but a fair clustering within a constant factor of the optimal disagreement distance can always be computed in $O(n\log n)$. The ratio independence of the 17 and 33 constants is the substantive point: the approximation cost does not grow with the skew of the protected groups.

    arxiv:2506.08673 · Towards Fair Representation: Clustering and Consensus · confidence 0.90 (phrase)

95. The central claim is that a cascaded system's wasted power can be summarized by one scalar per stage — $W_k$, the ratio of path power consumed to signal power delivered — combined by the cascade identity $W = 1 + \sum (W_k - 1)/\prod G_i$, with the wireless channel itself treated as a passive stage whose waste is $W_{ch} = 1/G_{ch}$. Substituting this into the Consumption Factor and taking the wideband Shannon limit yields the paper's bit-energy formula $E_{bc} = P_{NP}/C + \ln(2)N_0 W$, an additive generalization of Shannon's energy-per-bit limit. Approximating the link waste factor by $W_{TX}/(G_{RX}G_{ch})$ for lossy links, the comparison of direct versus two-hop energy per bit collapses to the distance-only rule $d_3^\alpha > (G_{RX,\text{sink}}/G_{RX,\text{relay}}) d_1^\alpha + (W_{TX,\text{relay}}/W_{TX,\text{source}}) d_2^\alpha$, so a relay node is worthwhile exactly when the direct distance, raised to the path-loss exponent, exceeds a weighted sum of the hop distances. Specializing the same comparison to Fixed Wireless Access with traffic fractions $\rho_u$ and $\rho_d$ yields Eq. (66), where the coefficients become gain- and waste-weighted averages over uplink and downlink, and the $\alpha = 2$ case is an ellipse of advantageous access-point positions that shrinks or grows with the traffic mix. Passive reflective intelligent surfaces fit as a special case of the relay rule, since a passive loss-only stage is exactly the channel-like form $W_{ch} = 1/G_{ch}$.

    arxiv:2506.08414 · Theoretical Foundations of Waste Factor and Waste Figure with Applications to Fixed Wireless Access and Relay Systems · confidence 0.90 (phrase)

96. The paper's central claim is Theorem 1: the lower bound of the computational complexity of the 0-1 knapsack problem on a 3D lattice, $C_L(M_{KP}^{3D})$, is subexponential and superpolynomial. Concretely, the author derives $C_L(M_{KP}^{3D}) \geq C_U(M_{AMC,KP}^{3D})$, and via Eq (20) sets this equal to the 3D spin-glass Ising lower bound $C_L(M_{SGI}^{3D})$, which is $O(2^{N^{2/3}})=O((1+\varepsilon)^N)$ with $\varepsilon \to 0$ and $\varepsilon \neq 1/N$. The same argument places an NP-intermediate (NPI) region between NP-complete and P for knapsack, with the absolute minimum core (AMC) model on the border, meaning the core cannot collapse directly into P.

    arxiv:2506.12080 · Lower bound of computational complexity of knapsack problems · confidence 0.80 (signals)

97. The central discovery is a characterization: gapP = [#2SAT−#2SAT]^log = [#IMPL2SAT−#IMPL2SAT]^log = [#0,1-2DNF−#0,1-2DNF]^log = [#2DNF−#2DNF]^log = [#MON2SAT−#MON2SAT]^log = [#MON2DNF−#MON2DNF]^log = spanL−spanL, and hence #P is strictly sandwiched between one and two #2DNF oracle calls. The proof rests on a new reduction from #SAT to two 2CNF formulas ψ1 and ψ2 with #(φ) = #(ψ1) − #(ψ2), computable in linear time or logspace and preserving treewidth, incidence treewidth, bandwidth, and incidence bandwidth up to small additive constants. The reduction works even for monotone 2CNF/2DNF and for cubic bipartite implication formulas, so subtraction compensates both for missing negations and for missing long clauses. As corollaries the paper derives sparsification for #2SAT and #2DNF, an O($2^{{itw(φ)}}$|φ|) algorithm for #SAT, SETH-tight lower bounds, and refined Toda-type inclusions PH ⊆ [#MON2SAT]^log_TC0 = [#MON2DNF]^log_TC0 and PH ⊆ [#IMPL2SAT]^log_AC0.

    arxiv:2506.06716 · #P is Sandwiched by One and Two #2DNF Calls: Is Subtraction Stronger Than We Thought? · confidence 0.85 (signals)

98. The central claim is Theorem 4: a bijection $f \colon \Sigma^* \to \Sigma^*$ is a Two-way bijection if and only if ForNo computes $f$ with zero-garbage. The forward direction says that if ForNo computes $f$ cleanly, then the syntactically defined inverse term computes $f^{-1}$, and FPTIME-soundness puts both in FPTIME; honesty follows from the polynomial bounds on the inverse. The reverse direction starts from any polynomial-time Turing machine for $f$ and for $f^{-1}$, compiles each into ForNo, and then uses the standard reversible-programming construction (run the forward program, copy the output, run its inverse to clear the workspace, and arrange the two directions so the input register is restored) to produce a single ForNo term that computes $f$ with zero garbage.

    arxiv:2506.03382 · Towards a Characterization of Two-way Bijections in a Reversible Computational Model · confidence 0.85 (signals)

99. Theorem 1.2: Let H be a fixed graph and let Δ and n be natural numbers. Then the polynomials HomH,n and ColSubH,n have monotone circuits of size O(n^{ptw_Δ(H)+1}) and product-depth Δ. Moreover, any monotone circuit of product-depth Δ has size Ω(n^{ptw_Δ(H)+1}). If correct, the exact exponent of monotone bounded-depth circuit complexity of these polynomials is ptw_Δ(H)+1.

    arxiv:2505.22894 · Monotone Bounded-Depth Complexity of Homomorphism Polynomials · confidence 0.85 (signals)

100. The paper's central claim is that in-context search prompting and test-time scaling are not independent tricks that produce marginal gains; their combination unlocks the reasoning ceiling of off-the-shelf models. Concretely, on level-10 instances, Claude 3.7 improves from 4 percent (direct prompt plus thinking mode) to 40 percent (AoT plus thinking mode) on Trip Planning, with similar 8-31 percent results on Meeting Planning, Vertex Cover, and 3-Dimensional Matching. The paper further claims the theoretical equivalences $CoT(poly) = P$, $AoT(poly) = NP$, $CoT(exp) = EXP$, and $AoT(exp) = NEXP$ for decoder-only transformers under its architectural assumptions, with the caveat that only the length of the core computational trace, not redundant tokens, determines the class.

     arxiv:2505.22290 · Rethinking the Unsolvable: When In-Context Search Meets Test-Time Scaling · confidence 0.80 (signals)

Showing 100 of 134. page the rest as JSON.