Timeline for If a decision problem is in $P$, must finding the solution be possible in polynomial-time?
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 23, 2020 at 1:21 | vote | accept | Dingle Berry | ||
| May 19, 2020 at 3:15 | history | edited | Dingle Berry | CC BY-SA 4.0 |
deleted 17 characters in body
|
| May 19, 2020 at 3:01 | history | edited | Dingle Berry | CC BY-SA 4.0 |
added 17 characters in body
|
| May 19, 2020 at 1:19 | answer | added | D.W.♦ | timeline score: 2 | |
| May 19, 2020 at 1:05 | comment | added | Dingle Berry | @NoahSchweber Sure is counterintuitive. My intuition tells me that every function-variant of a decision problem (in $P$) must be in $FP$. For example, suppose factorization is in $P$ with a working algorithm, but no one has found out how to provide the factors. Very impractical and counter-intuitive. | |
| May 19, 2020 at 1:03 | comment | added | Noah Schweber | Suppose $f$ is some really-hard-to-compute total function and consider the decision problem "Is $x$ in the domain of $f$?" This is trivial - since $f$ is total, everything is in the domain of $f$. But actually finding $f(x)$ given $x$ may be extremely hard. | |
| May 19, 2020 at 1:02 | comment | added | Dingle Berry | I got the idea from integer factorization. Finding a solution should run efficiently on a quantum computer. | |
| May 19, 2020 at 0:54 | history | asked | Dingle Berry | CC BY-SA 4.0 |