<p>Sublinear time algorithms (as well as sublinear <em>space</em> algorithms) are indeed an active area of research. The field of <strong>property testing</strong> covers much of the sublinear time regime, and I'll point you to the <a href="http://ptreview.sublinear.info/">property testing blog</a> to learn about recent work in the area. </p>

<p>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. </p>

<p>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:</p>

<ul>
<li><a href="http://privacytools.seas.harvard.edu/publications/interactive-proofs-proximity-delegating-computation-sublinear-time">Interactive proofs of proximity: delegating computation in sublinear time</a></li>
<li><a href="http://eccc.hpi-web.de/report/2013/078/">Non-Interactive Proofs of Proximity</a></li>
</ul>

CC BY-SA 3.0
2014-01-09T22:16:22.800Z
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?
Charlie Parker
CC BY-SA 3.0
2014-01-09T22:29:35.537Z
@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 $\}$)
Marzio De Biasi
CC BY-SA 3.0
2014-01-09T22:00:35.370Z
2014-01-09T22:00:35.370Z
Suresh Venkat
<p>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.</p>

<p>[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]</p>

CC BY-SA 3.0
2014-01-09T20:39:37.870Z
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 - http://www.cs.tau.ac.il/~ronitt/COURSES/F09course/index.html - after a short Googling.
Abuzer Yakaryilmaz
CC BY-SA 3.0
2014-01-09T21:42:23.047Z
I took for granted the word time or space (for some reason), but I meant time. I will correct that.
Charlie Parker
CC BY-SA 3.0
2014-01-09T21:46:57.500Z
But I think that "sublinear time" is not meaningful: in sublinear time the Turing machine hasn't enough time to read the whole input!?!
Marzio De Biasi
CC BY-SA 3.0
2014-01-09T21:50:03.410Z
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).
Marzio De Biasi
CC BY-SA 3.0
2014-01-09T21:51:56.710Z
True the TM can't read the whole input. But algorithms are TM. And sublinear algorithms are just TM that don't read their whole input.  But nevertheless, they are still valid TM. I think that saying they are not meaningful just because they don't read the whole input is not "correct". They are still valid models and have real researchers at real Universities (like MIT) working on them. Maybe the motivation to design them came from the "real" world like Big data, but they could have been studied, independent of their application. I still think they are meaningful and an interesting.
Charlie Parker
CC BY-SA 3.0
2014-01-09T21:52:50.540Z
@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.
Suresh Venkat
CC BY-SA 3.0
2014-01-09T22:00:38.440Z
@SureshVenkat, CharlieParker ... sorry, you are right! I was thinking of o(n) in the standard TM model and I was not aware of the whole "sublinear algorithms" area :-)
Marzio De Biasi
CC BY-SA 3.0
2014-01-09T22:03:01.583Z
sure, don't worry. :)
Charlie Parker
CC BY-SA 3.0
2014-01-09T22:08:58.590Z
A whole new world (for me) ... [sublinear.info](http://sublinear.info/index.php?title=Open_Problems:By_Number) :-D !!
Marzio De Biasi
CC BY-SA 3.0
2014-01-10T00:24:54.570Z
@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.
David Richerby
<cc.complexity-theory><ds.algorithms>
Where do sublinear time algorithms fit in the picture of complexity theory?
Charlie Parker
# Where do sublinear time algorithms fit in the picture of complexity theory?

(Asked by: username_0 on 2014-01-09)

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]

**Tags:** cc.complexity-theory, ds.algorithms

> **Comments:**
> **username_1**: 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 - http://www.cs.tau.ac.il/~ronitt/COURSES/F09course/index.html - after a short Googling.  
> **username_0**: I took for granted the word time or space (for some reason), but I meant time. I will correct that.  
> **username_2**: But I think that "sublinear time" is not meaningful: in sublinear time the Turing machine hasn't enough time to read the whole input!?!  
> **username_2**: 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).  
> **username_0**: True the TM can't read the whole input. But algorithms are TM. And sublinear algorithms are just TM that don't read their whole input.  But nevertheless, they are still valid TM. I think that saying they are not meaningful just because they don't read the whole input is not "correct". They are still valid models and have real researchers at real Universities (like MIT) working on them. Maybe the motivation to design them came from the "real" world like Big data, but they could have been studied, independent of their application. I still think they are meaningful and an interesting.  
> **username_3**: @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.  
> **username_2**: @SureshVenkat, CharlieParker ... sorry, you are right! I was thinking of o(n) in the standard TM model and I was not aware of the whole "sublinear algorithms" area :-)  
> **username_0**: sure, don't worry. :)  
> **username_2**: A whole new world (for me) ... [sublinear.info](http://sublinear.info/index.php?title=Open_Problems:By_Number) :-D !!  
> **username_4**: @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.  

---

## 1 answers

### Answer by username_3 on 2014-01-09. Score: 7 | Accepted answer

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](http://ptreview.sublinear.info/) 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:

* [Interactive proofs of proximity: delegating computation in sublinear time](http://privacytools.seas.harvard.edu/publications/interactive-proofs-proximity-delegating-computation-sublinear-time)
* [Non-Interactive Proofs of Proximity](http://eccc.hpi-web.de/report/2013/078/)

> **Comments:**
> **username_0**: 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?  
> **username_2**: @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 $\}$)  

---

