8
$\begingroup$

The monotone space complexity of a language $L \subseteq \Sigma^*$ can be defined in terms of monotone switching networks (see e.g. "Average Case Lower Bounds for Monotone Switching Networks" by Filmus et al.). This notion is linked to the monotone $NC$ hierarchy and may have applications to the non-monotone setting for which most questions are open.

Here is an equivalent definition in term of circuits. Let $K$ be a circuit (or dag) whose arcs are labelled by elements of $[n] \times \Sigma$, and which has a single root node $r$. We say that $K$ accepts a word $w \in \Sigma^n$ iff there is a root-leaf path $P$ in $K$ whose sequence of labels matches $w$, i.e. for each label $(i,a)$ in $P$ we have $w[i] = a$. Now, given a language $L$, for each integer $n$ we define its $n$-slice complexity $C_L(n)$ as the minimum size of a circuit accepting exactly the words in $L \cap \Sigma^n$. We can put some restrictions on this notion, for instance by requiring that the circuits are read-once, meaning that each accepting path makes a single access to a given position. This leads to a second complexity measure $C'_L(n)$ which seems easier to analyze, as illustrated below.

An example is the Perfect Matching problem ($PM$), which can be shown to have monotone complexity $C'_{PM}(n) = 2^{\Omega(n)}$ as follows. Let $PM_n$ denote the slice of the language corresponding to bipartite graphs $G$ with $n$ vertices on each side of the bipartition (denoted by $A,B$). Consider a circuit $K$ accepting it. Given an integer $k$, let $\mathcal{P}_k$ denote the set of paths of length $k$ in $K$ starting from the root, and let $\mathcal{T}_k$ denote the pair of sets $(S,T)$ with $S \subseteq A, T \subseteq B$ and $|S| = |T| = k$. By monotonicity, we can make the following assumption:

(*) for each node $u$ of depth $k$, there is a tuple $t = (S,T) \in \mathcal{T}_k$ such that each path $P \in \mathcal{P}_k$ leading to $u$ is labeled by a permutation $\sigma_P : S \rightarrow T$.

Indeed, if there were two different paths leading to $u$ corresponding to different tuples, one of them could be extended to a function that is not a permutation (and thus would recognize an $n$-edges graph that is not a matching).

Now observe that we must have the following "coverage" property: for each permutation $\sigma : A \rightarrow B$, there should exist some path $P \in \mathcal{P}_k$ such that $\sigma$ extends $\sigma_P$. Observe that a given permutation $\sigma_P$ can be extended to at most $(n-k)!$ different permutations, and that a given tuple in $\mathcal{T}_k$ can induce at most $k!$ different permutations. This implies that the number of nodes at depth $k$ is at least $\frac{n!}{k! (n-k)!}$. In particular, the number of nodes at level $\frac{n}{2}$ is at least $\frac{n!}{(\frac{n}{2})!^2} = 2^{\Omega(n)}$.

There are two things I would like to understand: (i) why does this reasoning break down for read-many / nonmonotone space complexity, (ii) how does it relate to known lower bounds for the monotone space complexity of $PM$.

$\endgroup$
6
$\begingroup$

This not quite an answer, but rather an "extended comment".

To question (i): property (*) holds because of read-once, not because of the monotonicity, and this is why the argument fails in the read-many (even monotone) case: then the combined paths need not be PMs, they can be arbitrary graphs containing a PM.

In the read-once case, even the Exact PM (accept a graph iff it is a perfect matching) requires exponential size (by the same argument as yours). But if we allow negations, then EPM can be computed by a circuit of size $O(n^3)$: check if every node in A has degree at least one, and if every node in B has degree at most one. The resulting switching network is "almost read-once": every consistent path is read -once. Search term "null-path" here for more information.

To question (ii): I haven't understood what "it" here refers to? But as far as I know, the $n^{\Omega(\log n)}$ lower bound of Razborov (for monotone circuit size of PM) remains the strongest one. Even though monotone switching networks constitute a special case of monotone circuits (where one input of each AND gate must be a variable), no stronger lower bounds for PM are known here.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.