# Where do sublinear time algorithms fit in the picture of complexity theory?

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]

• 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. Jan 9 '14 at 20:39
• 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). Jan 9 '14 at 21:50
• @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. Jan 9 '14 at 21:52
• A whole new world (for me) ... sublinear.info :-D !! Jan 9 '14 at 22:08
• @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. Jan 10 '14 at 0:24

• @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 $\}$) Jan 9 '14 at 22:29