ในทฤษฎีความซับซ้อนของการคำนวณซึ่งเป็นสาขาหนึ่งของวิทยาศาสตร์คอมพิวเตอร์ ปัญหาการตัดสินใจ แบบเวลาพหุนามเชิงความน่าจะเป็นที่มีขอบเขตความคลาดเคลื่อน ( BPP ) คือกลุ่มของปัญหาการตัดสินใจที่สามารถแก้ไขได้โดยเครื่องจักรทัวริงเชิงความน่า จะเป็น ในเวลาพหุนามโดยมีความน่าจะเป็น ของข้อผิดพลาด ที่จำกัดโดย 1/3 สำหรับทุกกรณี BPPเป็นหนึ่งในกลุ่มปัญหาเชิงปฏิบัติ ที่ใหญ่ที่สุด หมายความว่าปัญหาที่น่าสนใจส่วนใหญ่ใน BPPมีอัลกอริทึมเชิงความน่าจะ เป็นที่มีประสิทธิภาพ ซึ่งสามารถทำงานได้อย่างรวดเร็วบนเครื่องจักรสมัยใหม่จริง BPPยังรวมถึงPซึ่งเป็นกลุ่มของปัญหาที่สามารถแก้ไขได้ในเวลาพหุนามด้วยเครื่องจักรเชิงกำหนด เนื่องจากอัลกอริทึมเชิงกำหนดเป็นกรณีพิเศษของอัลกอริทึมเชิงความน่าจะเป็น

โดยทั่วไป ปัญหาจะอยู่ในกลุ่มปัญหา BPPหากมีอัลกอริทึมสำหรับแก้ปัญหานั้นซึ่งมีคุณสมบัติดังต่อไปนี้:

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

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

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

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

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

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

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

ในทางปฏิบัติ ความน่าจะเป็นของข้อผิดพลาด 1/3 อาจไม่เป็นที่ยอมรับ อย่างไรก็ตาม การเลือก 1/3 ในคำจำกัดความนั้นเป็นไปโดยพลการ การปรับเปลี่ยนคำจำกัดความโดยใช้ค่าคงที่ ใดๆ ระหว่าง 0 ถึง 1/2 (ไม่รวม 0 และ 1/2) แทน 1/3 จะไม่เปลี่ยนแปลงชุดBPP ที่ได้ ตัวอย่างเช่น หากกำหนดคลาสโดยมีข้อจำกัดว่าอัลกอริทึมอาจผิดพลาดได้ด้วยความน่าจะเป็นสูงสุด 1/2 ¹⁰⁰ผลลัพธ์ที่ได้จะเป็นคลาสของปัญหาเดียวกัน ความน่าจะเป็นของข้อผิดพลาดไม่จำเป็นต้องเป็นค่าคงที่ด้วยซ้ำ คลาสของปัญหาเดียวกันสามารถกำหนดได้โดยการอนุญาตให้มีข้อผิดพลาดสูงถึง 1/2 − n ^{− c}ในด้านหนึ่ง หรือกำหนดให้มีข้อผิดพลาดน้อยที่สุดถึง 2 ^{− ncในอีก}ด้านหนึ่ง โดยที่cเป็นค่าคงที่บวกใดๆ และnคือความยาวของข้อมูลป้อนเข้า ความยืดหยุ่นในการเลือกความน่าจะเป็นของข้อผิดพลาดนี้ขึ้นอยู่กับแนวคิดของการเรียกใช้อัลกอริทึมที่มีแนวโน้มผิดพลาดหลายครั้ง และใช้ผลลัพธ์ส่วนใหญ่ของการเรียกใช้เพื่อให้ได้อัลกอริทึมที่แม่นยำยิ่งขึ้น โอกาสที่การรันส่วนใหญ่จะผิดพลาดจะลดลงแบบทวีคูณอันเป็นผลมาจากขอบเขตของเชอร์นอฟ^{[ 1 ]}

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

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

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

ปัญหาทั้งหมดในPเห็นได้ชัดว่าอยู่ในBPP ด้วยเช่นกัน อย่างไรก็ตาม มีปัญหาหลายอย่างที่ทราบว่าอยู่ในBPPแต่ไม่ทราบว่าอยู่ในPจำนวนปัญหาดังกล่าวลดลงเรื่อยๆ และมีการคาดการณ์ว่า P = BPP

