Pytania oznaczone «pseudo-polynomial»

Dlaczego nie przyjąć jednolitej reprezentacji liczb w algorytmach numerycznych?

Pseudo-wielomianowy algorytm czasu jest algorytmem, który ma wielomianowy czas działania na wartości wejściowej (wielkość), ale wykładniczy czas działania na wielkości wejściowej (liczba bitów). Na przykład sprawdzenie, czy liczba jest liczbą pierwszą, czy nie, wymaga przejścia przez liczby od 2...

Czy może to być problem z NP-Complete?

Rozważ następujące stwierdzenie problemu: Biorąc pod uwagę początkową liczbę, ty i twój przyjaciel na zmianę odejmujemy od niej idealny kwadrat. Pierwszy, który osiągnie zero, wygrywa. Na przykład: Stan początkowy: 37 Gracz 1 odejmuje 16. Stan: 21 Gracz 2 odejmuje 8. Stan: 13 Gracz 1...