# Functional problem and verifying solutions

Is there a functional problem for which there is an algorithm that can decide if a solution is a solution or not in polynomial time but we can't find a solution in polynomial time?

Let FP be the class of functional problems.

Update: Every problem in FP, say $$a$$, has a correspondent decisione problem $$a'$$ (the associated decision problem $$a'$$ is the problem where we ask if a possible solution is a solution), I ask if there is a functional problem $$a$$ for which $$a'$$ is in P but $$a$$ is NOT in FP.

In this link: Hamiltonian cycle, verifying and finding

we have instead a functional problem HC (hamiltonian cycle) for which HC' is P and HC is in FP.

Intuitively I think that the kind of problems I search, should be 'more' the problem of kind of HC. But maybe the hard part, given $$a$$ (with $$a'$$ in P), is to prove that $$a$$ is NOT in FP.

• I refer to this: en.wikipedia.org/wiki/Function_problem The class P is the class of decision problem which are solvable in polynomial time in a Turing Machine. I ask for a functional problem for which the associated decision problem is in P (the associated decision problem is the problem where we ask if a possible solution is a solution), but the functional problem is not solvable in polynomial time.
– asv
Dec 2, 2019 at 12:18
• Thanks for your explanation. Are you asking whether FP = FNP?
– D.W.
Dec 2, 2019 at 17:14
• Every problem in FP, say $a$, has a correspondent decisione problem $a'$ (the associated decision problem $a'$ is the problem where we ask if a possible solution is a solution), I ask if there is a functional problem $a$ for which $a'$ is in P but $a$ is NOT in FP.
– asv
Dec 3, 2019 at 9:32
• In this link: cs.stackexchange.com/questions/117894/… we have instead a functional problem HC (hamiltonian cycle) for which HC' is P and HC is in FP.
– asv
Dec 3, 2019 at 9:33
• I don't know if asking FP=FNP is the same of my question.
– asv
Dec 3, 2019 at 9:38

• What if $2^n$ as a function problem is shown to require $2^n$ digits to display its solutions? What if I could verify the solutions for $2^n$ by converting the solution into binary and comparing the trailing $0-bits$ to the value of $n$ Where, $2^n$ = $solution$. pastebin.com/fGcSRGdU Mar 6, 2020 at 19:13
• @TravisWells, I don't see how that's relevant to my answer. Computing the function $n \mapsto 2^n$ is not in FP (assuming the input is represented in binary). Please don't use comments to raise new questions or seek feedback on your ideas. Thank you.