Follow

Counting 3-colorings: blog.computationalcomplexity.o and follow-up post blog.computationalcomplexity.o

Like all "natural" NP-complete problems (and many easier problems), the 3-coloring problem should have a -complete counting version, but the gadgets needed to prove it are a little subtle and tracking down the history of proof of this result took some effort.

· · Web · 0 · 0 · 0
Sign in to participate in the conversation
Mathstodon

The social network of the future: No ads, no corporate surveillance, ethical design, and decentralization! Own your data with Mastodon!