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 ...
- 12.3k
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 ...
- 269k
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\}$
...
- 4,073
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....
- 269k
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&...
- 22.7k
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 ...
- 22.7k
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 ...
- 16.2k
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 ...
- 269k
Top 50 recent answers are included