Problem liczbowy

Problem liczbowy

Problem liczbowy to rodzaj problemu decyzyjnego, w którym wartości liczbowe w opisie każdej instancji nie są ograniczone wielomianowo przez rozmiar problemu. Może on mieć charakter optymalizacyjny, ale nie jest to warunek konieczny.

Definicja formalna

Problem $pi$ jest uznawany za problem liczbowy, jeśli dla każdego wielomianu $P$ istnieje taka instancja $I$, w której spełniony jest warunek:

$max(I)\; >\; P(n(I)),$

gdzie $max(I)$ oznacza największą wartość w opisie instancji $I$, a $n(I)$ to rozmiar tej instancji.

Przykłady problemów liczbowych

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

Przykłady problemów, które nie są liczbowymi

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