10
$\begingroup$

Many complexity classes have "complete" problems. Do complete problems exist for the complexity class of problems that can be solved in $O(1)$ time?

A complication is that this class depends on the model of computation; a problem can be solvable in $O(1)$ time in one reasonable model of computation but not another, given that "reasonable" typically means polynomial-time equivalence with a Turing machine. However, it could still be worked out for specific reasonable models.

I think it makes the most sense to look at constant-time many-one reductions. However, I'm also open to looking at other sensible reductions if there is literature on them.

Does anything like this exist, or has it been studied, for any model of computation?

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
3
$\begingroup$

Since reading the input is necessary for almost all problems, we need at least $\Omega(n)$ time for nearly all problems, where $n$ is the size of the input. Therefore, you may think of the class of linear time problems, which is already defined.

However, we still do not know any $O(n)$-complete or $O(n^2)$-complete problem. The field of fine-grained complexity has some new results in this area, but the classes are problem-based (for example, APSP is equivalent to Radius, Negative Triangle, ...).

Improve this answer
$\endgroup$
7
  • $\begingroup$ I'm not sure whether this answers the question. Many problems require $\Omega(n)$ time, but not all of them -- there are still some problems that can be solved in $O(1)$ time -- so it seems like the question that was asked remains relevant. $\endgroup$
    – D.W. ♦
    Jun 15, 2017 at 17:08
  • 1
    $\begingroup$ This also assumes input must be read sequentially and there's no indirection, so this would be one of those instances where the model really does matter. (I'm wondering if I should insist on indirection and possibly randomness in my original post, as otherwise you run into a bunch of trivial roadblocks like this) $\endgroup$
    – Mike Battaglia
    Jun 15, 2017 at 17:25
  • $\begingroup$ Problem to decide if anything is given as input takes $O(1)$ time. All other problems that take constant time are bounded constant versions of other problems. $\endgroup$
    – rus9384
    Jun 15, 2017 at 17:26
  • $\begingroup$ What do you mean by "bounded constant versions of other problems," exactly? $\endgroup$
    – Mike Battaglia
    Jun 15, 2017 at 19:02
  • $\begingroup$ @MikeBattaglia, for example, if Turing machine will halt after performing 100 steps. $\endgroup$
    – rus9384
    Jun 16, 2017 at 7:53
3
$\begingroup$

I think that for $O(1)$ problems, all languages are complete under "constant-time reductions" except $L = \Sigma^*$ and $L = \emptyset$

Suppose that $L, L' \in O(1)$ and $L \neq 0, L \neq \Sigma^*$

Let $x_Y \in L, x_N \notin L$

This is a constant-time reduction from $L'$ to $L$:

  • given $x$ solve $L'$ in $O(1)$ time
  • if $x \in L'$ then output $x_Y$, otherwise output $x_N$

So $L$ is complete for $O(1)$ (... lazy reduction, lazy result :-)).

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ In general, hardness for a class $C$ is not meaningfully defined for reductions that are as powerful as $C$ itself, for exactly the reason you stated. To have a meaningful definition of TIME($O(1)$)-complete, we would need reductions that are weaker than constant time. I don't know what those could be. $\endgroup$
    – Pontus
    Jun 16, 2017 at 7:40
  • $\begingroup$ @Pontus: I agree; and definitely not so interesting ... unless we are living in a discrete and finite universe :-D $\endgroup$
    – Vor
    Jun 16, 2017 at 9:05
  • $\begingroup$ ... we could use $k$ steps reductions ($k$ fixed), but in this case there are no complete problems ... or add a constraint between the size of the TM and the number of constant steps (e.g. if the size of the (deterministic/nondeterministic) TM is $n$ then only $n / 2$ steps are allowed) ... $\endgroup$
    – Vor
    Jun 16, 2017 at 9:13
  • $\begingroup$ Yes, perhaps something interesting can (or has been) made up. What is the TM in your last suggestion? $\endgroup$
    – Pontus
    Jun 16, 2017 at 9:32
  • $\begingroup$ @Vor What about fixed time constant width in some parallel model? $\endgroup$
    – l4m2
    Dec 18, 2019 at 11:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.