SubjectsSubjects(version: 806)
Course, academic year 2017/2018
   Login via CAS
Proof Complexity and the P vs. NP Problem - NMAG536
Czech title: Důkazová složitost a P vs. NP problém
Guaranteed by: Department of Algebra (32-KA)
Faculty: Faculty of Mathematics and Physics
Actual: from 2017
Semester: summer
E-Credits: 3
Hours per week, examination: summer s.:2/0 Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: taught
Language: English
Teaching methods: full-time
Additional information: http://www1.karlin.mff.cuni.cz/~krajicek/ds11.html
Guarantor: prof. RNDr. Jan Krajíček, DrSc.
Class: M Mgr. MSTR
M Mgr. MSTR > Povinně volitelné
Classification: Mathematics > Algebra
Incompatibility : NALG139
Interchangeability : NALG139
Annotation -
Last update: T_KA (14.05.2013)

The course is concerned with the so called Cook's program which reduces the P vs. NP problem to the task to prove lengths-of-proofs lower bounds for propositional proofs. Even partial advances in the program have various concequences (e.g. for automated theorem proving or in mathematical logic).
Literature -
Last update: T_KA (14.05.2013)

J. Krajíček: "Bounded arithmetic, propositional logic, and complexity theory", Encyclopedia of Mathematics and Its Applications, Vol.60, Cambridge University Press, (1995).

P. Pudlák: The lengths of proofs, in Handbook of Proof Theory, S.R. Buss ed., Elsevier, 1998, pp.547-637.

Syllabus -
Last update: T_KA (14.05.2013)

The course is concerned with the so called Cook's program which reduces the P vs. NP problem to the

task to prove lengths-of-proofs lower bounds for propositional proofs. Even partial advances in the program

have various concequences (e.g. for automated theorem proving or in mathematical logic).

 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html