3
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$ – asv Dec 2 '19 at 12:18
  • 1
    $\begingroup$ Thanks for your explanation. Are you asking whether FP = FNP? $\endgroup$ – D.W.♦ Dec 2 '19 at 17:14
  • $\begingroup$ 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. $\endgroup$ – asv Dec 3 '19 at 9:32
  • $\begingroup$ 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. $\endgroup$ – asv Dec 3 '19 at 9:33
  • $\begingroup$ I don't know if asking FP=FNP is the same of my question. $\endgroup$ – asv Dec 3 '19 at 9:38
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$ – Travis Wells Mar 6 '20 at 19:13
  • $\begingroup$ @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. $\endgroup$ – D.W.♦ Mar 6 '20 at 19:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.