17 problems

Let $K$ be an amphichiral knot type and let $\omega$ be a minimal simple cubic lattice representative of $K$. Consider the minimal BFACF graph and the reflected mirror seed of…

Unpinning avoidance game complexity conjecture. The problem $\mathsf{Unpin_{AVOID}}(\Sigma,s)$ is $\textsf{PSPACE}$-complete for any $s$ and $\Sigma$, and…

Non-orientable surface complexity conjecture. Both $\mathsf{Pin}(\Sigma,s)$ and $\mathsf{SimplePin}(\Sigma,s)$ are in $\textsf{P}$ when $s\leq 3$, and are $\textsf{NP}$-complete wh…

Hardness-starts-at-four conjecture. For a fixed orientable surface $\Sigma$, the problem $\mathsf{SimplePin}(\Sigma,4)$ is $\textsf{NP}$-complete.

Let $L$ be a physically realizable computation and let $h(L)$ denote its homological complexity. Homological Church–Turing thesis. Every physically realizable computation has finit…

Let $f$ be a function, let … and let $h(L_f)$ denote the homological complexity of the inversion problem associated with $f$. Homological characterization of one-way functions. The…

Let $L$ be a computational problem, let $h(L)$ be its ordinary homological complexity, and let $h_q(L)$ be a proposed quantum homological complexity measure. Quantum homological co…

Let $\mathcal{C}$ be a natural complexity class, let $h(L_n)$ denote the homological complexity of the restriction $L_n$ of a problem $L$ to inputs of size $n$, and let…

Let $\mathcal{C}$ be a natural complexity class, let $h(L)$ denote the homological complexity of a problem $L$, and let $S_{\mathcal{C}}$ be a subset of $\mathbb{N}\cup\{\infty\}$.…

Let $L$ be a decision problem in the bounded-error quantum polynomial-time class $\mathcal{BQP}$, and let $h(L)$ denote its homological complexity. Quantum homological obstruction…

Let $L$ be a computational problem with homological complexity $h(L)$. A physical system is said to solve $L$ efficiently when it computes solutions to $L$ within the relevant effi…

Let $L$ be a computational problem, let $T_L(n)$ denote its time complexity, and let $h(L)$ denote its homological complexity. Homological Time Complexity Relation. There exists a…

Linear-size conjecture. The filtration $\mathcal{D}_{\infty}^{1}(X)$ consists of $O(kn)$ simplices.

Adaptive-radius homology computation conjecture. One can compute the homology of

Descriptive homology nerve boundary-intersection conjecture. Every such planar shape contains a descriptive homology nerve that intersects the boundary of a hole.

Fibonacci-growth conjecture. For every $n\geq 3$, the mean admissible vertex count satisfies

Tight upper-bound conjecture. For every positive $n\neq 1,2,3,5$, equation gives a tight upper bound on the admissible vertex count $\sigma$. Consequently,