**Problem Detail:**

I read

FP = FNP iff P = NP

which makes sense.

But if P = NP, does it mean FNP = NP?

Intuitively, I think no because P = NP would mean that decision problems in NP would become decision problems in P. But I don't see how that would reduce search problems to decision problems.

###### Asked By : Ashara

#### Answered By : D.W.

No, it doesn't mean that FNP = NP. NP is a class of decision problems; FNP is a class of function problems. See the definition of FNP (e.g., on Wikipedia, or in any textbook). Therefore, the elements of NP have a different type than the elements of FNP.

It's like asking whether the set of tart apples is equal to the set of seedless oranges; one is a set of apples, the other is a set of oranges, so they're certainly not equal, and you don't need to know anything about exactly which apples are tart or which oranges are seedless to know that.

###### Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/32950

**3.2K people like this**

## 0 comments:

## Post a Comment

Let us know your responses and feedback