9
$\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?

$\endgroup$
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, ...).

$\endgroup$
  • $\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 '17 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 '17 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 '17 at 17:26
  • $\begingroup$ What do you mean by "bounded constant versions of other problems," exactly? $\endgroup$ – Mike Battaglia Jun 15 '17 at 19:02
  • $\begingroup$ @MikeBattaglia, for example, if Turing machine will halt after performing 100 steps. $\endgroup$ – rus9384 Jun 16 '17 at 7:53
2
$\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 :-)).

$\endgroup$
  • 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 '17 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 '17 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 '17 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 '17 at 9:32

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.