เป็นเวลานานแล้วที่ปัญหาที่มีชื่อเสียงที่สุดปัญหาหนึ่งซึ่งทราบกันว่าอยู่ในBPPแต่ไม่ทราบว่าอยู่ในPคือปัญหาการตรวจสอบว่าจำนวนที่กำหนดให้เป็นจำนวนเฉพาะ หรือ ไม่ อย่างไรก็ตาม ในบทความปี 2002 เรื่องPRIMES is in Pนั้นManindra AgrawalและนักศึกษาของเขาNeeraj KayalและNitin Saxenaได้ค้นพบอัลกอริทึมเชิงกำหนดแบบใช้เวลาพหุนามสำหรับปัญหานี้ ซึ่งแสดงให้เห็นว่าปัญหานี้อยู่ใน P

ตัวอย่างที่สำคัญของปัญหาในBPP (ที่จริงในco-RP ) ที่ยังไม่เป็นที่รู้จักในPคือการทดสอบเอกลักษณ์ของพหุนามซึ่งเป็นปัญหาในการพิจารณาว่าพหุนามเท่ากับพหุนามศูนย์โดยสมบูรณ์หรือไม่ เมื่อคุณสามารถเข้าถึงค่าของพหุนามสำหรับอินพุตที่กำหนดใดๆ ได้ แต่ไม่สามารถเข้าถึงสัมประสิทธิ์ได้ กล่าวอีกนัยหนึ่งคือ มีการกำหนดค่าให้กับตัวแปรหรือไม่ เช่นนั้นเมื่อประเมินพหุนามที่ไม่ใช่ศูนย์บนค่าเหล่านี้ ผลลัพธ์จะไม่เป็นศูนย์ เพียงพอที่จะเลือกค่าของตัวแปรแต่ละตัวแบบสุ่มอย่างสม่ำเสมอจากเซตย่อยจำกัดอย่างน้อยdค่า เพื่อให้ได้ความน่าจะเป็นของข้อผิดพลาดที่จำกัด โดยที่dคือดีกรีทั้งหมดของพหุนาม^{[ 2 ]}

หาก เรา ลบเงื่อนไขการเข้าถึงความสุ่มออกจากนิยามของBPPเราจะได้คลาสความซับซ้อนP และหากเราแทนที่ เครื่องจักรทัวริง ธรรมดา ด้วยคอมพิวเตอร์ควอนตัมในนิยามของคลาสนี้เราจะได้คลาสBQP

การเพิ่มโพสต์การเลือกไปยังBPPหรือการอนุญาตให้เส้นทางการคำนวณมีความยาวต่างกัน จะทำให้ได้คลาสBPP path _[ ^{3 ] BPP} path _เป็นที่ทราบกันว่ามีNP อยู่ และมีอยู่ในPostBQP ซึ่งเป็นคู่ควอนตั ม ของมัน

อัลกอริทึม Monte Carloเป็นอัลกอริทึมแบบสุ่มที่มีโอกาสถูกต้องสูง ปัญหาในกลุ่มBPPมีอัลกอริทึม Monte Carlo ที่มีเวลาการทำงานจำกัดแบบพหุนาม ซึ่งแตกต่างจากอัลกอริทึม Las Vegasที่เป็นอัลกอริทึมแบบสุ่มซึ่งอาจให้คำตอบที่ถูกต้องหรือผิดพลาดได้ด้วยความน่าจะเป็นต่ำ อัลกอริทึม Las Vegas ที่มีเวลาการทำงานจำกัดแบบพหุนามถูกนำมาใช้กำหนดกลุ่มZPPหรืออีกทางหนึ่งZPPประกอบด้วยอัลกอริทึมเชิงความน่าจะเป็นที่ถูกต้องเสมอและมีเวลาการทำงานโดยเฉลี่ยแบบพหุนาม ซึ่งอ่อนกว่าการบอกว่าเป็นอัลกอริทึมเวลาพหุนาม เนื่องจากอาจใช้เวลานานกว่าพหุนาม แต่มีความน่าจะเป็นต่ำมาก

เป็นที่ทราบกันว่าBPPปิดภายใต้คอมพลีเมนต์นั่นคือBPP = co-BPP BPP มีประสิทธิภาพต่ำสำหรับตัวมันเอง หมายความว่า เครื่อง BPPที่มีกำลังในการแก้ ปัญหา BPPได้ทันที ( เครื่อง BPP ออราเคิล ) จะไม่มีประสิทธิภาพมากกว่าเครื่องที่ไม่มีกำลังพิเศษนี้ ในเชิงสัญลักษณ์ BPP = ^BPP

ความสัมพันธ์ระหว่างBPPและNPยังไม่เป็นที่ทราบแน่ชัด: ไม่ทราบว่าBPPเป็นเซตย่อยของNPหรือNPเป็นเซตย่อยของBPPหรือไม่ หากNPอยู่ในBPPซึ่งถือว่าไม่น่าเป็นไปได้ เนื่องจากจะหมายถึงวิธีแก้ปัญหาที่ใช้งานได้จริงสำหรับ^{ปัญหา} NP-completeดังนั้นNP = RPและPH ⊆ BPP [ ^{4 ]}

