Uusi opinto-opas (sisältäen myös opetusohjelmat) lukuvuodelle 2018-2019 sijaitsee osoitteessa https://opas.peppi.utu.fi . Tältä sivustolta löytyvät enää vanhat opinto-oppaat ja opetusohjelmat.

The new study guide (incl. teaching schedules) for academic year 2018-2019 can be found at https://studyguide.utu.fi. This site contains only previous years' guides.

x !
Arkistoitu opetussuunnitelma 2014–2016
Selaamasi opetussuunnitelma ei ole enää voimassa. Tarkista tiedot voimassa olevasta opetussuunnitelmasta.
MATE6009 NP-completeness 5 op
Organised by
Mathematics
Person in charge
Department of Mathematics and Statistics, Juhani Karhumäki
Planned organizing times
Period(s) I II III IV
2014–2015 X

General description

One of the great problems in constructive mathematics, or theoretical computer science is the question whether P=NP. More informally it asks for whether each polynomial time nondeterministic algorithm can be simulated by an ordinary deterministic polynomial time algorithm. It has turned out the problem reduces to a problem of deciding whether for some fixed problem there exists a polynomial time algorithm. Such problems are called NP-complete.

Learning outcomes

To learn and understand NP-completeness proofs/reductions and the role of NP-complete problems in theoretical computer science.

Contents

We formalize this theory and discuss about the basic questions of the field. In particular we show that many natural problems are NP-complete.

Teaching methods

Teaching method Contact Online
Lectures 28 h 0 h
Exercises 12 h 0 h

Teaching language

English

Modes of study

Option 1
Available for:
  • Degree Programme Students
  • Other Students
  • Doctoral Students
  • Exchange Students
Exercises Exercise(s)
  • In English
Written exam
  • In English

Evaluation

Numeric 0-5.

Study materials

Lecture notes.

Literature:

M.R. Garey and D.S. Johnson: Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, San Francisco, 1979.

Sanjeev Arora and Boaz Barak: Computational Complexity: A Modern Approach, Cambridge University Press, New York 2009.

Christos H. Papadimitriou: Computational Complexity, Addison Wesley, 1994.

Belongs to following study modules

Matematiikan ja tilastotieteen laitos
2014–2015
Teaching
Archived Teaching Schedule. Please refer to current Teaching Shedule.
Implementation details are unavailable.
Matematiikan ja tilastotieteen laitos
Opintokokonaisuudet
Tilastotiede