List of theorems of computer science

Contents A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

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. ${\displaystyle F}$ ${\displaystyle F}$ ${\displaystyle E(F)}$
• 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 . ${\displaystyle \operatorname {DTIME} {\big (}f(n){\big )}\subsetneq \operatorname {DTIME} {\big (}f(n)\cdot \log ^{2}(f(n)){\big )}}$ ${\displaystyle \operatorname {DSPACE} {\big (}f(n){\big )}\subsetneq \operatorname {DSPACE} {\big (}f(n)\cdot \log(f(n)){\big )}}$

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. ${\displaystyle \mathbf {P} \neq \mathbf {NP} }$

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 .) ${\displaystyle L}$ ${\displaystyle L}$

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. ${\displaystyle f_{max}}$ ${\displaystyle 2\cdot f_{max}}$

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 .

See also

• List of important people in IT