8
Czy jest jakiś inny algorytm, którego najgorszy czas działania jest wykładniczy, podczas gdy działa on bardzo dobrze w praktyce, inny niż algorytm Simplex?
Na ogół algorytm nazywamy „dobrym algorytmem”, jeśli jego czas działania jest w najgorszym przypadku wielomianowy. Ale w niektórych przypadkach (na przykład algorytm Simplex), chociaż najgorszy przypadek algorytmu ma charakter wykładniczy, może on działać bardzo dobrze w praktyce. Czy są jakieś (deterministyczne) przykłady tej sytuacji inne niż algorytm Simplex?