<p>In terms of machine model, I'm interested in multitape Turing machines with random access to the input via a query tape.</p>
<p>Criteria for &quot;interesting&quot; in this context:</p>
<ul>
<li>Not in <span class="math-container">$DLogTime$</span>: &quot;what's the length of the input&quot; falls into this category</li>
<li>Depends on the whole input: a padded decision version of Factoring is a problem in the desired class, but ignores most of the input and is just a rescaled problem in <span class="math-container">$NP \cap coNP$</span>.</li>
<li>Isn't a promise problem: &quot;Given two lists of bits A and B, promised that exactly one of them is identically zero, is A identically zero?&quot; is in the desired class, but is a promise problem such that the promise isn't in the desired class.</li>
</ul>
<p>It's also very possible no such problem exists -- it might be that &quot;any non-promise problem in <span class="math-container">$NLogTime \cap coNLogTime$</span> that depends on the whole input is also in <span class="math-container">$DLogTime$</span>&quot; -- which would also be an interesting answer.</p>

CC BY-SA 4.0
2023-10-30T21:50:49.463Z
Something possibly relevant: I know that every decision tree has both an equivalent CNF and an equivalent DNF (that are not much bigger). I believe these are the uniform counterparts of coNLogTime and NLogTime *with an oracle in NLogTime*, i.e. they are one level up the LogTime hierarchy than the ones you are asking about. Phrased otherwise, something like evaluation of a decision tree should be in $\Pi_2$-LogTime $\cap$ $\Sigma_2$-LogTime (assuming the CNF / DNF conversions go through uniformly). Perhaps some restricted form of Decision Tree might no longer need the extra NLogTime oracle.
Anupam Das
CC BY-SA 4.0
2023-11-01T15:40:11.157Z
...but in fact, doesn't any NLogTime predicate $P$ necessarily have polynomial-size clauses, i.e.  $P(x) \iff \bigvee L^P_{|x|}$ for $L^P_{|x|}$ a set of literals depending on $|x|$ (dually, terms $\bigwedge L^Q_{|x|}$, for any coNLogTime predicate $Q$) ? If so then even $P \subseteq Q$ is equivalent to $L^P_n = L^Q_n = \{l_n\}$ for some literal $l_n$, for each $n$. It feels like the value of such $l_n$ should be readily computed in DLogTime by restricting to some/any path through an NLogTime machine for $P$ (or a coNLogTime machine for $Q$).
Anupam Das
<turing-machines><nondeterminism>
"Interesting" problems in $NLogTime \cap coNLogTime$
Jake
# "Interesting" problems in $NLogTime \cap coNLogTime$

(Asked by: username_0 on 2023-10-26)

In terms of machine model, I'm interested in multitape Turing machines with random access to the input via a query tape.

Criteria for "interesting" in this context:

* Not in $DLogTime$: "what's the length of the input" falls into this category
* Depends on the whole input: a padded decision version of Factoring is a problem in the desired class, but ignores most of the input and is just a rescaled problem in $NP \cap coNP$.
* Isn't a promise problem: "Given two lists of bits A and B, promised that exactly one of them is identically zero, is A identically zero?" is in the desired class, but is a promise problem such that the promise isn't in the desired class.

It's also very possible no such problem exists -- it might be that "any non-promise problem in $NLogTime \cap coNLogTime$ that depends on the whole input is also in $DLogTime$" -- which would also be an interesting answer.

**Tags:** turing-machines, nondeterminism

> **Comments:**
> **username_1**: Something possibly relevant: I know that every decision tree has both an equivalent CNF and an equivalent DNF (that are not much bigger). I believe these are the uniform counterparts of coNLogTime and NLogTime *with an oracle in NLogTime*, i.e. they are one level up the LogTime hierarchy than the ones you are asking about. Phrased otherwise, something like evaluation of a decision tree should be in $\Pi_2$-LogTime $\cap$ $\Sigma_2$-LogTime (assuming the CNF / DNF conversions go through uniformly). Perhaps some restricted form of Decision Tree might no longer need the extra NLogTime oracle.  
> **username_1**: ...but in fact, doesn't any NLogTime predicate $P$ necessarily have polynomial-size clauses, i.e.  $P(x) \iff \bigvee L^P_{|x|}$ for $L^P_{|x|}$ a set of literals depending on $|x|$ (dually, terms $\bigwedge L^Q_{|x|}$, for any coNLogTime predicate $Q$) ? If so then even $P \subseteq Q$ is equivalent to $L^P_n = L^Q_n = \{l_n\}$ for some literal $l_n$, for each $n$. It feels like the value of such $l_n$ should be readily computed in DLogTime by restricting to some/any path through an NLogTime machine for $P$ (or a coNLogTime machine for $Q$).  

---

## 0 answers

