# Questions tagged [np-hard]

decision problems that are at least as hard as NP-complete problems

595 questions
Filter by
Sorted by
Tagged with
28 views

### Is Partition Problem with non-integer input NP-complete?

The Partition Problem supposes that we have a set $S=\{s_{i} \in \mathbb{R^{+}}\}_{i=1}^{n}$, is there a subset $T$ such that $\sum_{s \in T} s = \sum_{s \notin T}s$? I have read a lot of proofs using ...
42 views

### Are most machine learning problems the same problem? (NP-hard)

I am trying to teach P vs NP to some primarily Machine Learning folks. I wanted to come up with an introductory fact to grab their attention. Reasoning for Question: Most problems in Machine Learning ...
21 views

### What is a good reference for NP hardness in the machine learning/optimization/operations research context?

I am reading some papers in machine learning and at the very beginning (introduction) you will see statements of theorems that says, for example: Theorem 1.1. For any constant ϵ > 0, it is NP-hard ...
34 views

### If a poly-time solution exists for an NP-Complete (Decision) problem, then there exists a poly-time solution for the NP-hard (Optimization) flavor?

This question boils down to: If a polynomial time solution exists for a decision problem, is there also a polynomial time solution for the same problems optimization flavor? Let's take the Traveling ...
29 views

55 views

### Polynomial-time reduction of Primality and 3-SAT

Is 3-SAT $\leq_{p}$ Primality? And/or is Primality $\leq_{p}$ 3-SAT? I think the answer is no and yes, respectively, but I'm not sure. Any help would be appreciated. Thank you.
50 views

### Reducing independent set to triangle-free subgraph

The INDEPENDENT-SET problem is a well-known NP complete problem that takes in a graph $G$ and an integer $k$. It returns true if $G$ has an independent set of size $k$. An instance of the TFS (...