Problem liczbowy

Problem liczbowy – taki problem decyzyjny (to nie jest warunek konieczny – może być optymalizacyjny), w którym wielkość liczb występujących w opisie każdej jego instancji nie jest ograniczona wielomianowo przez rozmiar problemu.

Definicja formalna

Problem $\pi$ jest problemem liczbowym, jeśli dla każdego wielomianu $P$ istnieje taka instancja $I$ problemu $\pi ,$ ż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 tej instancji.

Przykłady

Następujące problemy są problemami liczbowymi:

• problem komiwojażera
• problem plecakowy
• problem podziału zbioru na trójelementowe podzbiory

Następujące problemy natomiast nie są problemami liczbowymi:

• problem kolorowania grafu
• problem maksymalnego skojarzenia
• problem spełnialności

Zobacz też

• algorytm pseudowielomianowy
• problem silnie NP-zupełny