List of theorems of computer science
C.
- Cook's theorem : There is a subset of NP to which all problems from NP can be polynomially reduced. This subset is called NP-complete .
- CAP Theorem : In a distributed system , it is impossible to simultaneously the three properties C onsistency ( consistency ) A vailability ( availability ) and P artition Tolerance ( fault tolerance ) guarantee.
F.
- Theorem of Friedberg and Muchnik : There are recursively enumerable Turing degrees that really lie between 0 (degree of decidable sets) and 0 '(degree of holding problems ).
H
- Set of Herbrand : Be a closed formula in Skolem , then then unrealizable exactly if there is a finite subset of the Herbrand expansion is that - in the propositional sense - is unattainable.
- Hierarchy sets: time and space complexity classes each form a hierarchy, so they can be set in a real subset relationship. The following applies: and .
I.
- Immerman and Szelepcsényi's theorem : The complexity class NL is closed with complement formation.
L.
- Set of Ladner : If true, there are problems which neither NP-complete are still in P lie.
M.
- Set of Myhill : A set of natural numbers is if and creative when they complete for the class of all recursively enumerable is amounts.
- Myhill's isomorphism theorem : Two sets of natural numbers are recursively isomorphic if and only if they are one-one-equivalent .
- Theorem of Myhill-Nerode : A deterministic finite automaton exists that accepts the formal language if and only if the index of the associated Nerode relation is finite. ( So under this condition is regular .)
N
- No-Free-Lunch-Theorems : There is no single search algorithm that is equally best for all problems.
- Nyquist - Shannon sampling theorem : A continuous, band-limited signal with a minimumfrequencyof 0 Hz and a maximum frequencymust besampledat a frequency greater thanthat, so that the original signal can be reconstructed from the time-discrete signal without loss of information.
P
- The pumping lemma : Property of certain classes of formal languages, suitable to prove that a formal language is not regular or not context-free.
R.
- Recursion theorem ( Kleene's fixed point theorem ): For a given source code modification program, a source code can always be found that does not mind the modification.
- Rice's Theorem : It is generally not possible to algorithmically prove any aspect of its functional behavior for a given algorithm.
S.
- Theorem of Savitch : A problem that can be solved by a nondeterministic Turing machine with a certain space complexity can be solved on a deterministic Turing machine with a square higher space bound. This results in the equality of PSPACE and NPSPACE .
- Shannon's theorem : The theorem gives a characterization of perfectly secure encryption methods .