Fine-grained dichotomies for the Tutte Plane and Boolean #CSP
Jaeger et al. (Math Proc Camb Philos Soc 108(1):35–53, 1990) proved a dichotomy for the complexity of evaluating the Tutte polynomial at fixed points: the evaluation is #P-hard almost everywhere, and the remaining points admit polynomial-time algorithms. Dell, Husfeldt, and Wahlén (in: ICALP 2010, v...
| Main Authors: | , , |
|---|---|
| 格式: | Journal article |
| 語言: | English |
| 出版: |
Springer Nature
2018
|
Search Result 1
