Probabilistic complexity classes
คลาสความซับซ้อนที่น่าจะเป็น
อ่าน 1 นาทีโพสต์บีคิวพี
CS1 maint: multiple names: authors listในทฤษฎีความซับซ้อนของการคำนวณPostBQPคือกลุ่มความซับซ้อน ที่ประกอบด้วย ปัญหาการคำนวณทั้งหมดที่สามารถแก้ไขได้ในเวลาพหุนามบนเครื่องทัวริงควอนตัมที่มีการเลือกภายหลังและข้อผิดพลาดที่จำก...
อ่าน 1 นาทีโปรโตคอลอาร์เธอร์-เมอร์ลิน
Probabilistic complexity classesในทฤษฎีความซับซ้อนของการคำนวณ โปรโตคอล Arthur –Merlinซึ่งแนะนำโดยBabai (1985)เป็นระบบพิสูจน์แบบโต้ตอบที่การโยนเหรียญ ของผู้ตรวจสอบ ถูกจำกัดให้เป็นสาธารณะ (กล่าวคือ...
อ่าน 1 นาทีPP (ความซับซ้อน)
Probabilistic complexity classesในทฤษฎีความซับซ้อนPPหรือPPT คือคลาสของปัญหาการตัดสินใจที่สามารถแก้ไขได้ด้วยเครื่องจักรทัวริงเชิงความน่า จะเป็น ในเวลาพหุนามโดยมีความน่าจะเป็นของข้อผิดพลาดน้อยกว่า 1/2 สำหรับทุกกรณี
อ่าน 1 นาทีZPP (ความซับซ้อน)
Probabilistic complexity classesในทฤษฎีความซับซ้อนZPP ( zero-error probabilistic polynomial time ) คือกลุ่มความซับซ้อนของปัญหาที่ มี เครื่องจักรทัวริงเชิงความน่าจะเป็นที่มีคุณสมบัติดังต่อไปนี้:
อ่าน 1 นาทีคิวเอ็มเอ
Probabilistic complexity classesQMAซึ่งเป็นคำย่อของQuantum Merlin Arthurหมายถึงกลุ่มความซับซ้อนในทฤษฎีความซับซ้อนของการคำนวณเป็นเซตของภาษาเชิงรูปธรรม ทั้งหมด ที่ตรงตามคุณสมบัติต่อไปนี้:
อ่าน 1 นาทีQIP (ความซับซ้อน)
Probabilistic complexity classesในทฤษฎีความซับซ้อนของการคำนวณคลาสQIP (ซึ่งย่อมาจากQuantum Interactive Proof ) คือคลาสความซับซ้อนแบบคลาสสิกIP ใน การคำนวณ ควอนตัม
อ่าน 1 นาทีโปรโตคอลอาร์เธอร์-เมอร์ลิน
Probabilistic complexity classesในทฤษฎีความซับซ้อนของการคำนวณ โปรโตคอล Arthur –Merlinซึ่งแนะนำโดยBabai (1985)เป็นระบบพิสูจน์แบบโต้ตอบที่การโยนเหรียญ ของผู้ตรวจสอบ ถูกจำกัดให้เป็นสาธารณะ (กล่าวคือ...
อ่าน 1 นาทีบีพีพี (ความซับซ้อน)
Probabilistic complexity classesในทฤษฎีความซับซ้อนของการคำนวณซึ่งเป็นสาขาหนึ่งของวิทยาศาสตร์คอมพิวเตอร์ ปัญหาการตัดสินใจ แบบเวลาพหุนามเชิงความน่าจะเป็นที่มีขอบเขตความคลาดเคลื่อน ( BPP )
RL (ความซับซ้อน)
CS1 maint: location missing publisherพื้นที่ลอการิทึมแบบสุ่ม ( RL ) บางครั้งเรียกว่าRLP (พื้นที่ลอการิทึมแบบสุ่มในเวลาพหุนาม) เป็นคลาสความซับซ้อนของ ปัญหา
อ่าน 1 นาทีทรัพย์สินทางปัญญา (ความซับซ้อน)
All pages needing cleanupในทฤษฎีความซับซ้อนของการคำนวณคลาสIP (ซึ่งย่อมาจากinteractive proof ) คือคลาสของปัญหาที่สามารถแก้ไขได้ด้วยระบบพิสูจน์แบบโต้ตอบมันเท่ากับคลาสPSPACEผลลัพธ์นี้ได้รับการพิสูจน์แล้วในชุด...
อ่าน 1 นาทีRP (ความซับซ้อน)
Probabilistic complexity classesในทฤษฎีความซับซ้อนของการคำนวณเวลาพหุนามสุ่ม ( RP ) คือกลุ่มความซับซ้อนของปัญหาการตัดสินใจที่ มี เครื่องจักรทัวริงเชิงความน่าจะเป็นที่มีคุณสมบัติดังต่อไปนี้: