← All Problems
P-complete

Mostowski Epimorphism (MostEpi)

Category: Logic

Input

A well-founded relation $(V, E)$ and $x_1, x_2 \in V$. Let $f$ be the Mostowski epimorphism of the relation. Refer to [1] for definitions.

Problem

Is $f(x_1) = f(x_2)$?

Status

$\P$-complete (Dahlhaus [1]).

Remarks

The reduction to show hardness is from MCVP. The result indicates that the programming language SETL may not be well suited to parallelism [1]. See CLWER for a related open problem.

References

  1. E. Dahlhaus (1987). Is SETL a suitable language for parallel programming — a theoretical approach.
  2. Greenlaw, R., Hoover, H. J., and Ruzzo, W. L. (1995). Limits to Parallel Computation: P-Completeness Theory. Oxford University Press. Problem A.6.12.

Related Problems