New answers tagged complexity-classes
2
This paper by Régis Barbanchon might be of interest. From the abstract:
We prove that the Satisfiability (resp. planar Satisfiability) problem
is parsimoniously P-time reducible to the 3-Colorability (resp. Planar
3-Colorability) problem, that means that the exact number of solutions
is preserved by the reduction, provided that 3-colorings are counted
...
4
There are a few points to consider here:
If we wish to show that $CC(f) = \omega(\log n)$, we should show that it is not possible to cover the domain of $f$ using $\mathrm{poly}(n)$ monochromatic rectangles (rather than $n$ rectangles). Showing it for $n$ rectangles would only establish that $CC(f) > \log n$.
If we wish to prove a lower bound on $D(EQ)$,...
Top 50 recent answers are included
