Timeline for Is factorial computation known to be in a class smaller than $FEXP$?
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 15, 2021 at 17:14 | vote | accept | Turbo | ||
| Aug 15, 2021 at 9:29 | comment | added | Emil Jeřábek | Usually, FCH is defined so that it requires output size to be polynomial. (E.g., this follows from the definition $\mathrm{FCH}=\bigcup_n\mathrm{FC}_n$, where $\mathrm{FC_0=FP}$, $\mathrm{FC}_{n+1}=\mathrm{\#P}^{\mathrm{FC}_n}$.) The bit-graph of a function $f$ is the language $\{(x,i):\mathrm{bit}(f(x),i)=1\}$, where $\mathrm{bit}(w,i)$ is the $i$th bit of $w$. (I take $i$ to be written in binary.) | |
| Aug 15, 2021 at 9:07 | comment | added | Turbo | Based on the statements you provide $n!$ is in $FCH$ it appears. Is there a definition for bit-graph? | |
| Aug 15, 2021 at 8:56 | history | edited | Emil Jeřábek | CC BY-SA 4.0 |
added 10 characters in body
|
| Aug 15, 2021 at 8:46 | history | edited | Emil Jeřábek | CC BY-SA 4.0 |
added 1797 characters in body
|
| Aug 15, 2021 at 8:19 | comment | added | Turbo | Thank you but where is $n!$? | |
| Aug 15, 2021 at 7:12 | history | answered | Emil Jeřábek | CC BY-SA 4.0 |