2022 Developer Survey is open! Take survey.

# Tag Info

## 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

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