เป็นที่ทราบกันว่าRPเป็นเซตย่อยของBPPและBPPเป็นเซตย่อยของPPแต่ไม่ทราบว่าทั้งสองเป็นเซตย่อยแบบเข้มงวดหรือไม่ เนื่องจากเราไม่ทราบด้วยซ้ำว่าPเป็นเซตย่อยแบบเข้มงวดของPSPACE หรือ ไม่BPPอยู่ในระดับที่สองของลำดับชั้นพหุนามดังนั้นจึงอยู่ในPH กล่าว โดยละเอียดทฤษฎีบท Sipser–Lautemannระบุว่าดังนั้นP = NPจึงนำไปสู่​​P = BPPเนื่องจากPHยุบตัวลงเป็นPในกรณีนี้ ดังนั้นP = BPPหรือP ≠ NPหรือทั้งสองอย่าง ${\displaystyle {\mathsf {BPP}}\subseteq \Sigma _{2}\cap \Pi _{2}}$

ทฤษฎีบทของ Adlemanระบุว่าการเป็นสมาชิกในภาษาใดๆ ในBPPสามารถกำหนดได้โดยตระกูลของวงจรบูลีน ขนาดพหุนาม ซึ่งหมายความว่าBPPบรรจุอยู่ในP/poly [ ^{5 ] อัน}ที่จริง ผลที่ตามมาจากการพิสูจน์ข้อเท็จจริงนี้ อัลกอริทึม BPP ทุกตัว ที่ทำงานกับอินพุตที่มีความยาวจำกัดสามารถลดความสุ่มลงเป็นอัลกอริทึมเชิงกำหนดโดยใช้สตริงคงที่ของบิตสุ่ม อย่างไรก็ตาม การค้นหาสตริงนี้อาจมีค่าใช้จ่ายสูง ผลลัพธ์การแยกที่อ่อนแอสำหรับคลาสเวลา Monte Carlo ได้รับการพิสูจน์โดยKarpinski & Verbeek (1987a)ดูเพิ่มเติมที่Karpinski & Verbeek (1987b )

คลาส BPP มีคุณสมบัติปิดภายใต้การเติมเต็ม การรวม การตัดกัน และการต่อกัน

เมื่อเทียบกับออราเคิล เราทราบว่ามีออราเคิล A และ B อยู่ โดยที่P ^A = BPP ^AและP ^B ≠ BPP ^Bยิ่งไปกว่านั้น เมื่อเทียบกับออราเคิลแบบสุ่มที่มีความน่าจะเป็น 1, P = BPPและBPPจะถูกบรรจุอยู่ในNPและco-NPอย่าง เคร่งครัด ^{[ 6 ]}

ยังมีออราเคิลอีกด้วยซึ่ง⁠ ⁠${\displaystyle {\mathsf {BPP}}={\mathsf {EXP}}^{\mathsf {NP}}}$ (และด้วยเหตุนี้⁠ ⁠${\displaystyle {\mathsf {P<NP<BPP=EXP=NEXP}}}$ ) ^{[ 7 ]}ซึ่งสามารถสร้างซ้ำได้ดังต่อไปนี้ สำหรับ ปัญหา E ^NP (สัมพัทธ์) ที่สมบูรณ์คงที่ ออราเคิลจะให้คำตอบที่ถูกต้องด้วยความน่าจะเป็นสูงหากสอบถามด้วยอินสแตนซ์ของปัญหาตามด้วยสตริงแบบสุ่มที่มีความยาวkn ( nคือความยาวของอินสแตนซ์; kเป็นค่าคงที่ขนาดเล็กที่เหมาะสม) เริ่มต้นด้วยn = 1 สำหรับทุกอินสแตนซ์ของปัญหาที่มีความยาวnให้กำหนดคำตอบของออราเคิล (ดูเลมมาด้านล่าง) เพื่อกำหนดเอาต์พุตของอินสแตนซ์ ต่อไป ให้จัดเตรียมเอาต์พุตของอินสแตนซ์สำหรับการสอบถามที่ประกอบด้วยอินสแตนซ์ตามด้วยสตริง ที่มีความยาว knจากนั้นให้ถือว่าเอาต์พุตสำหรับการสอบถามที่มีความยาว ≤ ( k + 1) nคงที่ และดำเนินการต่อด้วยอินสแตนซ์ที่มีความยาวn + 1

