2022 Developer Survey is open! Take survey.

New answers tagged

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 ...
user avatar
  • 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 ...
user avatar
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\}$ ...
user avatar
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....
user avatar
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&...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar

Top 50 recent answers are included