Timeline for Computationally intractable orbit of a monoid action on a finite set
Current License: CC BY-SA 4.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 24, 2021 at 10:24 | vote | accept | westlon | ||
| Sep 24, 2021 at 14:24 | |||||
| Sep 24, 2021 at 9:29 | answer | added | Dmitry Vaintrob | timeline score: 1 | |
| Sep 24, 2021 at 9:12 | comment | added | westlon | Thanks for the advice. I would point out however that the requirement for a polynomial time membership test was present in all versions of the question. | |
| Sep 24, 2021 at 9:05 | comment | added | Dmitry Vaintrob | It's understandable as you are a new contributor, but you should keep in mind that significantly revising a question multiple times is bad form in mathoverflow, since future readers will not be able to understand old comments/answers. Generally if you find yourself having to revise multiple times that means your question is not ready for mathoverflow, and you need to either figure out what it is you actually want on your own, or find an upstream point of confusion and ask a question about that. | |
| Sep 24, 2021 at 7:55 | comment | added | westlon | @DmitryVaintrob Do you have a membership test for your submonoid that runs in polynomial time in $n$? | |
| Sep 24, 2021 at 7:43 | comment | added | westlon | question revised | |
| Sep 24, 2021 at 7:43 | history | edited | westlon | CC BY-SA 4.0 |
added 127 characters in body
|
| Sep 24, 2021 at 7:02 | comment | added | Dmitry Vaintrob | I don't think you can do better than listing the elements. For example suppose your monoid has all self-maps with image {2,...,n} and may or may not have a random map that takes 1 to 1 and {2,...,n} to {2,...,n}, and this map and whether or not it exists is given by inverting a hash which is polynomial time in $|M_n|\cdot n$. Then evidently there is no faster way to determine whether 1 is in your image than inverting the hash. | |
| Sep 24, 2021 at 6:48 | comment | added | YCor | I see, but what if $M_n$ is the set of all maps fixing $i$? This has size $(n-1)^{n-1}$. | |
| Sep 24, 2021 at 6:23 | comment | added | westlon | added an assumption | |
| Sep 24, 2021 at 6:22 | history | edited | westlon | CC BY-SA 4.0 |
added 93 characters in body
|
| Sep 24, 2021 at 5:43 | comment | added | YCor | If the only information you have is such an efficient algorithm checking whether a map lies in $M_n$, it sounds to me that the worst case is basically when $M_n=\{\mathrm{id}\}$ (or is very small), since the procedure seems to basically check all $n^n$ maps until being sure the given element does lie in the orbit of $1$. | |
| S Sep 24, 2021 at 5:21 | review | First questions | |||
| Sep 24, 2021 at 7:04 | |||||
| S Sep 24, 2021 at 5:21 | history | asked | westlon | CC BY-SA 4.0 |