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:
“In times like ours, where the growing complexity of life leaves us barely the time to read the newspapers, where the map of Europe has endured profound rearrangements and is perhaps on the brink of enduring yet others, where so many threatening and new problems appear everywhere, you will admit it may be demanded of a writer that he be more than a fine wit who makes us forget in idle and byzantine discussions on the merits of pure form ...”
—Marcel Proust (1871–1922)