0
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ Also, is it correct to say that NP is a subset of FNP because decision problems can be solved with search problems? $\endgroup$
    – aksd
    Commented Nov 10, 2014 at 22:52
  • $\begingroup$ Do you mean to ask: "But if P = NP, does it mean FP = FNP?" ? If so, then the yes, your quote already says this. If not then no, as FNP contains function problems (really binary relations, but the details aren't important right now), and NP contains decision problems, so the can never be equal for trivial reasons. $\endgroup$
    – Luke Mathieson
    Commented Nov 10, 2014 at 23:19
  • $\begingroup$ Yeah, i meant is FNP = NP? Is there any material relating the complexity of search to that of deciding or is this an incorrect question? If you can search, you can decide, but how hard is it to go the other way? $\endgroup$
    – aksd
    Commented Nov 10, 2014 at 23:23
  • 2
    $\begingroup$ FNP cannot equal NP because there's a type mismatch: NP is a class of decision problems while FNP is a class of relations. $\endgroup$
    – Yuval Filmus
    Commented Nov 10, 2014 at 23:38

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Ok am confused because I thought NP is the class of decision problems and FNP is the class of search problems. $\endgroup$
    – aksd
    Commented Nov 11, 2014 at 0:37
  • $\begingroup$ @Aegon, I suggest you read some basic material in textbooks or Wikipedia to get yourself clear on the formal definitions of these complexity classes. At this point, that's probably the most helpful and effective way to get a better understanding of this subject and clear up this confusion (posting more comments here on this site is not the right path forward). After you've reviewed that material, if you're still lost, you'll be in a better position to ask a more specific, focused, informed question about what specifically confuses you. $\endgroup$
    – D.W. ♦
    Commented Nov 11, 2014 at 0:39
  • $\begingroup$ @Aegon Check out our reference material! $\endgroup$
    – Raphael
    Commented Nov 11, 2014 at 11:22

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.