TOPICS
Search

EXPTIME-Complete Problem

An EXPTIME-complete problem is a problem in EXPTIME to which every problem in EXPTIME can be transformed in polynomial time while preserving its yes-or-no answer. More precisely, for every problem A in EXPTIME, there is a function f computable in polynomial time such that an input x has answer yes for A iff f(x) has answer yes for the EXPTIME-complete problem (Sedgewick and Wayne).

Determining whether a player can force a win from a given position in English draughts generalized to an n×n board is an EXPTIME-complete problem (Robson 1984).

See also

Computational Complexity, English Draughts, EXPTIME, NP-Complete Problem

Explore with Wolfram|Alpha

References

Robson, J. M. "n by n Checkers Is Exptime Complete." SIAM J. Comput. 13, 252-267, 1984. https://doi.org/10.1137/0213018.Sedgewick, R. and Wayne, K. "Intractability." Princeton University. https://algs4.cs.princeton.edu/66intractability/.

Cite this as:

Weisstein, Eric W. "EXPTIME-Complete Problem." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/EXPTIME-CompleteProblem.html

Subject classifications