P versus NP

A new framework defines TFNP subclasses by adversarial oracles for complexity classes, and shows PSPACE and the polynomial hierarchy yield classes characterized by Frege and constant-depth Frege.

arxiv:2412.09984 · cs.CC · 2024-12

Dung argumentation frameworks are polynomially encodable as inconsistent databases with functional and inclusion dependencies, with extensions matching subset-repairs and covering repairs.

arxiv:2412.11617 · cs.LO · 2024-12

Optimal deterministic policies for LDST-robust MDPs are NP-hard even in a two-stage, single-deviation reward case, and transition uncertainty is Sigma_2^p-hard, but a 1/(5+epsilon)-approximation exists for the two-stage case.

arxiv:2412.12879 · math.OC · 2024-12

Running-buffer minimization for tabletop rearrangement is NP-hard, can require Ω(√n) buffers even for identical cylinders in the worst case, and exact search algorithms scale to over 100 objects.

arxiv:2412.15398 · cs.RO · 2024-12

A Gaussian rounding algorithm for Boolean Max k-CSP is shown to achieve a (1 - o(1)) k/2^k approximation, matching known hardness bounds.

arxiv:2608.07800 · cs.DS · 2026-08

The paper proves solvability of div u = f in Hardy, BMO, and Lipschitz spaces for p greater than n/(n+1), and a Korn inequality in Hardy-Sobolev spaces.

arxiv:2412.21048 · math.AP · 2024-12

For hypergraph Horn functions, enumerating all coatoms (equivalently minimal stopping sets) is not output-polynomial unless P=NP when hyperedge size and element frequency are both at least three, and becomes output-linear when either is at most two.

arxiv:2608.06820 · math.CO · 2026-08

A p-percolated uniform temporal tree on an n-ary tree has size converging to an exponential law, height asymptotic to e times np, and typical depth asymptotic to np.

arxiv:2501.13044 · math.PR · 2025-01

Neural TSP solvers trained on uniform Euclidean instances depend on nearest-neighbor structure, fail on low nearest-neighbor density instances, and can be partly fixed by augmenting training data.

arxiv:2502.00767 · cs.LG · 2025-02

The authors prove that two fairness-constrained variants of the densest subgraph problem over graph snapshots are NP-hard and give integer-programming and greedy algorithms.

arxiv:2502.01381 · cs.DS · 2025-02

A new NP-hard problem, L-agony, ranks nodes via a binary label tree that explains the hierarchy, and a greedy divide-and-conquer heuristic is shown to recover ground-truth rankings in synthetic and real networks.

arxiv:2502.01408 · cs.DS · 2025-02

Unless P=NP, A/E-design under partition constraints has no polynomial-time approximation better than 2^{poly(d)+(1−ε)B}; the proof reduces three-dimensional matching to the inverse matrix norm.

arxiv:2608.05468 · cs.DS · 2026-08

For the binary energy harvesting channel, the authors provide convex optimization formulations of Q-graph lower and upper bounds that converge to the capacity with an O(1/N) gap, enabling capacity computations to 1e-6 precision.

arxiv:2502.07566 · cs.IT · 2025-02

Computing an Ulam median is NP-hard already for exactly four input permutations, which is the minimum possible since three permutations are easy.

arxiv:2608.05544 · cs.CC · 2026-08

The paper derives closed-form energy-per-bit formulas and a geometric decision rule for choosing relay, access point, or direct links using the Waste Factor metric, extended to asymmetric uplink and downlink traffic.

arxiv:2506.08414 · eess.SY · 2025-06

For two-color data, the paper provides the first constant-factor approximation algorithms for closest fair clustering and for fair consensus clustering under the generalized mean objective.

arxiv:2506.08673 · cs.LG · 2025-06

k-Planarity Testing stays NP-hard and hard to approximate on graphs with tiny feedback vertex sets, while becoming fixed-parameter tractable and kernelizable under vertex cover or treedepth parameters.

arxiv:2506.10717 · cs.DS · 2025-06

A system that learns fencing strategy from unlabeled bout videos via pose reconstruction and clustering, then generates new touches that trained fencers rate as competitive with real ones.

arxiv:2507.00261 · cs.CV · 2025-06

Enumerating induced s-t hyperpaths and minimal s-t separators in directed hypergraphs is not output-polynomial unless P=NP, and s-t hyperpath enumeration on BF-hypergraphs is at least as hard as the 45-year-old minimal transversal enumeration problem.

arxiv:2507.07528 · cs.DS · 2025-07

A new bicriteria transit network design problem is shown to be NP-complete and inapproximable in general, with polynomial-time approximation schemes in restricted fixed-flow cases.

arxiv:2507.07894 · math.OC · 2025-07

Minimum-cost CSPs admit a |D|-approximation for dual-discriminator languages, require near-unanimity polymorphisms for any constant-factor approximation, and have an exact approximability dichotomy over permutation-closed languages.

arxiv:2507.08693 · cs.DS · 2025-07

With fixed task mapping and ordering, minimizing carbon cost by shifting task start times is polynomial for one processor, NP-hard for multiple, and a new greedy+local-search framework approaches the ILP optimum.

arxiv:2507.08725 · cs.DC · 2025-07

The m-eternal domination problem and its Roman and Italian variants are NP-hard on narrow graph classes, and four infinite regular grids admit strongly optimal eternally-dominating guard sets.

arxiv:2507.09283 · cs.DM · 2025-07

Introduces glitches as monotonic-oscillation anomalies in decision models and shows that detecting them in tree ensembles is NP-complete.

arxiv:2507.14492 · cs.LG · 2025-07

A three-phase patent retrieval pipeline achieved 100% recall on five examiner-cited test queries, but the score is driven by post hoc cutoff choices and a candidate set that already contains the target patents.

arxiv:2507.14946 · cs.IR · 2025-07

The claimed Verifier Trade-off Theorem is not proven; the valid core reduces to the standard exhaustive-enumeration bound that any b-bit verifier implies a 2^b g(n) solver.

arxiv:2507.23504 · cs.LG · 2025-07

A claimed constructive proof of P=NP via polynomial-time graph simulation of all certificates.

arxiv:2508.13166 · cs.CC · 2025-08

The join-ear equality does not extend beyond graphic matroids, but the two parameters stay within a factor of 6 for all regular matroids.

arxiv:2608.01059 · math.CO · 2026-08

Finding a linearly ordered 3-colouring for a 1-in-3 SAT instance that is known to be satisfiable is NP-hard.

arxiv:2508.14606 · cs.CC · 2025-08

A company can always raise demographic parity violation by at least (N-B)/s_max by flipping un-audited samples, but the paper's alpha-tolerant auditi ng extension is not supported by its proofs.

arxiv:2608.00568 · cs.LG · 2026-08

Bounded positive local weak solutions of the critical p-Laplace equation in R^n, for all 1<p<n, are classified as p-bubbles via new optimal integral estimates.

arxiv:2510.23243 · math.AP · 2025-10

Covering a simple polygon with k equal squares is claimed NP-hard to approximate within factor 1.165 (or 1.25 with centers restricted to the polygon), with a 2.828-approximation algorithm.

arxiv:2512.18268 · cs.RO · 2025-12

An algorithm finds epsilon-approximate solutions to mixed integer quadratic programs in polynomial time on a Turing machine when the number of integer variables and negative Hessian eigenvalues are fixed.

arxiv:2607.29386 · math.OC · 2026-07

Binomial masses a fixed distance from the upper mode have an all-order expansion whose elementary tail is exactly the size-bias factor, leaving pure Appell coefficients.

arxiv:2607.19844 · math.PR · 2026-07

Eliminating p-illusion by recoloring vertices is NP-hard even on directed grids and on bipartite DAGs, but polynomial on trees, cycles, outward grids, and lambda-outerplanar graphs.

arxiv:2604.02395 · cs.DS · 2026-04

A Christofides-style algorithm with prediction-biased spanning trees turns any TSP edge heatmap into a tour of cost at most OPT + 2η, with near-linear-time and graphical variants plus a matching lower bound.

arxiv:2607.03791 · cs.DS · 2026-07

Fractional-logarithmic Laplacians admit logarithmic Bessel potentials with sharp kernel asymptotics and yield critical compact embeddings absent from classical Sobolev/Bessel scales.

arxiv:2603.04879 · math.AP · 2026-03

E^{prMA}/1 contains a language requiring circuits of size Ω(2^n/n).

arxiv:2607.09963 · cs.CC · 2026-07

FFPTAS approximates the amortized multi-copy optimum and forms a complexity class strictly between P and FPTAS for fractionally-polynomial problems (assuming P ≠ NP).

arxiv:2603.17489 · cs.CC · 2026-03

No admissible generator-verifier method can uniformly certify non-trivial semantic invariants such as those needed for P vs NP or one-way functions, by reduction to Rice's theorem.

arxiv:2607.07723 · cs.LO · 2026-07

