Table of Contents for Programming Languages: a survey
? any well known ones? todo
An example of a widespread system that is not Turing Complete is Relational Algebra, the theoretical basis behind SQL as described in Codd's paper A relational model for large shared data banks. Relational Algebra has the property of Godel Completeness, which means that it can express any computation that can be defined in terms of first-order predicate calculus (i.e. ordinary logical expressions). However, it is not Turing-Complete as it cannot express an arbitrary algorithmic computation.
Note that most if not all all practical SQL dialects extend the pure relational model with procedural constructs to the extent that they are Turing Complete by the definition as normally applied to programming languages. However, an individual SQL query by and large is not." -- http://stackoverflow.com/a/449156/171761
toread: Subrecursive Programming Systems: Complexity & Succinctness (Progress in Theoretical Computer Science) by James S. Royer and John Case.
arguments for protocols to be context-free or regular: http://www.cs.dartmouth.edu/~sergey/langsec/occupy/ and http://www.cs.dartmouth.edu/~sergey/langsec/
https://en.wikipedia.org/wiki/Template:Formal_languages_and_grammars
within each type, the most general subtypes are listed first, e.g. you have strict containment as you go down this list (todo doublecheck this for the stuff in type 1)
For each class we list some complete problems of that class.
i think we have some strict containments known except for NP, which may be nonstrict: L < NL < CC < P <= NP
i don't know where NC fits it. NC^1 < L.
There's also some circuit classes ACC0 and TC0
"decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors.", equivalently "those decision problems decidable by a uniform Boolean circuit (which can be calculated from the length of the input) with polylogarithmic depth and a polynomial number of gates." "the problems solvable on an alternating Turing machine restricted to at most two options at each step with O(log n) space and (\log n)^{O(1)} alternations.[6]" -- https://en.wikipedia.org/wiki/NC_%28complexity%29
NC = AC.
logspace
https://en.wikipedia.org/wiki/L_%28complexity%29
equivalent to https://en.wikipedia.org/wiki/SL_%28complexity%29
Nondeterministic Logarithmic-space
see also https://en.wikipedia.org/wiki/NL-complete
https://en.wikipedia.org/wiki/CC_%28complexity%29
(deterministic) polynomial time
https://en.wikipedia.org/wiki/P-complete
interesting subclasses within P are linear , nlogn ('linearithmic'), quasilinear, Sub-quadratic, and quadratic.
todo: http://mathoverflow.net/questions/80612/structure-of-class-p notes that the complexity classes of quadratic etc are not closed under composition and are sensitive to the definition of your machine, since different machine definitions sometimes tend to have polynomial effects on time. However imo it would still be interesting to find linear-complete, linearithmic-complete, quasilinear-complete, sub-quadratic-complete, and quadratic-complete problems (besides the obvious emulation of Turing machines running FOR loops) for logtime or logspace reductions on the most common machine model (I'm guessing a RAM Turing machine, but really we want whichever model gives us the results in https://en.wikipedia.org/wiki/Time_complexity#Complexity_classes such as linear to search every element in an arrya, n log n for quicksort, n^2 for bubble sort, n^3 for naive matrix multiplcation. Or, if logtime or logspace reductions are too restrictive, then try linear time reductions, or possibly just (n - 1) time reductions for polynomial times of degree n. here's a paper on the structure of quasilinear time: http://www.cse.buffalo.edu/~regan/papers/pdf/NRS95.pdf "On Quasilinear Time Complexity Theory" Ashish V. Naik, Kenneth W. Regan, D. Sivakumar.
https://en.wikipedia.org/wiki/List_of_NP-complete_problems
https://en.wikipedia.org/wiki/Grzegorczyk_hierarchy
(i find that one less interesting for our purposes b/c of the arbitrary-seeming restriction on primitive recursion)
also look into these and see if they are relevant:
https://en.wikipedia.org/wiki/Slow-growing_hierarchy https://en.wikipedia.org/wiki/Fast-growing_hierarchy
todo check out http://www.cstheory.com/stockmeyer@sbcglobal.net/survey.pdf for more todo read http://stackoverflow.com/questions/13899274/algorithmic-task-which-requires-quadratic-time todo read http://cs.stackexchange.com/questions/10886/the-complexity-class-fp
also there's the primitive recursive FUNCTIONALS
other toreads: