New answers tagged cc.complexity-theory
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
...
9
Maybe the keyword you are looking for is "Implicit Complexity". It is more general than Curry-Howard correspondence, but several lines of research investigate along the axis you are interested in. You can check for instance the publications of Patrick Baillot for many references and pointers.
For a little self-promotion, here are for instance two ...
6
If $G$ is $2k$-regular, then a relaxed edge coloring with exactly $k$ colors is the same thing as a 2-factorization, and is known to always exist by results of Petersen 1891.
Otherwise, let $k=\lceil\Delta/2\rceil$ where $\Delta$ is the maximum degree of $G$. Then obviously, at least $k$ colors are needed in any relaxed coloring of $G$. But $G$ can be ...
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)$,...
2
It is unlikely to have a "name" because it is trivial: it can be solved with a hashtable, array, self-balanced binary search tree, or any other data structure that maps $x$ to $X_i$.
-1
Using Kahn's algorithm, we can easily keep track of unvisited vertices at each step for the node at topological order $k\in[1..n]$. Using backtracking we can effectively accomplish this.
The worst case is a graph with no edges. In this case there are $n!$ topological orderings, and given that each contains $n$ nodes we are already at $n*n!$ output size ...
Top 50 recent answers are included
