Timeline for Why is the "balanced vs constant function" problem not a proof that P ≠ BPP?
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Sep 24, 2023 at 14:23 | history | suggested | Peter Mortensen | CC BY-SA 4.0 |
Copy edited (e.g. ref. <https://en.wiktionary.org/wiki/amount#Noun>). Fixed the question formation - see e.g. <https://www.youtube.com/watch?v=t4yWEt0OSpg&t=1m49s> (see also <https://www.youtube.com/watch?v=kS5NfSzXfrI> (QUASM)) - alternatively, drop the question mark.
|
| May 29, 2023 at 14:31 | comment | added | usul | Worth noting that the input size is the number of bits needed to describe $f: \{0,1\}^n \to \{0,1\}$, which could be as large as $2^n$, in which case the brute-force algorithm is linear-time. | |
| May 29, 2023 at 4:15 | review | Suggested edits | |||
| S Sep 24, 2023 at 14:23 | |||||
| May 27, 2023 at 9:16 | vote | accept | Thiago | ||
| May 27, 2023 at 7:21 | history | became hot network question | |||
| May 27, 2023 at 6:33 | review | Close votes | |||
| Jun 1, 2023 at 3:11 | |||||
| May 27, 2023 at 4:18 | answer | added | Andras Farago | timeline score: 22 | |
| S May 26, 2023 at 23:21 | review | First questions | |||
| May 27, 2023 at 7:45 | |||||
| S May 26, 2023 at 23:21 | history | asked | Thiago | CC BY-SA 4.0 |