[Solved]: Does NP-completeness require to find the solution?

ignougroup
Problem Detail: 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.

Asked By : seek

Answered By : Yuval Filmus

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/40883  Ask a Question  Download Related Notes/Documents