Timeline for Computational complexity and commuting functions
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 5, 2022 at 12:20 | vote | accept | Doriano Brogioli | ||
| Nov 5, 2022 at 12:18 | comment | added | Doriano Brogioli | After the answer of Fedor Pakhomov, I proposed a slightly weaker version of Prop. 1 here : mathoverflow.net/questions/433954/… . | |
| Nov 5, 2022 at 12:16 | history | edited | Doriano Brogioli | CC BY-SA 4.0 |
link to new question
|
| Nov 4, 2022 at 14:32 | answer | added | Fedor Pakhomov | timeline score: 5 | |
| Nov 4, 2022 at 9:24 | history | edited | Doriano Brogioli | CC BY-SA 4.0 |
added 34 characters in body
|
| Nov 4, 2022 at 9:23 | comment | added | Doriano Brogioli | Yes! The binary representations of $n$ and $m$ are part of the input. If we used the unary representation, Prop. 1 would become easy to prove. I will edit the question. | |
| Nov 4, 2022 at 9:15 | history | edited | YCor |
edited tags
|
|
| Nov 4, 2022 at 9:07 | comment | added | Fedor Pakhomov | When you talk about the polynomial dependency on $n$ and $m$ do you mean that they are represented as binary expansions and the algorithms are working in polynomial time of their lengths? | |
| Nov 4, 2022 at 8:54 | history | edited | Doriano Brogioli | CC BY-SA 4.0 |
notation f^a
|
| Nov 4, 2022 at 8:51 | comment | added | Doriano Brogioli | The expression $f^a$ means: $f$ applied $a$ times, like $f(f(f(...(x))))$. I will edit the question to clarify the notation. | |
| Nov 4, 2022 at 6:34 | comment | added | Emil Jeřábek | What exactly do you mean by $h^a$ and $h^b$? Are they taken modulo something? Or how else do you make it a length-preserving function? | |
| Nov 3, 2022 at 20:42 | history | asked | Doriano Brogioli | CC BY-SA 4.0 |