ในทฤษฎีความซับซ้อนของการคำนวณเวลาพหุนามสุ่ม ( RP ) คือกลุ่มความซับซ้อนของปัญหาการตัดสินใจที่ มี เครื่องจักรทัวริงเชิงความน่าจะเป็นที่มีคุณสมบัติดังต่อไปนี้:

• การทำงานจะใช้เวลาแบบพหุนามเสมอเมื่อพิจารณาจากขนาดของข้อมูลป้อนเข้า
• ถ้าคำตอบที่ถูกต้องคือ NO ระบบจะแสดงผลลัพธ์เป็น NO เสมอ
• ถ้าคำตอบที่ถูกต้องคือ ใช่ ระบบจะส่งคืนค่า ใช่ ด้วยความน่าจะเป็นอย่างน้อย 1/2 (มิเช่นนั้น ระบบจะส่งคืนค่า ไม่)

กล่าวอีกนัยหนึ่งคืออัลกอริทึมสามารถสุ่มเลือกผลลัพธ์ได้อย่างแท้จริงในระหว่างการทำงาน กรณีเดียวที่อัลกอริทึมจะส่งคืนค่า YES ได้ก็ต่อเมื่อคำตอบที่แท้จริงคือ YES เท่านั้น ดังนั้น หากอัลกอริทึมสิ้นสุดการทำงานและส่งคืนค่า YES แสดงว่าคำตอบที่ถูกต้องคือ YES อย่างแน่นอน อย่างไรก็ตาม อัลกอริทึมอาจสิ้นสุดการทำงานด้วยค่า NO โดยไม่คำนึงถึงคำตอบที่แท้จริง นั่นคือ หากอัลกอริทึมส่งคืนค่า NO แสดงว่าอาจผิดพลาด

นักเขียนบางคนเรียกกลุ่มนี้ว่าRแม้ว่าชื่อนี้มักใช้กับกลุ่มของภาษาแบบเรียกซ้ำ มากกว่า ก็ตาม

ถ้าคำตอบที่ถูกต้องคือ YES และอัลกอริทึมทำงานnครั้ง โดยผลลัพธ์ของการทำงานแต่ละครั้งเป็นอิสระทางสถิติจากกัน อัลกอริทึมจะคืนค่า YES อย่างน้อยหนึ่งครั้งด้วยความน่าจะเป็นอย่างน้อย1 − 2 ^{− n}ดังนั้น ถ้าอัลกอริทึมทำงาน 100 ครั้ง โอกาสที่จะได้คำตอบที่ผิดทุกครั้งจะน้อยกว่าโอกาสที่รังสีคอสมิกจะทำให้หน่วยความจำของคอมพิวเตอร์ที่รันอัลกอริทึมเสียหาย^{[ 1 ]}ในแง่นี้ ถ้ามีแหล่งที่มาของตัวเลขสุ่ม อัลกอริทึมส่วนใหญ่ในRPจะใช้งานได้จริงมาก

เศษส่วน 1/2 ในคำนิยามนั้นเป็นค่าที่กำหนดขึ้นเอง เซตRPจะประกอบด้วยปัญหาชุดเดิมทุกประการ แม้ว่าจะแทนที่ 1/2 ด้วยค่าคงที่ใดๆ ที่ไม่ใช่ศูนย์และมีความน่าจะเป็นน้อยกว่า 1 ก็ตาม โดยที่ค่าคงที่ในที่นี้หมายถึงค่าที่ไม่ขึ้นอยู่กับข้อมูลป้อนเข้าของอัลกอริทึม

ภาษาLอยู่ในRPก็ต่อเมื่อมีเครื่องจักรทัวริงเชิงความน่าจะเป็นMอยู่จริง โดยที่

• Mใช้เวลาในการประมวลผลแบบพหุนามสำหรับข้อมูลป้อนเข้าทั้งหมด
• สำหรับทุกค่า xในL M จะส่งคืนค่า 1 ด้วยความน่าจะ เป็นมากกว่าหรือเท่ากับ 1/2
• สำหรับค่าx ทั้งหมด ที่ไม่ได้อยู่ในL M จะ ส่งคืนค่า 0

อีกทางเลือกหนึ่งRPสามารถกำหนดได้โดยใช้เพียงเครื่องจักรทัวริงแบบกำหนดได้เท่านั้น ภาษาLอยู่ในRPก็ต่อเมื่อมีพหุนามpและเครื่องจักรทัวริงแบบกำหนดได้Mอยู่จริง โดยที่

• Mทำงานโดยใช้เวลาพหุนามpกับข้อมูลป้อนเข้าทั้งหมด
• สำหรับทุกxในLเศษส่วนของสตริงyที่มีความยาวp (| x |) ที่สอดคล้องกับ⁠ ⁠${\displaystyle M(x,y)=1}$มีค่ามากกว่าหรือเท่ากับ 1/2
• สำหรับx ทั้งหมด ที่ไม่ได้อยู่ในLและสตริงy ทั้งหมด ที่มีความยาวp (| x |), ⁠ ⁠${\displaystyle M(x,y)=0}$

