Tutte Polynomial - Computational Complexity

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)