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.

Problem π {\displaystyle \pi } jest problemem liczbowym, jeśli dla każdego wielomianu P {\displaystyle P} istnieje taka instancja I {\displaystyle I} problemu π , {\displaystyle \pi ,} że

max ( I ) > P ( n ( I ) ) , {\displaystyle \max(I)>P(n(I)),}

gdzie max ( I ) {\displaystyle \max(I)} to największa liczba występująca w opisie instancji I , {\displaystyle I,} a n ( I ) {\displaystyle n(I)} to rozmiar tej instancji.

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

• algorytm pseudowielomianowy
• problem silnie NP-zupełny