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$:

  1. 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;
  2. 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.

  • 1
    $\begingroup$ It's called a search problem and in this case, it's more or less equivalent to the decision variant. $\endgroup$
    – Pål GD
    Mar 31, 2015 at 2:01
  • $\begingroup$ @PålGD Could you please explain what is meant by more or less equivalent? Thanks for the Wikipedia link, that explains the naming. $\endgroup$
    – seek
    Mar 31, 2015 at 2:11
  • $\begingroup$ @PålGD It's clear that the search problem is at least as hard as the decision problem, but the other direction not so much. $\endgroup$
    – Raphael
    Mar 31, 2015 at 7:33

1 Answer 1


You are right that NP-completeness applies only to decision problems. What they mean by "Problem 2.1 is NP-complete" can be either

The decision problem corresponding to Problem 2.1 is NP-complete


The decision problem corresponding to Problem 2.1 is NP-complete, and the search problem is in FNP

Here the search problem is finding a clique of size $k$ if one exists. We think of the search problem as a two-place predicate $f(\langle G,k \rangle,K)$ which is true if $G$ is a graph and $K$ is a $k$-clique of $G$. This search problem is in FNP if the predicate $f$ is in P. (Usually FNP is defined for functions, i.e. for relations which are functions, but you can also define it for general relations.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.