patternMinor
Functional problem and verifying solutions
Viewed 0 times
problemverifyingandsolutionsfunctional
Problem
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.
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.
Solution
It appears that you are asking whether FP = FNP. That is an open problem. It is known that FP = FNP if and only if P = NP. I suspect that most theoreticians expect that it's likely that P != NP, which would imply FP != FNP. If FP != FNP, there exists a function problem whose solutions can be verified in polynomial time, but where you can't find a solution in polynomial time. In particularly, any FNP-complete problem -- such as FSAT, say -- will have that property, if FP != FNP. So, the FNP-complete problems are particularly good candidates for having the property you articulate. See https://en.wikipedia.org/wiki/Function_problem for an overview.
Context
StackExchange Computer Science Q#117919, answer score: 2
Revisions (0)
No revisions yet.