the scientific landscape 
 representation (models, semantics) 

 logic & reasoning  complexity & metrics  category of relations  

 meaning
 linguistic glossary  components & datatypes  
Location: http://www.mun.ca/~ulf/gloss/complex.html.
By Ulf Schünemann since 2001.
Please mail any comments.

CHECK: A Data Model for ObjectOriented Design Metrics (1997)
Johann Eder, Gerti Kappel, Michael Schrefl: Coupling and Cohesion in ObjectOriented Systems (1992)
x ++ y > y=x+z > ++ ^ (A) z   
Two channels (A) and (B)
with a 2bit information source x (values 0,1,2,3) as input,
an endpoint y (values 0,1,2,3,4 in (A), values 0,1,2,3 in (B)) as output,
and a 1bit noise signal z (values 0,1).

x ++ y > y=x*z > ++ ^ (B) z   
in bits (rounded)  
(A)  (B)  
H(x)  entropy of x = medium information content  2  

2  



H(z)  entropy of x  1  

1  

 
H(y)  entropy of y  9/4  


31/20  

 
H(xy)  signal equivocation = the receiver's uncertainty what the sender actually sent (``disturbed'' information)  3/4  
24/20  


H(yx)  signal dissipation (the sender's uncertainty what the receiver will receive)  1  

15/20  
 
T(x,y)  signal transinformation = information of x manifest in y (``undisturbed'' information) = H(x)  H(xy) = H(y)  H(yx)  5/4  
16/20  

H(zy)  noise equivocation  3/4  
9/20  


H(yz)  noise dissipation  2  

1  


T(z,y)  noise transinformation.  1/4  11/20  
I_{L}(y)  latent information = information in y overlapping from x and z = H(y)  T(x,y)  T(z,y). The manifest information is T(x,y) + T(z,y)  3/4  
4/20  

?  information lost unrecoverably  0  1  
x ++ y ++ u > y=x+z > u=yz > ++ ++ ^ ^ z _______________   The channel extended by an information processor reading the channel's endpoint y and the noise z and ``calculating'' output u. The processor recovers the disturbed information, i.e., converts the information about x which was latent in y back to manifest information in u. 
computability  complexity theory  algorithm theory  formal languages 
Text colors: black for complexity/power classes, green for solvers,
problems from [Hopcroft+Ullman] or from elsewhere
det = deterministic, ndet = nondeterministic, c.f. = contextfree, LC = lambdacalculus
Main reference [Hopcroft, Ullman: Introduction to automata theory, languages and computation; 1979]
also [F Henglein, H Mairson: The Complexity of Type Inference for HigherOrder Typed Lambda Calculi; POPL'91]
also [N Immerman: Languages That Capture Complexity Classes; SIAM Journal of Computing 1987]
also [A ArratiaQuesada, S Chauhan, I Stewart: Hierarchies in classes of program schemes; Journal of Logic and Computation 1999]
also [I Stewart: Logical definability versus computational complexity: another equivalence]
Cf. the hierarchy at wikipedia
and the huge list of complexity classes and results at the Complexity Zoo
Computable, RE (recursively enumerable) coRE, RE a syntactic class: RE functions can be explicitly enumerated [zoo] Turing complete solvers:Turing machines; 2stack machines; counter machines; RAM; recursive functions; while programs; Chomsky grammars  Decidable, R (recursive) =REcoRE; PR [cf. Ackermann] a semantic class: R functions cannot be explicitly enumerated [zoo]  PR (primitive recursive) elementary a syntactic class: PR functions can be explicitly enumerated  Elementary relation to EXPSPACE? (union of DTIME(2^{n}), DTIME(2^{2n}), DTIME(2^{22n}), etc.)  EXP SPACE EXP  EXP [TIME] =PSPACE?, P  PSPACE =NPSPACE; includes NP and coNP (solvable in polynomial space) Buechi automata;  NP (includes RP, =RP?) (solvable ndet'ly in polynomial time) ESO (second order existential logic) [theorem by Fagin 74  found in Imm] ·········coNP (=NP?, includes coRP, =coRP?) Problem in NP and coNP: integer factorization [wiki]  NLIN (=NTIME(n)?) (solvable ndet'ly in linear time on RAM) [cf. page 12]  NTIME(n) (solvable ndet'ly in linear time on TM) [cf. page 12]  CFL (contextfree) (below NTIME(n) and CSL[cf. page 12], unknown rel. to NL; diagram in wiki shows CFL below NC) stack machines ("pushdown automata" PDA), contextfree grammars (CFG)  nonregular CFL ...  
RP
(includes P, =P?, sub of coNP?) Randomized Polynomial time defined wrt. probabilistic TMs eg. isnonprime ·········coRP (=RP?, includes P, =P?) eg. isprime  P (=NC?[wiki]) (solvable det'ly in polynomial time, "tractable problems") least fixed point logic (first order logic with least fixed point primitive) [Imm]; path system logic [mentioned in Arr+] [less?] NSPS (NPS with stack) [Arr+] 
CSL (context sensitive)
= NSPACE(n), ie. solvable ndet'ly in linear space [Kur64] primitive recursive functions (equiv. to loop); loop programs; context sensitive grammars (CSG)  REG (regular)
=DSPACE(O(1)) ie. constant space, =NSPACE(O(1)) finite automata (DFA=NFA), regular expressions, monadic ESO[cf]  
DSPACE(n) (solvable det'dly in linear space)  L (solvable det'ly in logarithmic space)  
NL =coNL (solvable ndet'ly in logarithmic space) transitive closure logic (first order logic with special transitive closure primitive)[Imm]; NPS program schemes [Arr+]  
NC
Nick's Class (includes NL) (solvable in (log n)^{c} time on n^{k} parallel processors, eg. parallelRAM = decidable by uniform Boolean circuits with polylogarithmic depth and a polynomial number of gates)  NLcomplete (hardest in NL):  GAP  reachability in directed graph [by Savitch 73  found in Imm]  
(n log n)space, etc, ...  
Pcomplete (hardest in P, "probably not parallelizable" / "probably inherently sequential") 
· [complete or maybe simpler?]
type inference for the simplytyped (firstorder) LC
· evaluating a propositional formula for given values · emptiness of CFGs' languages · CFG membership [wiki] CVP  Circuit Value Problem: calculate output of given gate in given circuit for given inputs [wiki] · linear programming [wiki] · game of life [wiki] · LZ78 compression [wiki]  
NPcomplete (hardest in NP, "probably intractable")
·········coNPcomplete (hardest in coNP) 
SAT  satisfyability of unquantified formula = evaluation of existentially quantified formula
Vertex Cover; Hamilton Circuit; Integer Linear Programming; Chromatic Number; TSP (traveling salesman); Exact Cover; Knapsack; Partition (of integer lists); Tetris, Minesweeper ··········is a structural subtyping entailed by a set of subtyping constraints  
PSPACEcomplete (hardest in PSPACE) known to be disjoint from NC; maybe subset of P or NP? 
·type inference in the presence of subtyping over ground & function types
QBF  evaluation of quantified Boolean formulas L_{cs}  wordproblem for CSLs  
EXPTIMEcomplete  · best move in Chess or Go on an n × n board [wiki]  
EXPSPACEcomplete (hardest problems solvable in exponential space): 
L_{rex}  does a regular expressions with exponentiation denote all strings?
· two regular expressions with star represent different languages? [wiki]  
harder than any problem ndet'ly solvable in exponential time: 
· is an untyped term typable in the second order polymorphic LC (aka F_{2})? [Hen+]
· the theory of reals with addition  
nonelementary time: 
· Is an untyped term typable in F_{omega}? [Hen+]
· Is the normal of two lambdaterms typable in firstorder typed LC the same? · Evaluation of formula with quantific. over (higherorder) Booleans functions  
nonprimitive recursive:  · the Ackermann function  
semidecidable (REcomplete): 
· The Halting Problem is the canonical REcomplete problem [zoo]  determining, in F_{<}'s type system, whether one type is subtype of another L_{u}  pairs of TM encoding and accepted word PCP  Post's Correspondence Problem · ambiguity of CFGs, inherent ambiguity of CFLs · CFG accepts everything, · intersection of the languages of two CFGs is empty / is c.f. · inverse of CFG's language is c.f. · CFG's language is regular  
noncomputable  cf. hypercomputation:
TMs with oracles, and some forms of Quantum computers, ... Arithmetic hierarchy: The halting problem for _{n} sits in _{n+1} 
L_{d}  the diagonal language of TM encodings
L_{e}, L_{r}, L_{nr}  emptiness / recursiveness / nonrecursiveness of a TM's language · TM accepts everything, accepts exactly one word, accepts a regular set 
Cf. Design and Analysis of Algorithms with some complexity examples.
For some of the (shown and further) complexity classes it has not yet been proven whether they are in fact separate or only appear so. Especially, the possibility of ``P = NP'' is repeatedly considered, and there are several results on the implication should it be true, but no proof put forward so far has been accepted by the scientific community (it would reclassify NPcomplete problems from intractable to P). ``NP = NL?'' (ndet. polynomial time v. ndet. logarithmic space) is discussed here.
Further classes: