New answers tagged np-hardness
6
This is an interesting (and surprising) example for a P $\to$ NP-hard $\to$ P $\to$ NP-hard $\to \cdots$ phase transition:
Deciding if a complete graph on $n$ vertices, in which each vertex has a strict ranking of all other vertices, admits a popular matching is in P for odd $n$ and NP-hard for even $n$. (The parameter is the vertex number $n$.)
The ...
0
This problem is in NP. (easy to verify a given solution)
Subset sum is NP-Complete, so this problem can be reduced to subset sum.
0
Especially when looking at the Knapsack problem later on, this NP-complete problem might be a good fit:
Number guessing, where you can only guess single numbers till you've got it right.
3
The problem seems to be NP-complete. My reduction is from Planar 1-in-3-SAT, just like in their paper. For each variable, take $2k$ vertices. Each of these is covered by two 4-sets and each 4-set covers two consecutive vertices. Thus, we need to take every second of the 4-sets for each variable, this corresponds to TRUE/FALSE. The other two vertices of the 4-...
Top 50 recent answers are included
