Algorytm Atlantic City

Algorytm Atlantic City to probabilistyczny algorytm czasu wielomianowego , który odpowiada poprawnie przez co najmniej 75% czasu (lub, w niektórych wersjach, inną wartość większą niż 50%). Termin „Atlantic City” został po raz pierwszy wprowadzony w 1982 roku przez J. Finna w niepublikowanym rękopisie zatytułowanym Porównanie probabilistycznych testów dla pierwszości .

Dwie inne popularne klasy algorytmów probabilistycznych to algorytmy Monte Carlo i algorytmy Las Vegas . Algorytmy Monte Carlo są zawsze szybkie, ale tylko prawdopodobnie poprawne. Z drugiej strony algorytmy Las Vegas są zawsze poprawne, ale tylko prawdopodobnie szybkie. Algorytmy Atlantic City, które są ograniczonymi probabilistycznymi algorytmami czasu wielomianowego, są prawdopodobnie poprawne i prawdopodobnie szybkie.

Zobacz też


Pobrano z „ https://en.wikipedia.org/w/index.php?title=Atlantic_City_algorithm&oldid=1093087166 ”