<p>A related question <a href="https://cstheory.stackexchange.com/questions/1535/intermediate-problems-between-l-and-nl">asked</a> about intermediate problems between $L$ and $NL$. I'm interested in problems between the nonuniform versions of $NL$, $Mod_n L$ and $P$. This makes sense as it is known that $NL \subseteq Mod_2 L$ nonuniformly (see <a href="https://cstheory.stackexchange.com/questions/7937/parity-l-vs-nl">here</a>).</p>

<p>A motivation comes from the complexity classification of Constraint Satisfaction Problems. To the best of my knowledge, all known dichotomies in this field yield tractable cases that fall in one of the above classes. A seminal result in this area is Schaefer's dichotomy for binary CSPs showing that the tractable instances are reducible to either $2SAT$ (thus $NL$-complete), $HornSAT$ or its dual (thus $P$-complete) or satisfiability of affine equations (thus $\oplus L$-complete).</p>

<p>This question can also be declined in two variants: (i) what about the corresponding counting classes, (ii) what about the corresponding parameterized classes, e.g. parameterized problems non-deterministically solvable in $O(k \log n)$ space vs problems solvable in $n^{O(k)}$ time.</p>

CC BY-SA 3.0
2014-03-17T03:30:32.920Z
So what's the question again?  Things of the form "I'm interested in X" tend not to be a good fit for this site's format.
D.W.
CC BY-SA 3.0
2014-03-17T04:51:43.277Z
Let me explain. It seems that current standards favor people asking explicit questions or giving explicit orders. The problem with this approach is accountability in the presence of terrorism: if you ask some question/solve some problem, and later some terrorist uses your result for criminal purposes, this makes you guilty of collaboration in their eyes. A famous example was the development of the atomic bomb that was made possible by Einstein's SR. Considering that Einstein was Jewish you can draw your own conclusion...
Super8
CC BY-SA 3.0
2014-03-17T06:15:29.677Z
Super8, terrorism?  Huh?  I thought we were talking about CS theory. This sure went off the rails pretty rapidly.  Your fear that asking an explicit question about complexity theory will lead to you being considered guilty of terrorism strike me as, well, far-fetched to me... but in any case discussion of the site rules and policies should be taken to Meta.  In the meantime, if you want to ask participate in this site, please abide by the site rules and policies.
D.W.
CC BY-SA 3.0
2014-03-17T14:33:43.287Z
I agree that CS theory looks innocuous on the surface, but there is still a possibility of intentional "double entendres" on behalf of a devious adversary. That's why I'm trying to be very cautious -- probably not enough, though. Anyways, I apologize for this off-topic discussion.
Super8
CC BY-SA 3.0
2014-03-17T14:49:38.693Z
Can't decide if you are trolling or serious. If a terrorist manages to use a problem between nonuniform NL and nonuniform Mod2L for his evil deeds, I'd sure be impressed!
Sasho Nikolov
<complexity-classes>
Intermediate problems between nonuniform $NL$, $Mod_n L$ and $P$?
Super8
# Intermediate problems between nonuniform $NL$, $Mod_n L$ and $P$?

(Asked by: username_0 on 2014-03-17)

A related question [asked](https://cstheory.stackexchange.com/questions/1535/intermediate-problems-between-l-and-nl) about intermediate problems between $L$ and $NL$. I'm interested in problems between the nonuniform versions of $NL$, $Mod\_n L$ and $P$. This makes sense as it is known that $NL \subseteq Mod\_2 L$ nonuniformly (see [here](https://cstheory.stackexchange.com/questions/7937/parity-l-vs-nl)).

A motivation comes from the complexity classification of Constraint Satisfaction Problems. To the best of my knowledge, all known dichotomies in this field yield tractable cases that fall in one of the above classes. A seminal result in this area is Schaefer's dichotomy for binary CSPs showing that the tractable instances are reducible to either $2SAT$ (thus $NL$-complete), $HornSAT$ or its dual (thus $P$-complete) or satisfiability of affine equations (thus $\oplus L$-complete).

This question can also be declined in two variants: (i) what about the corresponding counting classes, (ii) what about the corresponding parameterized classes, e.g. parameterized problems non-deterministically solvable in $O(k \log n)$ space vs problems solvable in $n^{O(k)}$ time.

**Tags:** complexity-classes

> **Comments:**
> **username_1**: So what's the question again?  Things of the form "I'm interested in X" tend not to be a good fit for this site's format.  
> **username_0**: Let me explain. It seems that current standards favor people asking explicit questions or giving explicit orders. The problem with this approach is accountability in the presence of terrorism: if you ask some question/solve some problem, and later some terrorist uses your result for criminal purposes, this makes you guilty of collaboration in their eyes. A famous example was the development of the atomic bomb that was made possible by Einstein's SR. Considering that Einstein was Jewish you can draw your own conclusion...  
> **username_1**: username_0, terrorism?  Huh?  I thought we were talking about CS theory. This sure went off the rails pretty rapidly.  Your fear that asking an explicit question about complexity theory will lead to you being considered guilty of terrorism strike me as, well, far-fetched to me... but in any case discussion of the site rules and policies should be taken to Meta.  In the meantime, if you want to ask participate in this site, please abide by the site rules and policies.  
> **username_0**: I agree that CS theory looks innocuous on the surface, but there is still a possibility of intentional "double entendres" on behalf of a devious adversary. That's why I'm trying to be very cautious -- probably not enough, though. Anyways, I apologize for this off-topic discussion.  
> **username_2**: Can't decide if you are trolling or serious. If a terrorist manages to use a problem between nonuniform NL and nonuniform Mod2L for his evil deeds, I'd sure be impressed!  

---

## 0 answers

