11 questions linked to/from "NP-complete" optimization problems
152 views

### Why are optimization problems always NP-hard and not NP-complete and what does this mean for other levels of the polynomial time hierarchy? [duplicate]

I have read that optimization problems cannot be $\mathcal{NP}$-complete, but are always classified as $\mathcal{NP}$-hard. When a problem is NP-complete, I know it is contained in $\mathcal{NP}$P. ...
75 views

### Is the Maximum Independent Set problem NP-complete? [duplicate]

It can be read on Wikipedia that MIS is NP-hard. However, is it also NP-complete? This article says: "Thus, the Maximum Clique Problem(MCP) and the Maximum Independent Set(MIS) Problem are ...
139k views

### What is the definition of P, NP, NP-complete and NP-hard?

I'm in a course about computing and complexity, and am unable to understand what these terms mean. All I know is that NP is a subset of NP-complete, which is a subset of NP-hard, but I have no idea ...
4k views

### Decision problems vs “real” problems that aren't yes-or-no

I read in many places that some problems are difficult to approximate (it is NP-hard to approximate them). But approximation is not a decision problem: the answer is a real number and not Yes or No. ...
11k views