4
$\begingroup$

Let the binary relation computed by a nondeterministic transducer be the relation between input strings and the possible output strings the transducer can produce (and accept) for the given input string.

It is easy to see that the nondeterministic transducers using polynomial time can compute different binary relations than the nondeterministic transducers using logarithmic space. (Trivial examples like $\{(1^n,ww^R):n\in\mathbb N, |w|\leq n\}$ suffice to see this. Edit: This assumes that the output is generated symbol by symbol, see András Salamon's comment. If random access to write only output memory is assumed, then $\{(1^n,w):n\in\mathbb N, w\in D_2, |w|\leq 2n\}$ where $D_2$ is the Dyck language of all strings of matching brackets over two pairs of brackets, say $\{ [,], (,) \}$ is an example. However, proving that this example really works is non-trivial.)

Can anything of interest be concluded from this basic observation? For example, concluding that there must exist an oracle $A$ such that $NL^A \neq NP^A$ would be of interest, but things don't work that way. Or concluding that directly programming in NP is easier that directly programming in NL, because more powerful subroutines are available. That sort of sounds true, even so subroutines generally can have more that a single input string and produce more than a single output string. (So one could try to prove that if all those possible subroutines would be equal, then there could not exist an oracle for which the relativized decision problems are different. But even this will probably fail.)


Edit:

  • WLOG, we can restrict us to NL tranducers that never repeat a configuration. These are exactly those NL transducers that only use polynomial time.
  • The random access to write only output memory is well outside NL. But it is still inside NP, so the composition of those NL transducers could be done inside NP. This should be good enough to conclude things about powerful subroutines or oracles, if this is possible at all. (Even the symbol by symbol output tape was outside of NL, it was just less obvious.)
  • The oracles $A$ such that $NL^A \neq NP^A$ are white box oracles, where the problem $A$ is (expected to be) outside of the considered complexity classes. The conclusions about subroutines from the basic observation might tell us something about black box oracles from the same or weaker complexity classes. Or they might at least provide a motivation to prove black box separations between complexity classes relative to oracles from weaker complexity classes.
$\endgroup$
  • $\begingroup$ I just noticed that the binary relations computed by $NL$ are not really closed under composition. Maybe I should have used $SAC^1=LOGCFL$ instead of $NL \subset SAC^1$, but the basic question "so what?" remains the same. (And I would need a new trivial example, because the binary relation $\{(1^n,ww^R):n\in\mathbb N, |w|\leq n\}$ won't do the job anymore.) $\endgroup$ – Thomas Klimpel Feb 7 '16 at 13:56
  • $\begingroup$ Whatever does this have to do with relational algebra? $\endgroup$ – Raphael Feb 7 '16 at 18:03
  • $\begingroup$ @Raphael Especially if there is more than a single input string and more than a single output string, a transducer can compute relatively general relations. For nondeterministic transducers, the distinction between input and output can easily get blurred, so the operations available in the relational algebra might indeed describe quite well, how such relation can be combined to get new relations. But the reason why I added it was that there was neither a "binary relation" tag, nor a "function" tag, and anyway neither would have properly captured the intended subroutine notion. $\endgroup$ – Thomas Klimpel Feb 7 '16 at 18:29
  • $\begingroup$ definitions need to be unpacked/ expanded here. this seems to want to define PTime and logspace wrt transducers (2nd paragraph) which maybe is possible somehow. but dont see what this is talking about nor have seen this in refs. suggest further analysis in Computer Science Chat. (FSM transducers are indeed capable of computing single instantaneous description changes for arbitrary TMs, and this is maybe nearly what this is thinking of.) $\endgroup$ – vzn Feb 8 '16 at 16:05
  • $\begingroup$ Could you provide more details about your claim that the relation you define cannot be generated by a logspace transducer? A transducer only has to leave its output on the output tape, it does not have to generate it symbol by symbol. $\endgroup$ – András Salamon Feb 17 '16 at 7:37
1
$\begingroup$

We know that $NL \subseteq NP$, but that $NL \subsetneq NP$ is not known. So one cannot outright say that $NL$ and $NP$ are different.

We only know for sure $NL \subsetneq PSPACE \subsetneq EXPSPACE$ by space hierarchy theorem. And $P \subsetneq EXPTIME$,and $NP \subseteq NEXPTIME$ by time hierarchy theorem.

We only know for sure is $$L\subseteq NL \subseteq P \subseteq NP \subseteq PH \subseteq PSPACE =NPSAPCE \subseteq EXPTIME \subseteq NEXPTIME\subseteq EXPSPACE$$

Only above four inclusions are known to be strict. All the other inclusions are unknown and open problems. (Though most but not all have unproven belief that each of them is strict).

See https://en.wikipedia.org/wiki/PSPACE#Relation_among_other_classes.

Also, I think, we might be able to prove that there exists a language $B$ for which $NL^B \neq NP^B$. Probably $U_B$ and $B$ of Baker, Gill and Soloway will work here too. And we are also able to show that $NL^A = NP^A$ for $A = TQBF$, the $PSPACE$ complete problem to decide the true quantified Boolean formulas.

$\endgroup$
  • $\begingroup$ Thanks for your interest. If you want to list (nondeterministic) complexity classes related to the question, you could also include AuxPDA(log n, $n^{O(1)}$)=LogCFL (background) or AuxPDA(log n)=P (background). Strictly deterministic complexity classes like L, P, EXPTIME, or EXPSPACE seem less relevant, because the only binary relations they can compute are partial functions. I expected rather answers like the comment by András Salamon, or that black box separations idea. $\endgroup$ – Thomas Klimpel Mar 1 '16 at 18:32
  • $\begingroup$ I thought it was relevant because even decision problems can be written as binary relations $f:\Sigma^*\rightarrow\{0,1\}$. $\endgroup$ – Shreesh Mar 2 '16 at 6:37
  • $\begingroup$ Also I found out that a similar language B and therefore $U_B$ can be used to get $NP^B \neq NL^B$ if we allow the machines $M_i$'s in BGS to use only $n_i/10$ space, which means it will be difficult to prove $NL = NP$ or $NL \neq NP$ (at least by relativization techniques). $\endgroup$ – Shreesh Mar 2 '16 at 6:42
  • $\begingroup$ You are right, this trivial way to write decision problems as binary relations is even exploited in the typical proof of BGS. I now also see where (an explicit example proving) the fact that NL and NP compute different binary relations will be needed when adopting the BGS construction to NL vs NP. The language basically has to ask whether the intersection of the oracle language with the "separating" binary relation is empty for a given input length. (If your language B doesn't exploit the existence of such a "separating" binary relation, then I doubt that your construction will work...) $\endgroup$ – Thomas Klimpel Mar 2 '16 at 10:02

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.