Atlantic City Algorithmus

Atlantic City Algorithmus ist ein probabilistisch Polynomzeit Algorithmus Das beantwortet mindestens 75% der Zeit korrekt (oder in einigen Versionen ein anderer Wert von mehr als 50%).Der Begriff "Atlantic City" wurde 1982 von J. Finn in einem unveröffentlichten Manuskript mit dem Titel " Vergleich von probabilistischen Tests für die Primalität.[1]

Zwei weitere gemeinsame Klassen von probabilistischen Algorithmen sind Monte Carlo -Algorithmen und Las Vegas -Algorithmen.Monte Carlo -Algorithmen sind immer schnell, aber wahrscheinlich nur richtig.Andererseits sind Las Vegas -Algorithmen immer korrekt, aber wahrscheinlich nur schnell.Die Atlantic City -Algorithmen, die probabilistische Polynomzeitalgorithmen begrenzt sind, sind wahrscheinlich korrekt und wahrscheinlich schnell.[2]

Siehe auch

Verweise

  1. ^ Richard A. Mollin (2003). RSA und öffentliche Schlüsselkryptographie.Chapman & Hall/CRC.p.80.
  2. ^ William J. Turner (Mai 2002). Black Box Lineare Algebra mit der Linbox -Bibliothek.North Carolina State University.p.3. Abgerufen 10. Juli 2014.