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 ${\displaystyle \pi }$ jest problemem liczbowym, jeśli dla każdego wielomianu ${\displaystyle P}$ istnieje taka instancja ${\displaystyle I}$ problemu ${\displaystyle \pi ,}$ że

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

gdzie ${\displaystyle \max(I)}$ to największa liczba występująca w opisie instancji ${\displaystyle I,}$ a ${\displaystyle 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