New answers tagged np-hardness
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