2
$\begingroup$

I'm interested in talking about fine-grained time complexity in a model-invariant way. For example, classes like $\text{DTIME}(n^{2+o(1)})$. The standard practice is apparently to define such classes in terms of a specific model. Are there other ways to do it that respect some amount of invariance?

I figured out one way that apparently works, which I'll present as an example, although it's not completely satisfactory. Let $\frak{M}$ be the equivalence class of models that have mutual time-translations satisfying $T'(n) = T(n)^{1+o(1)} \times S(n)^{O(1)}$ and space-translations satisfying $S'(n) = S(n)^{O(1)}$. That is, instead of considering polynomial time-translations as we would to construct the robust classes like $\text{P} = \text{DTIME}(n^{O(1)})$, define the class of models with mutual time-translations that are essentially linear in time but polynomial in space. This is a smaller class, but it still contains a variety of models, like single-tape Turing machines, multi-tape Turing machines, and some RAM models. Now, define:

$\text{DTIME}^*(S) = \displaystyle\bigcap_{M \in \frak{M}}{\text{DTIME}_{M}(S)}$

I think it is not hard to show that $\text{DTIME}^*$ is compatible with the robust classes, for example, $\text{DTIME}^*(n^{O(1)}) = \text{DTIME}(n^{O(1)}) = \text{P}$. But we also get something extra, the ability to talk about specific polynomial exponents: whenever we know that a problem is in $\text{L}$ and we have an effective space bound $k \times \log_2{(n)}$ then we can also place it in a specific class $\text{DTIME}^*(n^{k+o(1)})$. If it's a problem not known to be in $\text{L}$, for example edit distance, then we can't do that, but we still know edit distance is in $\text{DTIME}^*(n^{O(1)})$, since that's just $\text{P}$. This definition also yields specific bases for exponential-time functions and in this case the lack of effectivity is not as crippling to my program since these are often search problems that are in $\text{PSPACE}$ anyway. For example we can prove that $\text{SUBSET-SUM} \in \text{DTIME}^*(2^{n+o(1)})$ since trying all possibilities uses only linear space, but maybe not that $\text{SUBSET-SUM} \in \text{DTIME}^*(2^{\frac{n}{2}+o(1)})$, since that algorithm uses exponential space.

This seems like a valid and possibly useful alternative to a model-specific definition of $\text{DTIME}$ but I've never heard of it before. Can anyone point me to a reference for this construction, or an equivalent way of understanding it?

And is there a different way to define fine-grained time complexity that isn't model-specific?

EDIT: I found this example of a model-invarant theorem. The result can seemingly be restated as $\text{SAT} \notin \text{DTIME}^*(n^{\sqrt{3}+o(1)})$ without explicit mention of a model or a space restriction. There is some discussion of machine models in this paper that I'm not really understanding, but it doesn't seem to be answering my question in terms of describing time-complexity itself in a model-invariant way.

$\endgroup$

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.