# Uniform _vs._ Nonuniform Membership for Mildly Context-Sensitive Languages: A Brief Survey
## 6 The Parameterized Complexity of LCFRS Membership  
We now summarize the results we have obtained concerning the parameterized complexity of the uniform membership problem for LCFRS and related formalisms. Recall that the complexity of the best known algorithms for LCFRS parsing is \(\Theta(|G|\cdot n^{f\cdot(r+1)})\) where \(f\) is the fan-out and \(r\) the rank. The main idea of our investigation was to find out whether the fan-out and rank _have_ to end up in the exponent of \(n\) (the length of the input string). Imagine, for example, that we could achieve a complexity like \(2^{\mathcal{O}(f\cdot r)}\cdot\mathcal{O}(|G|\cdot n^{c})\), for some constant \(c\). If \(f\) and \(r\) were considered parameters, this would be fixed-parameter tractable. The complexity would still be exponential in \(f\) and \(r\), but consider what happens to the polynomial that describes the dependency on \(n\). Instead of \(f\) and \(r\) determining the _rank_ of this polynomial, they would only determine the _coefficient_. This would be a substantial improvement. We therefore set out to investigate what happens if we treat the fan-out, the rank, or both as parameters. In particular, we wanted to know if it was possible to achieve fixed-parameter tractability. The fan-out and rank are also a natural choice for parameters from a linguistic point of view, since they can be kept small in most linguistic applications; see, e.g., [PERSON] and [PERSON] (2010). Unfortunately, the answers we got were negative. We proved hardness for presumably intractable complexity classes, showing that the rank and fan-out probably do have to go into the exponent of \(n\). For our first result, we fixed the rank to 1 and treated the fan-out as a parameter. **Theorem 1** ([24]). : _The uniform membership problem for \(1\)-LCFRS, where the fan-out is the parameter, is \(W[SAT]\)-hard._  
We proved this result by reduction from the Weighted Monotone Satisfiability problem, which is known to be \(W[SAT]\)-complete [21; 25; 26]. A monotone Boolean formula is a formula built up from only variables, conjunctions, and disjunctions. In particular, there are no negations. In the Weighted Monotone Satisfiability problem, we are given a pair \((\varphi,k)\), where \(\varphi\) is a monotone Boolean formula and \(k\) is an integer. The question is whether \(\varphi\) has a satisfying assignment with weight exactly \(k\), _i.e._, one that sets exactly \(k\) variables to true. In the parameterized version, the parameter is \(k\). In the reduction, the input string represents an encoding of the variables of the formula we reduce from. The structure of the formula is encoded into the rules. The grammar then \"guesses\" \(k\) variables to be set to true by partitioning the input string into \(2k+1\) sections. It can use its encoded knowledge of the formula to verify that the guessed assignment indeed satisfies the formula. This shows off the general ability of an LCFRS with fan-out \(k\) to guess \(k\) items by partitioning the input string, allowing for many reductions from problems of the kind \"is there a subset of size \(k\) with a certain property\". Interestingly, though, we were not able to find a reduction from any \(W[P]\)-hard problem of this kind. Here, we did not manage to find a way of encoding the verification step into an LCFRS. As an example, we can mention the Minimum Axiom Set problem. Here, we are given a set \(S\), a relation \(R\) of pairs \((A,s)\), where \(A\subseteq S\) and \(s\in S\), and an integer \(k\). The question is whether there is a subset \(C\subseteq S\) of size \(k\) from which we can \"generate\" all of \(S\) using \(R\). This problem is \(W[P]\)-complete [25]. Here, as above, it is not too difficult to simulate the \"guessing\" of the subset \(C\). The problem is how to simulate the verification step, _i.e._, checking whether \(C\) generates all of \(S\), in an LCFRS membership problem where the fan-out only depends on \(k\).