Computational Complexity
Several computational problems are associated with the Tutte polynomial. The most straightforward one is
- Input
- A graph
- Output
- The coefficients of
In particular, the output allows evaluating at, which is equivalent to counting the number of 3-colourings of . This latter question is #P-complete, even when restricted to the family of planar graphs, so the problem of computing the coefficients of the Tutte polynomial for a given graph is #P-hard even for planar graphs.
Much more attention has been given to the family of problems called Tutte defined for every complex pair :
- Input
- A graph
- Output
- The value of
The hardness of these problems varies with the coordinates .
Read more about this topic: Tutte Polynomial
Famous quotes containing the word complexity:
“It is not only their own need to mother that takes some women by surprise; there is also the shock of discovering the complexity of alternative child-care arrangements that have been made to sound so simple. Those for whom the intended solution is equal parenting have found that some parents are more equal than others.”
—Elaine Heffner (20th century)