Talk:FNP (complexity)
Add topicLatest comment: 18 years ago by Dcoetzee
 | This article is rated Stub-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
| |||||||||||
Having just claimed that Complexity Zoo (the main reference for this definition) is wrong, I should explain myself. For one thing, the other reference (Bellare and Goldwasser) define "NP relations" this way. Second, as given on Complexity Zoo, FNP clearly cannot equal FP. For instance, the relation n ~ 2^n (in unary or binary, no matter) is polynomially verifiable, but it's clearly not in FP: it would take more than polynomial time just to write the output. Bitwiseshiftleft 03:52, 28 July 2007 (UTC) bitwiseshiftleft
- If the verifier machine is polytime in x, rather than both x and y, I believe this is implied in the same way that NP certificates being defined to have polynomial length is redundant. But your modification is sufficient and somewhat nicer so let's keep it. Dcoetzee 10:29, 28 July 2007 (UTC)