Introduktion till komplexitet, omvänd föreläsning

Förberedelser inför föreläsningen

Titta på denna video:

Läs denna Download motivering

till varför det är bra att kunna komplexitet.

Läs i KT sida 463-466 (hela sidan).

Uppgifter som görs under föreläsningen

1

Visa att problemet Kappsäck ligger i NP.

2

Det går att reducera Hamiltonsk krets till TSP på polynomisk tid.
Hamiltonsk krets är NP-fullständigt.
Förklara varför TSP då också måste vara NP-fullständigt.

3

Vi vet att Pussel är NP-fullständigt.
Vi vet inte om P = NP.
1. Anta att vi hittar en algoritm med värstafallstidskomplexitet O(n^8) för
Pussel. Vad kan vi då säga om P och NP?
2. Anta att vi kan bevisa att värstafallstidskomplexitet för Pussel är
Ω(1.2^n). Vad kan vi då säga om P och NP?