Subjects

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

Proof complexity and the P vs. NP problem - NALG139

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 2018
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:	cancelled
Language:	English
Teaching methods:	full-time
Teaching methods:	full-time
Additional information:	http://www.karlin.mff.cuni.cz/~krajicek/ds11.html

Guarantor:	prof. RNDr. Jan Krajíček, DrSc.
Classification:	Mathematics > Algebra
Interchangeability :	NMAG536
Is incompatible with:	NMAG536
Is interchangeable with:	NMAG536

Opinion survey results Examination dates Schedule Noticeboard

Annotation -

Last update: T_KA (03.03.2011)

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 (03.03.2011)

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 (03.03.2011)

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).