บทพิสูจน์ย่อยนี้รับรองว่า (สำหรับค่าk ที่มากพอ ) สามารถสร้างโครงสร้างได้โดยยังคงเหลือสตริงเพียงพอสำหรับ คำตอบ E ^NP แบบสัมพัทธ์ นอกจากนี้ เรายังสามารถรับรองได้ว่าสำหรับE ^NP แบบสัมพัทธ์ นั้น เวลาเชิงเส้นก็เพียงพอแล้ว แม้แต่สำหรับปัญหาฟังก์ชัน (หากกำหนดออราเคิลฟังก์ชันและขนาดเอาต์พุตเชิงเส้น) และมีความน่าจะเป็นของข้อผิดพลาดที่น้อยมาก (ด้วยเลขชี้กำลังเชิงเส้น) ยิ่งไปกว่านั้น โครงสร้างนี้ยังมีประสิทธิภาพตรงที่เมื่อกำหนดออราเคิล A ใดๆ เราสามารถจัดเรียงออราเคิล B ให้มีP ^A ≤ P ^BและEXP ^{NP A} = EXP ^{NP B} = BPP ^Bได้ นอกจากนี้ สำหรับ ออราเคิล ZPP =EXP (และดังนั้นZPP=BPP=EXP<NEXP ) เราจะกำหนดคำตอบในการคำนวณ E แบบสัมพัทธ์ให้เป็นคำตอบที่ไม่ใช่คำตอบพิเศษ เพื่อให้แน่ใจว่าจะไม่มีคำตอบปลอมเกิดขึ้น

ผู้เชี่ยวชาญส่วนใหญ่ในสาขานี้คาดการณ์ถึงการมีอยู่ของตัวสร้างเลขสุ่มเทียมที่แข็งแกร่งบางตัว ตัวสร้างดังกล่าวสามารถใช้แทนเลขสุ่มจริงในอัลกอริธึมสุ่มใดๆ ก็ได้ในเวลาพหุนาม โดยให้ผลลัพธ์ที่แยกแยะไม่ได้ การคาดการณ์ว่าตัวสร้างเหล่านี้มีอยู่จริงหมายความว่าความสุ่มไม่ได้ให้พลังการคำนวณเพิ่มเติมแก่การคำนวณในเวลาพหุนาม นั่นคือP = RP = BPPยิ่งไปกว่านั้นสมมติฐานที่ว่าP = BPPในบางแง่เทียบเท่ากับการมีอยู่ของตัวสร้างเลขสุ่มเทียมที่แข็งแกร่ง^{[ 8 ]}

László Babai , Lance Fortnow , Noam NisanและAvi Wigdersonแสดงให้เห็นว่าเว้นแต่EXPTIMEจะยุบตัวเป็นMAแล้วBPPจะมีอยู่ใน^{[ 9 ]}

${\displaystyle {\textsf {io-SUBEXP}}=\bigcap \nolimits _{\varepsilon >0}{\textsf {io-DTIME}}\left(2^{n^{\varepsilon }}\right).}$

คลาสio-SUBEXPซึ่งย่อมาจาก infinitely often SUBEXP นั้นประกอบด้วยปัญหาที่มี อัลกอริทึม เวลาต่ำกว่าเลขชี้กำลังสำหรับขนาดอินพุตจำนวนอนันต์ พวกเขายังแสดงให้เห็นว่าP = BPPหากลำดับชั้นเวลาเลขชี้กำลัง ซึ่งกำหนดในแง่ของลำดับชั้นพหุนามและEเป็นE ^PHนั้นยุบตัวลงเป็นEอย่างไรก็ตาม โปรดทราบว่าโดยทั่วไปแล้วลำดับชั้นเวลาเลขชี้กำลังมักถูกคาดเดาว่า จะ ไม่ยุบตัวลง

Russell ImpagliazzoและAvi Wigdersonแสดงให้เห็นว่าหากมีปัญหาใดๆ ในEซึ่ง

${\displaystyle {\mathsf {E}}={\mathsf {DTIME}}\left(2^{O(n)}\right),}$

^หากวงจรมีความซับซ้อน 2 ^{Ω( n )}แล้วP = BPP [ ^{10 ]}

• อาร์พี
• ซีดีพีพี
• บีคิวพี
• รายการคลาสความซับซ้อน

• Princeton CS 597E: รายชื่อเอกสารเกี่ยวกับการลดความสุ่ม
• เอกสารวิชา CS 225 ของมหาวิทยาลัยฮาร์วาร์ด: ความสุ่มเทียม (Pseudorandomness) เก็บถาวรเมื่อวันที่ 5 สิงหาคม 2546 ที่Wayback Machine