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 jest problemem liczbowym, jeśli dla każdego wielomianu istnieje taka instancja problemu że
gdzie to największa liczba występująca w opisie instancji a 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
Kategoria:Teoria obliczeń