Timeline for Difference b/w Functional and Decisional Problem's computational complexity
Current License: CC BY-SA 4.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 20, 2022 at 18:42 | comment | added | D.W.♦ | @student0, If you have a new/follow-up question, I'd suggest asking a new question. This site isn't really designed for interactive back-and-forth / conversation. | |
| Dec 20, 2022 at 10:37 | comment | added | student0 | 2. In this link of problems in $P$ (en.wikipedia.org/wiki/P-complete) the examples are: "Circuit Value Problem (CVP) – Given a circuit, the inputs to the circuit, and one gate in the circuit, calculate the output of that gate." Aren't they supposed to be just YES/NO problems in P. These seem functional version examples. I am confused here? | |
| Dec 20, 2022 at 10:31 | vote | accept | student0 | ||
| Dec 20, 2022 at 10:31 | comment | added | student0 | Thank you. I understood both parts. Follow up query though: 1. For an input $x$ with running time of $T_f$ given by some function $r_f(|x|)$ can we ALWAYS have a logic/function such that the decision version Turing machine $T_d$ has also the same running time i.e. $r_f(|x|)=r_d(|x|)$. Notice we even in decision variant are using the running time only over $x$? | |
| Dec 20, 2022 at 9:51 | history | answered | D.W.♦ | CC BY-SA 4.0 |