6
$\begingroup$

I know that there are complexity classes that are "below" P like L or NL and stuff like that. But I was curious to know where sub linear time algorithms fitted in this picture and maybe how they were related to the P vs NP problem or if they had their own version of something similar. I am aware that this question might lead to a list of open problem in sublinear time algorithms or something similar, which is a fine answer to my question. I am also curious to know what we know about this theory and what we don't know or what are open problems to tackle.

[I tried adding the tag sublinear time algorithms but I am not sure if it exists. Feel free to add a tag that might help]

$\endgroup$
  • 1
    $\begingroup$ I think you meant "sublinear time" not "sublinear space". Am I right? In small resources, the computational model you picked can also be very essential. Are you interested in the complexity classes of some problems or some algorithms or both. I am not sure whether it is helpful for you, but, I found for example this site - cs.tau.ac.il/~ronitt/COURSES/F09course/index.html - after a short Googling. $\endgroup$ – Abuzer Yakaryilmaz Jan 9 '14 at 20:39
  • 1
    $\begingroup$ Furthermore it is not correct to say '...classes that are "below" P like L or NL ...'; indeed L =? P is an open problem (and L =? NL is also an open problem). $\endgroup$ – Marzio De Biasi Jan 9 '14 at 21:50
  • 1
    $\begingroup$ @MarzioDeBiasi Sublinear time algorithms are well defined and indeed they do not read their entire input. The field of property testing studies many such questions. $\endgroup$ – Suresh Venkat Jan 9 '14 at 21:52
  • 1
    $\begingroup$ A whole new world (for me) ... sublinear.info :-D !! $\endgroup$ – Marzio De Biasi Jan 9 '14 at 22:08
  • 1
    $\begingroup$ @MarzioDeBiasi Note that it only makes sense to talk about sublinear-time algorithms in random access models of computation. Any ordinary Turing machine that runs in sublinear time actually runs in constant time: if it doesn't know what $n$ is, it can't terminate in $\log n$ time or $\sqrt{n}$ time because it can't distinguish an input of length $n$ from one of length $2^n$ or anything else. $\endgroup$ – David Richerby Jan 10 '14 at 0:24
7
$\begingroup$

Sublinear time algorithms (as well as sublinear space algorithms) are indeed an active area of research. The field of property testing covers much of the sublinear time regime, and I'll point you to the property testing blog to learn about recent work in the area.

The question about complexity theory relating to this is very interesting, and is also an active area of research. P vs NP might not exactly be the right analogy here, but you're right that the boundary between computation and verification is something where sublinearity changes things.

In particular, you can look at a PCP as "kind of" doing something sublinear, in that it only inspects a few bits of a long proof in order to check the prover's claim. More generally, there's been recent work prover-verifier systems where the verifier runs in sublinear time. Some references that are worth perusing:

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I think it seems "intuitive" that whatever the complexity class of sublinear time algorithms is not equal to P. But do we actually have a proof of this? $\endgroup$ – Charlie Parker Jan 9 '14 at 22:16
  • 2
    $\begingroup$ @CharlieParker: even regular languages are a superset of the languages that can be recognized in sublinear time (just pick $L= \{ w \in\{0,1\}^* | $ the parity of w is 0 $\}$) $\endgroup$ – Marzio De Biasi Jan 9 '14 at 22:29

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.