10099 strona1 (10)

100

Nazwisko i imię

21.01.2005.

Grupa/rok.

Czas trwania testu: 120 minut

sąsiad lewy

Nazwiska proszę pisać CZYTELNIE literami DRUKOWANYMI

sąsiad prawy

UWAGA: Obok każdego pytania napisz końcowe rozwiązanie. Tok rozumowania prowadzącego do tego rozwiązania załącz

	24 +4,-2

1. Jak wiadomo, problem podziału zbioru liczb naturalnych A={a,, .... a„) jest NP-zupełny. Czy pozostaje on NP-zupełny, czy też staje się wielomianowy przy następujących modyfikacjach:

1.    zbiór A chcemy podzielić na 3 podzbiory o równych sumach elementów

2.    a,<3 dla każdego /'= 1,.... n

3.    n jest podzielne przez 3

4.    wszystkie liczby są podzielne przez 3

5.    a, = i dla każdego i= 1, .... n

6.    a, = 2'dla każdego/= 1,...,/j

Każdą odpowiedź uzasadnij.

2. Udowodnij, że problem DROGA HAMILTONA jest w klasie NP, przyjmując iż graf zapisany jest w postaci macierzy sąsiedztwa A[l..«, 1 ../*].

Wskazówka: Napisz algorytm, weryfikujący rozwiązanie zapisane w wektorze VEC[\ .. «].

3. Udowodnij, że problem komiwojażera nic posiada wielomianowego algorytmu A-absolutnie przybliżonego dla żadnego k > 0 (chyba, że P=NP).