First poly-time approximation algorithms for sequential posted pricing under known/random deadlines with independent or correlated valuations, including a tight (1-1/e) for known-horizon correlated values.

arxiv:2607.04027 · math.OC · 2026-07

The paper disproves a prior FPT algorithm for PNE in graphical games of bounded treewidth, proves W[1]-hardness, and gives improved algorithms with matching pw-SETH lower bounds for pathwidth and cutwidth.

arxiv:2607.07627 · cs.DS · 2026-07

Claims an O(n log n) (4/3)OPT + p_max algorithm for PTS that resolves a prior open question, plus faster and more general approximations for MCS.

arxiv:2607.00878 · cs.DS · 2026-07

Introduces witness complexity γ(x) measuring expansion time of near-shortest descriptions, proving polynomial invariance, conditional separation from KC under P≠NP, and a biconditional characterization of P=NP via the relative variant γP.

arxiv:2606.31370 · cs.CR · 2026-06

k-level LP feasibility is Σ^p_{k-1}-complete for k≥2, polynomial for k≤4 without coupling and unbounded variables but Σ^p_{k-1}-complete for k≥5; optimal value is FΔ^p_k-complete for k≥2 even without coupling.

arxiv:2605.25100 · math.OC · 2026-05

MSA-S is NP-complete under broad fixed scoring schemes and admits no PTAS for MSA-S-OPT(lambda) even with k=2 unless P=NP.

arxiv:2606.02408 · cs.CC · 2026-06

Provides a 2-approximation for weighted mixed domination when w_e >= w_v and inapproximability results (1.3606, 1.1803, logarithmic) for different weight ratios under P≠NP and UGC.

arxiv:1906.10801 · cs.DS · 2019-06

The 2-connected bottleneck Steiner network problem is NP-hard in any ℓ_p plane, with inapproximability ratio 2^{1/p}−ε for 1≤p<∞.

arxiv:1907.03474 · math.CO · 2019-07

Establishes no-PTAS hardness for interval-restricted assignment and approximation thresholds of 48/47 and 1.5 for 2- and 4-resource restricted scheduling.

arxiv:1907.03526 · cs.CC · 2019-07

Claims a proof that CLIQUE is not solvable in polynomial time on deterministic TMs, implying P ≠ NP.

arxiv:2005.00809 · cs.CC · 2020-05

Develops the first approximation algorithms with guarantees for line planning using heterogeneous fleets and multiple resource constraints, achieving 1-1/e ratio for cost-free case via randomized rounding.

arxiv:2311.03327 · math.OC · 2023-11

The paper shows that small height bounds on rooted trees do not generally yield efficient enumeration for closed or maximal frequent trees, except for a polynomial-delay algorithm in the unordered closed case of height at most 2, while linking other cases to Dualization or NP-hardness.

arxiv:2602.03436 · cs.DS · 2026-02

Claims a proof of P ≠ NP via contradiction between O(1) and Ω(t) bounds on polynomial conditional Kolmogorov complexity for a specially constructed family of SAT instances.

arxiv:2510.08814 · cs.CC · 2025-10

Lipschitz verification is NP-hard due to hidden-state reachability, SDP methods fail like the trivial bound, yet regularizing the trivial bound with bias-free trigonometric layers makes it tight.

arxiv:2603.28113 · cs.LG · 2026-03

The Gallai vertex problem is Θ₂^p-complete.

arxiv:2605.13488 · cs.DM · 2026-05

Gives an approximation algorithm for satisfiable instances of generalized linear equation CSPs over finite groups that is optimal for certain S, while the predicate remains approximation resistant on almost-satisfiable instances.

arxiv:2605.10010 · cs.CC · 2026-05

For n≥4 and p>2 close to 2 (or q close to p), the radial solution to the generalized Hénon-Neumann problem is a local minimizer of the energy for sufficiently large α.

arxiv:2604.26286 · math.AP · 2026-04

Turing's work relies on Cantor's contributions; a new undecidability measure and U-complete, D-complete, H-complete classes are defined, with a negative answer to a P-vs-NP analog for undecidable problems.

arxiv:2604.10418 · cs.CL · 2026-04

Near-tight (2/3-ε) approximation for identical-capacity bottleneck multiple knapsack and (1/2-ε) for arbitrary capacities, with matching inapproximability.

arxiv:2605.05233 · cs.DS · 2026-04

Asymptotically sharp A_∞ to A_p embedding for flat weights with [w]_{A_∞} near 1, yielding quantitative weighted Poincaré-Sobolev inequalities that approach the unweighted case.

arxiv:2604.25873 · math.CA · 2026-04