On-device research index

arXiv research

A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.

168,657 papers · 148 categories

Trend · papers per month

count % of corpus

5 results for “co-NP”

The computational complexity of the solid torus core recognition problemmath.GT

Proves NP and co-NP status for knot core recognition in solid torus.

problem Determining if a knot is the core of a solid torus.

method Alternate proof and corollary of Hopf link recognition problem.

result Proves NP and co-NP status for solid torus core recognition problem.

solid torus knot theory NP problem co-NP problem knot core

2023-05-17abs ↗pdf ↗

The pseudo-Anosov and conjugacy problems are in

\textbf{NP} \cap \textbf{co-NP}

math.GT

For a fixed marked surface $S$ , we construct polynomial bounds on the periodic and preperiodic lengths of the maximal splitting sequences of a projectively invariant measured train track. We give two consequences of these bounds. Firstly, that the problem of deciding whether a mapping class is pseudo-Anosov lies in $\t…

2014-10-06abs ↗pdf ↗

The computational complexity of knot genus in a fixed 3-manifoldmath.GT

Knot genus problem solved for all 3-manifolds.

problem Determining if a knot bounds a surface of genus g in a fixed 3-manifold.

method Showing the problem is in co-NP for all 3-manifolds.

result The knot genus problem is now solved for all 3-manifolds, not just rational homology 3-spheres.

knot theory 3-manifolds NP-completeness co-NP genus

2020-04-03abs ↗pdf ↗

Embeddability in

\mathbb{R}^3

is NP-hardmath.GT

We prove that the problem of deciding whether a 2- or 3-dimensional simplicial complex embeds into $\mathbb{R}^3$ is NP-hard. Our construction also shows that deciding whether a 3-manifold with boundary tori admits an $\mathbb{S}^{3}$ filling is NP-hard. The former stands in contrast with the lower dimensional cases wh…

2017-08-25abs ↗pdf ↗

Computational and Statistical Hardness of Calibration Distancecs.DS

Study on computing and estimating calibration distance, showing hardness and efficiency.

problem Computing and estimating calibration distance under different assumptions.

method Efficient algorithm for exact computation, polynomial-time approximation scheme; sample-based estimation for upper bounds.

result The problem becomes NP-hard when assumptions are removed, but efficient algorithms exist under certain conditions.

calibration distance NP-hardness approximation algorithms sample-based estimation concentration inequalities

2026-03-19abs ↗pdf ↗