Lu­ke­mis­teh­tä­vä:
NP-täy­del­li­syys

Tä­män teh­tä­vän ta­voi­te on toi­saal­ta an­taa oi­keaa tie­toa jois­ta­kin NP-täy­del­li­syy­teen liit­ty­vis­tä asiois­ta, jois­ta on liik­keel­lä vää­rin­kä­si­tyk­siä, ja toi­saal­ta an­taa opet­ta­jil­le kä­si­tys­tä opis­ke­li­joi­den val­miuk­sis­ta tul­ki­ta ne­tis­tä ja kir­jal­li­suu­des­ta löy­ty­vää tie­toa. Jot­ta opis­ke­li­jat us­kal­tai­si­vat yrit­tää vaik­ka oli­si­vat epä­var­mo­ja, vas­tauk­set pyy­de­tään ano­nyy­mei­na etä­vas­tauk­sia lu­kuun­ot­ta­mat­ta. Etä­vas­tauk­sien ta­pauk­ses­sa ano­nyy­miy­den jär­jes­tä­mi­nen oli­si ko­vin han­ka­laa suh­tees­sa odo­tet­ta­vis­sa ole­vaan hyö­tyyn.

Vas­taa jo­kai­seen seu­raa­vis­ta ky­sy­myk­sis­tä ja myös pe­rus­te­le vas­tauk­se­si. Läh­tei­nä saat käyt­tää mi­tä ta­han­sa kir­jal­li­sia läh­tei­tä, ku­ten kurs­sin vep­pi­si­vul­la mai­nit­tu­ja il­mais­kir­jo­ja, mui­ta kir­jo­ja ja Wi­ki­pe­diaa. Mai­nit­se käyt­tä­mä­si läh­teet asian­mu­kai­ses­ti, eli käy­tä opin­näy­te­töi­den tai tie­teel­li­sen kir­jal­li­suu­den viit­taus­ta­paa.

Vas­tauk­set pe­rus­te­lui­neen ja läh­de­viit­tei­neen saa­vat ol­la yh­teen­sä kor­kein­taan 2 A-ne­los­ta pit­kät. Voit kir­joit­taa (tie­to)­ko­neel­la tai sel­väl­lä kä­si­alal­la. Älä käy­tä hy­vin pien­tä font­tia älä­kä hy­vin le­vei­tä ri­ve­jä. Älä lai­ta ni­meä­si vas­tauk­siin.

Jos tu­let de­moon, pa­lau­ta vas­tauk­se­si pa­pe­ril­la ja mer­kit­se teh­tä­vä de­mo­lis­taan teh­dyk­si. Jos et tu­le de­moon, mei­laa vas­tauk­se­si Jo­han­na Ran­ta­lal­le nor­maa­lis­sa etä­pa­lau­tuk­sen ai­ka­tau­lus­sa.

1. 0-1-sel­kä­rep­pu­teh­tä­väs­sä (0-1-knap­sack) on n ta­va­raa, jois­ta kul­la­kin on pai­no (weight) w_i ja ar­vo (value) v_i, ja rep­puun on pa­kat­ta­va ta­va­roi­ta si­ten, et­tä nii­den yh­teis­pai­no on enin­tään W ja yh­teis­ar­vo on mah­dol­li­sim­man suu­ri. Teh­tä­väs­sä ky­sy­tään, kuin­ka suu­rek­si yh­teis­ar­vo voi­daan saa­da. Teh­tä­vä osa­taan rat­kais­ta ajas­sa O(nW), jo­ka on n:n ja W:n po­ly­no­mi. Sil­ti kir­jal­li­suu­des­sa väi­te­tään, et­tä 0-1-sel­kä­rep­pu­teh­tä­vä on NP-ko­va (NP-hard). Mik­si tä­mä vai­kut­taa ris­ti­rii­tai­sel­ta ja mi­kä on ris­ti­rii­dan rat­kai­su?
2. Mik­si kir­jal­li­suu­des­sa ei sa­no­ta, et­tä 0-1-sel­kä­rep­pu­teh­tä­vä on NP-täy­del­li­nen (NP-complete)? Mi­kä hy­vin sa­man­kal­tai­nen teh­tä­vä on NP-täy­del­li­nen? Mik­si tä­män teh­tä­vän NP-täy­del­li­syys on kiin­nos­ta­va myös 0-1-sel­kä­rep­pu­teh­tä­vän kan­nal­ta?
3. An­na esi­merk­ki kyl­lä/ei-teh­tä­väs­tä, jo­ka ei ole NP:ssä.
4. Jos P = NP, niin mit­kä NP:hen kuu­lu­vat kie­let ovat NP-täy­del­li­siä? Tä­mä on yk­sin­ker­tai­nen seu­raus mää­ri­tel­mis­tä. Kun et­sit tä­hän vas­taus­ta, kan­nat­taa kes­kit­tyä sii­hen, mi­ten aja­tus teh­tä­vän rat­kai­se­mi­ses­ta toi­sen teh­tä­vän avul­la on käy­tös­sä NP-täy­del­li­syy­den mää­ri­tel­mäs­sä.