Switch to English
Cursus: CK3W3071
Logische complexiteit
Cursus informatie
Studiepunten (EC)7,5
Begrip van grondslagen computatietheorie en complexiteit. Toepassingen in de cryptografie.

Part1. Basic formal language theory Finite automata, regular languages, context-free languages.

Part 2. Basic computation theory  Turing machines, computable functions Church-Turing thesis, Entscheidungsproblem Universal Turing machine Undecidability of the halting problem Decidable and undecidable logical theories, Goedel Theorem

Part 3. Basic complexity theory Time and space complexity measures. Classes P and PSPACE. Class NP, nondeterministic Turing machines. Satisfyiability problem. Clique and Hamiltonian path problems. Polynomial reducibility. NP-completeness. Cook's Theorem. PSPACE-completeness.

Part 4. Elements of cryptography Calculating modulo n. Ring Z_n. Inverible elements. Euclid algorithm. Euler function. Euler theorem and Fermat's little theorem. Pseudoprimes. Probabilistic polynomial algrothms for testing pseudoprimality and primality. Cryptosystems, one time pad cryptosystem, information-theoretic security Public key cryptosystems RSA cryptosystem Electronic signatures in RSA.

Switch to English