ผลต่างระหว่างรุ่นของ "ขั้นตอนวิธีแบบสุ่ม"

[[ทฤษฎีความซับซ้อนในการคำนวณ]]ซึ่งเป็นการศึกษาเกี่ยวกับทรัพยากรทางการคำนวณที่ต้องใช้ในการแก้ปัญหาหนึ่งๆ ได้สร้างแบบจำลองของอัลกอริทึมแบบสุ่มให้เป็น''[[เครื่องจักรทัวริง]][[เครื่องจักรทัวริงเชิงความน่าจะเป็น|เชิงความน่าจะเป็น]]'' ทั้งอัลกอริทึมลาสเวกัสและมอนติคาร์โลได้ถูกนำมาพิจารณา รวมถึง "คลาสของความซับซ้อน" หลายๆคลาสก็ได้ถูกนำมาศึกษา คลาสของความซับซ้อนแบบสุ่มแบบที่เป็นพื้นฐานที่สุดคือแบบ[[อาร์พี]] ซึ่งเป็นคลาสของ[[ปัญหาการตัดสินใจ]]ที่มีอัลกอริทึมแบบสุ่ม(หรือเครื่องจักรทัวริงเชิงความน่าจะเป็น)ที่มีประสิทธิภาพ(ทำงานได้ได้ในเวลาโพลิโนเมียล) ที่สามารถตอบว่า"ไม่"ได้ถูกต้องเสมอ และสามารถตอบว่า"ใช่"ได้ โดยมีโอกาสถูกต้องอย่างน้อย 1/2 คลาสส่วนกลับ(complement)ได้แก่โค-อาร์พี และคลาสของปัญหาซึ่งทั้งคำตอบ"ใช่"และ"ไม่" สามารถมีค่าความน่าจะเป็นได้ทั้งคู่ (นั่นคือ ไม่ได้บังคับให้ต้องตอบถูกต้องเสมอ) เรียกว่า[[ซีพีพี]](ZPP) สำหรับปัญหาซึ่ง(เชื่อกันว่า)อยู่นอกคลาสนี้ เช่นปัญหา[[เอ็นพีแบบยาก]] (ซึ่งแม้แต่อัลกอริทึมแบบสุ่มก็ไม่สามารถแก้ได้) จำเป็นต้องแก้ด้วย[[อัลกอริทึมแบบประมาณ]]

 

 

* ถ้ามีตัวยืนยันการเป็นจำนวนประกอบของ ''n'' แล้ว ''n'' เป็นจำนวนประกอบ (หมายความว่า ''n'' ไม่เป็น[[จำนวนเฉพาะ]]) และ

* ถ้า ''n'' เป็นจำนวนประกอบแล้ว มีอย่างน้อยสามในสี่ของจำนวนนับที่มีค่าน้อยกว่า ''n'' ที่เป็นตัวยืนยันการเป็นจำนวนประกอบของ ''n'' ได้ และ