New answers tagged np-hard
1
vote
Accepted
Is finding the union of all minimum hitting sets NP-hard?
Your logic isn't sound, because it could be that the minimum hitting set (MHS) problem where there is a unique hitting set is much easier. In general you can't assume a problem is hard because it ...
4
votes
Proof that 2-sat is P-hard?
2SAT is NL-complete (with respect to logspace reductions). Wikipedia outlines a proof:
We start by describing Krom's algorithm for 2SAT, using the implication graph. In this directed graph, the ...
2
votes
Name and complexity of this problem on bipartite graphs
This problem is related to the hitting set problem. You can represent this problem in terms of sets. Let $V$ be the ground set and we define the family $\mathcal{F} = \{V_u = N_G(u)\colon u \in U\}$
...
17
votes
Accepted
Why rectangle packing is NP-hard but maybe not in NP?
In order for a language $L$ to be in NP, there needs to be a way to certify that instance $x$ belongs to $L$. This "way" is a polynomial size witness which can be verified in polynomial time....
0
votes
Knapsack with quadratic constraint
The problem is clearly in $\mathsf{NP}$. You can see that it is $\mathsf{NP}$-hard by a reduction from subset sum: given a set $X = \{ x_1, \dots, x_m \}$ of positive integers and another integer $T&...
2
votes
NP-completeness of some problems on assigning candidates to departments
Your problem is not $NP$-complete because it is not a decision problem and hence it is not even in $NP$. Moreover your problem is not $NP$-hard, unless $P=NP$.
In fact, your problem can be solved in ...
5
votes
What kind of problems in the world can be classified into PSPACE categories?
I'm not sure if this question is meant seriously, but it actually relates to a common misunderstanding in computability.
Recall that a problem is formally captured as a formal language, i.e. a set of ...
1
vote
Accepted
Proving the NP hardness of two variants of SAT
The idea is to use a gadget that lets you copy variables. Given a variable $x$, there is a gadget that allows you to create a copy of $x$, that is, a new variable $x'$ such that any satisfying ...
Top 50 recent answers are included
Related Tags
np-hard × 725complexity-theory × 367
np-complete × 291
np × 146
reductions × 137
algorithms × 120
graphs × 105
optimization × 75
decision-problem × 56
approximation × 38
time-complexity × 35
satisfiability × 34
polynomial-time × 23
traveling-salesman × 21
p-vs-np × 19
set-cover × 17
3-sat × 16
polynomial-time-reductions × 16
knapsack-problems × 15
partitions × 15
subset-sum × 14
complexity-classes × 13
proof-techniques × 11
combinatorics × 11
scheduling × 11