TOPICS
Search

End-of-Line

End-of-Line is a total search problem for a directed graph described implicitly by two Boolean circuits giving predecessor and successor functions. A directed edge v->w is present when S(v)=w, P(w)=v, and v!=w. Each vertex has at most one predecessor and one successor, so a known source forces another endpoint. In one conventional normalization, P,S:{0,1}^n->{0,1}^n satisfy P(0^n)=0^n, S(0^n)!=0^n, and P(S(0^n))=0^n. The task is to find v!=0^n such that

P(S(v))!=v or S(P(v))!=v.

These circuits give a concise description of a graph that can have exponentially many vertices. The complexity class PPAD consists of total search problems reducible to this problem in polynomial time (Papadimitriou 1994).

See also

Boolean Circuit, Directed Graph, Polynomial Time, PPAD

Explore with Wolfram|Alpha

References

Papadimitriou, C. H. "On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence." J. Comput. Syst. Sci. 48, 498-532, 1994. https://doi.org/10.1016/S0022-0000(05)80063-7.

Cite this as:

Weisstein, Eric W. "End-of-Line." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/End-of-Line.html

Subject classifications