0
$\begingroup$

Suppose for each integer $n\geq 1$ we have a submonoid $M_n\subset \mathrm{Self}(\{1, \dots, n\})$ of self-maps of $\{1, \dots, n\}$.

A characterization of $M_n$ is an algorithm that takes an integer $n\geq 1$ and a self-map of $\{1, \dots, n\}$ as input and decides whether the self-map lies in $M_n$.

A characterization of $M_n(1)$ is an algorithm that takes two integers $n\geq i\geq 1$ as input and decides whether $i$ lies in $M_n(1)$.

Suppose we have a characterization of $M_n$ that runs in polynomial time in $n$. Is there a characterization of $M_n(1)$ that runs in polynomial time in $n$?

Improve this question
$\endgroup$
8
  • $\begingroup$ 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$. $\endgroup$
    – YCor
    Commented Sep 24, 2021 at 5:43
  • $\begingroup$ added an assumption $\endgroup$
    – westlon
    Commented Sep 24, 2021 at 6:23
  • $\begingroup$ I see, but what if $M_n$ is the set of all maps fixing $i$? This has size $(n-1)^{n-1}$. $\endgroup$
    – YCor
    Commented Sep 24, 2021 at 6:48
  • 1
    $\begingroup$ 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. $\endgroup$
    – Dmitry Vaintrob
    Commented Sep 24, 2021 at 7:02
  • $\begingroup$ question revised $\endgroup$
    – westlon
    Commented Sep 24, 2021 at 7:43

1 Answer 1

Reset to default
1
$\begingroup$

Edit In my previous answer I took $M$ to be the set of elements with image $\{2,\dots, n\}$ together with a random involution. In fact, that answer does not produce a monoid, since the square of an involution is the identity $\text{id}$ which was not an element of the monoid defined.

Here is a correct answer. Take $M\subset \text{Self}(\{1,\dots, n\})$ to be the set consisting of the identity, and the set of elements that have image in $\{\lfloor n/2\rfloor, \dots, n\}$. Let $\sigma$ be a perfect hash on involutions that are the identity on $\lfloor n/2\rfloor, \dots, n$. Let $M_\sigma$ be the monoid consisting of $M$ and the involution $f_\sigma$ with $\sigma(f_\sigma) = 0,$ if it exists. Then you can check that $M$ is always a monoid, but you can't compute $f_\sigma(1),$ and hence the image of $M_\sigma,$ in polynomial time.

Note With the current formulation of your question, it is actually enough to take $M$ to be $\text{id}$ and a random involution determined by a perfect hash. In a previous version, you asked that $M$ be enumerable in a length of time which is polynomial in $|M|,$ and adding in all elements with image $\{\lfloor n/2\rfloor,\dots, n\}$ guarantees this.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Could you expand what these standard cryptographic assumptions are? Do they apply when you are taking the preimage of one element? $\endgroup$
    – westlon
    Commented Sep 24, 2021 at 12:02
  • $\begingroup$ The assumption is that there exists a (in this case, "perfect") hash function which does not have a polynomial-time inverse. This is a standard cryptographic assumption but would fail if, for example, P and NP were equivalent. $\endgroup$
    – Dmitry Vaintrob
    Commented Sep 26, 2021 at 16:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .