4
$\begingroup$

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.

$\endgroup$
  • 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 '15 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 '15 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 '15 at 7:33
7
$\begingroup$

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

or

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.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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