Home >  Term: randomisert Polynomisk tid (RP)
randomisert Polynomisk tid (RP)

Klassen språk som medlemskap kan bli bestemt i Polynomisk tid av en sannsynlig Turing machine med ingen falske godkjente og halvparten falske avviste. Formell definisjon: For et språk, S, finnes det en sannsynlig Turing machine, M, som godkjenner eller avviser alle strenger i Polynomisk tid. Hvis w ∉ S, M, avviser w. Hvis w ∈ S, M godtar w med en sannsynlighet minst 1/2.

0 0

ผู้สร้าง

  • Irene Baglien
  • (Norway)

  •  (V.I.P) 31473 points
  • 100% positive feedback
© 2024 CSOFT International, Ltd.