Timeline for Is it incorrect too say that this function problem cannot be in $FNP$?
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 15, 2020 at 1:41 | comment | added | user114966 | @BernardoSubercaseaux, thanks, I think you are right! | |
| Aug 14, 2020 at 19:15 | comment | added | Bernardo Subercaseaux | @Dmitry, as far as I see, they are indeed equivalent. It doesn't matter that you don't have the exact bound because the definitions are existencial. If you know there is a machine M that verifies (x,y) in time polynomial with respect to x, then you know y <= p(x) for some polynomial p, even if you don't know p. Then there is necessarily a NTM M' that guesses y for every x and then checks before accepting (leaving y on the tape). M' is of course dependent on p. It is true that as we don't know p we don't know how M' looks like, but we know it exists, because such a p exists by definition. | |
| Aug 14, 2020 at 18:11 | history | edited | D.W.♦ | CC BY-SA 4.0 |
deleted 575 characters in body
|
| Aug 14, 2020 at 18:08 | comment | added | D.W.♦ | @Dmitry, Good points. I've managed to get myself confused and twisted up, so I don't trust my understanding right now, and I might be making erroneous statements. Hopefully someone who knows this topic better will clear things up. In retrospect, I shouldn't be looking at Wikipedia as my source on this subject. | |
| Aug 14, 2020 at 18:03 | comment | added | user114966 | Ah, our search Turing machine is non-deterministic (so we can non-deterministically try all such $y$), so they are equivalent, right? But in general we don't know when we should stop our search (we only know that $|y| = poly(|x|)$, but don't have an exact bound). | |
| Aug 14, 2020 at 18:00 | comment | added | user114966 | If I understand the definitions correctly, they are not equivalent: for factorization ($P(x,y)=$ $y>1$ and $y$ divides $x$), checking $P(x,y)$ is probably easier than finding such $y$. | |
| Aug 14, 2020 at 17:56 | history | edited | D.W.♦ | CC BY-SA 4.0 |
deleted 2 characters in body
|
| Aug 14, 2020 at 17:55 | comment | added | D.W.♦ | @Dmitry, no. I think both are correct. It's analogous to NP: there are two definitions, one as as a set of decision problems that can be computable by a polynomial-time non-deterministic algorithm, another as a verifier (a binary relation) that has a deterministic polynomial-time algorithm. I've revised my answer. Regardless of which definition you use, you'll come to the same conclusion regarding the original question. | |
| Aug 14, 2020 at 17:50 | comment | added | user114966 | I've actually seen two definitions of FNP: a predicate-based one and as a search problem. Is there a reliable source which states which one is correct? | |
| Aug 14, 2020 at 17:34 | history | answered | D.W.♦ | CC BY-SA 4.0 |