Table of Contents for Programming Languages: a survey

? any well known ones? todo

- linear programming problem
- prolog
- NP-complete instance
- pushdown
- regex
- DFA, NFA
- Relational algebra and relational calculus
- https://en.wikipedia.org/wiki/Relational_algebra
- XQBE http://wwwconference.org/www2003/cdrom/papers/poster/p291/p291-braga.html (XQuery is Turing-complete, this isn't)
- "

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

- horn clauses
- some description logics

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)

- computably enumerable
- decidable

- context-sensitive
- Linear-bounded automaton

- indexed
- one-way nondeterministic nested stack automata

- various mildly context-sensitive languages
- various automata, including thread automaton

- https://en.wikipedia.org/wiki/Tree-adjoining_grammar

- context-free
- Nondeterministic pushdown

- deterministic context-free
- deterministic pushdown

- Visibly pushdown
- Visibly pushdown

- regular
- finite automaton (both NFA and DFA, that is, non-deterministic and deterministic)

- star-free
- https://en.wikipedia.org/wiki/Aperiodic_finite_state_automaton finite-state automata, regular languages (and regular expressions), pushdown automata, context-free languages, formal grammars

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

- https://en.wikipedia.org/wiki/USTCON
- the problem of determining whether there exists a path between two vertices in an undirected graph, otherwise described as the problem of determining whether two vertices are in the same connected component. This problem is also called the undirected reachability problem.

Nondeterministic Logarithmic-space

- ST-connectivity ( https://en.wikipedia.org/wiki/STCON )
- 2-satisfiability.

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:

- https://www.google.com/search?client=ubuntu&channel=fs&q=Primitive+recursive+hierarchy&ie=utf-8&oe=utf-8#channel=fs&q=%22Primitive+recursive%22+hierarchy
- http://www.jstor.org/discover/10.2307/1993169?uid=3739560&uid=2129&uid=2&uid=70&uid=4&uid=3739256&sid=21102567087501 On a subrecursive hierarchy and primitive recursive degrees by Axt
- https://www.google.com/search?client=ubuntu&channel=fs&q=Elementary+function+arithmetic+induction+&ie=utf-8&oe=utf-8#channel=fs&q=%22Elementary+function+arithmetic%22++induction+bounded
- http://mathoverflow.net/questions/46350/between-mu-and-primitive-recursion
- http://mathoverflow.net/questions/35461/interesting-complexity-classes-pr-subsetneq-c-subsetneq-r
- http://math.stackexchange.com/questions/388518/growth-rate-vs-totality/388559#388559
- http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.3374 "Characterizing the Grzegorczyk hierarchy by safe recursion"
- http://web.archive.org/web/20130507093618/http://www.nomachetejuggling.com/files/complexity_zoo.pdf
- http://www.cs.toronto.edu/~bor/Papers/subrecursive.pdf