In the paper "Computing Equilibria:A Computational Complexity Perspective" by Tim Roughgarden, they consider the problem:
Problem 2.1 (Clique). Given a graph $G = (V, E)$ and an integer $k$:
- if there is a set $K ⊆ V$ with $|K| = k$ and with $(i, j) ∈ E$ for every distinct $i, j ∈ K$, then output such a set;
- otherwise, indicate that $G$ has no $k$-clique.
Then they claim that Problem 2.1 is NP-complete in the Theorem 2.7.
My question is about the part (1). I always thought NP-completeness is for yes/no problems and thus they didn't require that the the solution be output if the decision is an yes?
So is this definition of NP-complete problem 2.1 right? Or should part (1) be rephrased as "if there is a set $K \subseteq V$ with $|K| = k$ and with $(i, j) \in E$ for every distinct $i, j \in K$, then output yes;
The Problem 2.1 is a half decision problem and half feasibility problem, what are such problems called?
P.S the paper can be found at http://theory.stanford.edu/~tim/papers/et.pdf
I went through Optimization version of decision problems and still not sure where Problem 2.1 belongs to.