##

6.5.1 Lower Bounds

Lower bounds have been established for a variety of motion planning
problems and also a wide variety of planning problems in general. To
interpret these bounds a basic understanding of the *theory of
computation* is required [462,891]. This fascinating
subject will be unjustly summarized in a few paragraphs. A *problem* is a set of *instances* that are each carefully encoded
as a binary string. An *algorithm* is formally considered as a
*Turing machine*, which is a finite-state machine that can read
and write bits to an unbounded piece of tape. Other models of
computation also exist, such as integer RAM and real RAM (see
[118]); there are debates as to which model is most
appropriate, especially when performing geometric computations with
real numbers. The standard Turing machine model will be assumed from
here onward. Algorithms are usually formulated to make a binary
output, which involves *accepting* or *rejecting* a problem
instance that is initially written to the tape and given to the
algorithm. In motion planning, this amounts to deciding whether a
solution path exists for a given problem instance.

**Subsections**
Steven M LaValle
2012-04-20