Przejdź do zawartości

Problem liczbowy

Z Wikipedii, wolnej encyklopedii

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

[edytuj | edytuj kod]

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

[edytuj | edytuj kod]

Następujące problemy są problemami liczbowymi:

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

Zobacz też

[edytuj | edytuj kod]