Subjects

Your browser does not support JavaScript, or its support is disabled. Some features may not be available.

Structural Complexity - NTIN081

Title:	Strukturální složitost
Guaranteed by:	Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
Faculty:	Faculty of Mathematics and Physics
Actual:	from 2016 to 2016
Semester:	summer
E-Credits:	3
Hours per week, examination:	summer s.:2/0, Ex [HT]
Capacity:	unlimited
Min. number of students:	unlimited
4EU+:	no
Virtual mobility / capacity:	no
State of the course:	taught
Language:	Czech
Teaching methods:	full-time
Teaching methods:	full-time

Guarantor:	prof. Mgr. Michal Koucký, Ph.D.
Class:	Informatika Mgr. - Teoretická informatika
Classification:	Informatics > Theoretical Computer Science
Co-requisite :	NTIN063
Is co-requisite for:	NTIN082

Opinion survey results Examination dates Schedule Noticeboard

Annotation -

Last update: T_KTI (26.04.2016)

This course extends the basic course on computational complexity (NTIN063). It covers hierarchy theorems for probabilistic computation, time-space trade-offs for SAT, Toda's Theorem, pseudo-random generators and interactive protocols.

Aim of the course - Czech

Last update: T_KTI (26.04.2016)

Naučit další látku z teorie složitosti: vztahy mezi třídami složitosti, pseudonáhodné generátory a interaktivni protokoly.

Literature -

Last update: T_KTI (26.04.2016)

Oded Goldreich, Computational Complexity: A Conceptual Perspective, Cambridge University Press 2008.

Sanjeev Arora, Boaz Barak. Complexity Theory: A Modern Approach. Cambridge University Press 2008.

D. van Melkebeek and K. Pervyshev. A Generic Time Hierarchy for Semantic Models With One Bit of Advice. Computational Complexity, 16: 139-179, 2007.

D. van Melkebeek. Time-Space Lower Bounds for Satisfiability. Bulletin of EATCS, 73: 57-77, 2001.

Syllabus -

Last update: T_KTI (26.04.2016)

Nondeterministic time hierarchy and hierarchy for probabilistic computation

BPP and polynomial hierarchy

Time-space trade-off for SAT

Isolation Lemma and Toda's Theorem

Pseudo-random generators, Nisan's pseudo-random generator

Interactive protocols - Arthur-Merlin games (class AM, IP=PSPACE)

Multi-prover interactive protocols (MIP=NEXP)