ในคำจำกัดความนี้ สตริงyสอดคล้องกับผลลัพธ์ของการโยนเหรียญแบบสุ่มที่เครื่องจักรทัวริงเชิงความน่าจะเป็นจะทำได้ สำหรับบางแอปพลิเคชัน คำจำกัดความนี้เหมาะสมกว่า เนื่องจากไม่ได้กล่าวถึงเครื่องจักรทัวริงเชิงความน่าจะเป็น

นิยามของRPกล่าวว่า คำตอบ "ใช่" นั้นถูกต้องเสมอ และคำตอบ "ไม่ใช่" อาจผิดได้ เนื่องจากกรณีที่ตอบว่า "ใช่" อาจให้คำตอบว่า "ไม่ใช่" ได้ ส่วนคลาสความซับซ้อนco-RPนั้นเป็นส่วนเติมเต็ม ซึ่งคำตอบ "ใช่" อาจผิดได้ ในขณะที่คำตอบ "ไม่ใช่" นั้นถูกต้องเสมอ

คลาสBPPอธิบายถึงอัลกอริธึมที่สามารถให้คำตอบที่ไม่ถูกต้องได้ทั้งในกรณี YES และ NO ดังนั้นจึงประกอบด้วยทั้งRPและco-RPส่วนจุดตัดของเซตRPและco-RPเรียกว่าZPPเช่นเดียวกับที่RPอาจถูกเรียกว่าRผู้เขียนบางคนใช้ชื่อco-Rแทนco- RP

ปัญหาที่ยังแก้ไม่ตกในวิทยาการคอมพิวเตอร์

⁠ ⁠${\displaystyle {\mathsf {P}}{\overset {?}{=}}{\mathsf {RP}}}$

ยังมีปัญหาที่ยังแก้ไม่ตกอีกมากมายในสาขาวิทยาการคอมพิวเตอร์

Pเป็นเซตย่อยของ RPซึ่งเป็นเซตย่อยของ NPในทำนองเดียวกัน Pเป็นเซตย่อยของ co-RPซึ่งเป็นเซตย่อยของ co-NPยังไม่เป็นที่ทราบแน่ชัดว่าการรวมเหล่านี้เป็นการรวมแบบเข้มงวดหรือไม่ อย่างไรก็ตาม หากสมมติฐานที่เชื่อกันโดยทั่วไปว่า P = BPPเป็นจริง RP , co-RPและ Pจะยุบตัวลง (เท่ากันทั้งหมด) สมมติเพิ่มเติมว่า P ≠ NPนั่นหมายความว่า RPถูกบรรจุอยู่ใน NP อย่างเข้มงวด ยังไม่เป็นที่ทราบแน่ชัดว่า RP = co-RPหรือไม่ หรือว่า RPเป็นเซตย่อยของส่วนร่วมของ NPและ co-NPหรือไม่ แม้ว่าสิ่งนี้จะถูกบ่งชี้โดย P = BPPก็ตาม

ตัวอย่างที่เป็นธรรมชาติของปัญหาในco-RPที่ปัจจุบันยังไม่ทราบว่ามีอยู่ในPคือการทดสอบเอกลักษณ์ของพหุนามซึ่งเป็นปัญหาในการตัดสินใจว่านิพจน์เลขคณิตหลายตัวแปรที่กำหนดเหนือจำนวนเต็มนั้นเป็นพหุนามศูนย์หรือไม่ ตัวอย่างเช่นx · x − y · y − ( x + y )·( x − y )เป็นพหุนามศูนย์ ในขณะที่ x · x + y · yไม่ใช่

การกำหนดลักษณะเฉพาะของRP ในอีกรูปแบบหนึ่ง ที่บางครั้งใช้งานง่ายกว่าคือ ชุดของปัญหาที่เครื่องจักรทัวริงแบบไม่กำหนด สามารถจดจำได้ โดยที่เครื่องจักรจะยอมรับก็ต่อเมื่อมีเส้นทางการคำนวณอย่างน้อยบางส่วนที่เป็นสัดส่วนคงที่ ซึ่งไม่ขึ้นอยู่กับขนาดของอินพุต ยอมรับได้ ในทางกลับกัน NP ต้องการเพียงเส้นทางการยอมรับเพียงเส้นเดียว ซึ่งอาจคิดเป็นสัดส่วนที่น้อยมากในเชิงเลขชี้กำลังของเส้นทางทั้งหมด การกำหนดลักษณะเฉพาะนี้ทำให้เห็น ได้อย่างชัดเจน ว่าRPเป็นเซตย่อยของNP

• อัลกอริทึมแบบสุ่ม

• RP ที่สวนสัตว์แห่งความซับซ้อน