0
$\begingroup$

A related question asked 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).

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.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – D.W. Mar 17 '14 at 3:30
  • $\begingroup$ 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... $\endgroup$ – Super8 Mar 17 '14 at 4:51
  • 4
    $\begingroup$ 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. $\endgroup$ – D.W. Mar 17 '14 at 6:15
  • $\begingroup$ 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. $\endgroup$ – Super8 Mar 17 '14 at 14:33
  • 1
    $\begingroup$ 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! $\endgroup$ – Sasho Nikolov Mar 17 '14 at 14:49

Your Answer

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

Browse other questions tagged or ask your own question.