2
$\begingroup$

Is there a well established adjective or name for an algorithm such that, given as input any of its own output, always outputs it unchanged? In other words, an algorithm such that it implements a function $f$ with the property $f\circ f=f$. What would be a reference?

My application is a cryptographic security reduction. An example would be an algorithm which on input $X\in\{0,1\}^*$, outputs $1^{|X|}$.

Besides identity, an algorithm implementing $X\mapsto|X|$ in one of $\Bbb Z$, $\Bbb Q$, $\Bbb R$, $\Bbb C$ also comes to mind.


Stationary algorithm or circular algorithm would do, but neither googles. In my experience that means quickly it will google here, bringing circularity to a new level!

$\endgroup$
9
$\begingroup$

In mathematics we would say $f$ is an idempotent function. It's a widely known term and I suppose most TCS people should also recognize it.

| cite | improve this answer | |
$\endgroup$
  • 4
    $\begingroup$ In some contexts, this is also called a projection. $\endgroup$ – Emil Jeřábek Jun 2 at 8:27
1
$\begingroup$

Ilkka Törmä has already given the answer that $f$ is an idempotent function.

You might want to be aware of the concept of fixed-points.

A point $c$ is a fixed-point for $f$ if $f(c) = c$, and hence

$$f(f(c)) = f(c) = c.$$

A set of fixed-points is often called a fixed set.

In your scenario, the output of $f$, or image of $f$, is a fixed set itself.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Ah. So correct me if I'm wrong, but my class of algorithms is those which output is a fixed set for them. While idempotent algorithm is shorter and attested, I'm happy to have a short name for the set of outputs of these algorithms: their fixed set. $\endgroup$ – fgrieu Jun 3 at 11:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.