New answers tagged

4

To complete the first answer, the equivalence problem is decidable (this dates back to haken, a good reference is Lackenby's survey Elementary Knot Theory ). It is neither known to be in NP nor known to be NP-hard. The crossing number of a knot/link is not known to be in NP (even if you give me the diagram with the fewest crossings I would need to solve the ...


4

Regarding the HOMPFLY-PT polynomial, evaluating the coefficients of the Jones polynomial is #P-hard, and this of course transfers to the more general HOMPFLY-PT polynomial: https://doi.org/10.1017/S0305004100068936 On the positive side, this problem is fixed-parameter tractable: https://arxiv.org/abs/1712.05776 Regarding the unknotting problem, Marc Lackenby ...


2

We confirm @YonatanN's conjecture: Lemma 1. There is always an optimal solution $v'$ such that, for some $i'$, $|v_{i'}' - v_{i'}| = k$, while $v'_i = v_i$ for all $i\ne i'$. @YonatanN's suggested algorithm (try all possible such solutions and choose the best) will give the following corollary: Corollary 1. There is a polynomial-time algorithm for the ...


0

To answer my own question, I have found that this problem is indeed NP-Hard via a reduction from the Cactus Augmentation Problem (which is NP-hard). In "Parameterized Algorithms to Preserve Connectivity" they show that a Cactus Augmentation Problem can be transformed into an equivalent Node-weighted Steiner Tree problem where each Steiner node is ...


4

Theorem 1. The problem in the post is NP-complete. Proof. MIN DNF is the following special case of the problem in the post: Given a truth table $T$ and integer $k$, is there a DNF of size at most $k$ whose truth table is $T$? MIN DNF is known to be NP-complete (see [1] and works cited by it). Since the problem in the post generalizes MIN DNF, the problem ...


Top 50 recent answers are included