Timeline for Computational complexity and commuting functions
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 5, 2022 at 12:20 | vote | accept | Doriano Brogioli | ||
| Nov 5, 2022 at 12:20 | comment | added | Doriano Brogioli | I tried to formalize a weaker version of the proposition, here: mathoverflow.net/questions/433954/… . If I am not wrong, it includes your example, but is still difficult to prove or dis-prove for me. | |
| Nov 5, 2022 at 1:05 | comment | added | Fedor Pakhomov | @DorianoBrogioli I don't know, this is a really vague question. And I am not really sure what you would consider to be an improvement of the example. | |
| Nov 4, 2022 at 22:40 | comment | added | Doriano Brogioli | I think it is correct: it proves that Prop. 1 is false. It is very ingenious, but maybe too much ad-hoc: I have the feeling that Prop. 1 could be slightly corrected to include this counter-example. It's just a feeling, due to the fact that there is a single "hard task", calculate $h^n$ for large $n$, that is carried on step-by-step by both $f$ and $g$. Suggestions to modify Prop. 1, or further counter-examples, are welcome. | |
| Nov 4, 2022 at 14:47 | history | edited | Fedor Pakhomov | CC BY-SA 4.0 |
added 4 characters in body
|
| Nov 4, 2022 at 14:37 | history | edited | Fedor Pakhomov | CC BY-SA 4.0 |
added 398 characters in body
|
| Nov 4, 2022 at 14:32 | history | answered | Fedor Pakhomov | CC BY-SA 4.0 |