Problem liczbowy
Z Wikipedii
Problem liczbowy to taki problem decyzyjny, w którym wielkość liczb występujących w opisie każdej jego instancji nie jest ograniczona wielomianowo przez rozmiar problemu.
[edytuj] Definicja formalna
Problem π jest problemem liczbowym jeśli dla każdego wielomianu P istnieje taka instancja I problemu π, że
- max(I) > P(n(I))
gdzie max(I) to największa liczba występująca w opisie instancji I a n(I) to rozmiar instancji I.
[edytuj] Przykłady
Następujące problemy są problemami liczbowymi:
- Problem plecakowy,
- Problem komiwojażera,
- Problem podziału zbioru na trójelementowe podzbiory.
Następujące problemy natomiast nie są problemami liczbowymi:
- Problem spełnialności formuł,
- Problem maksymalnego skojarzenia,
- Problem kolorowania grafu.
