หลักการลดรูปตัวเองแบบสุ่ม ( RSR ) คือกฎที่ว่าอัลกอริทึมที่ดีสำหรับกรณีเฉลี่ยจะหมายถึงอัลกอริทึมที่ดีสำหรับกรณีที่เลวร้ายที่สุด RSR คือความสามารถในการแก้ปัญหาทุกกรณีได้โดยการแก้ปัญหาเพียงส่วนน้อยเท่านั้น

ถ้าฟังก์ชันf ที่สามารถประเมินค่าอินสแตนซ์x ใดๆ ได้ สามารถลดทอนลงได้ในเวลาพหุนามไปเป็นการประเมินค่าf บนอินสแตน ซ์สุ่มy _iหนึ่งตัวหรือมากกว่านั้น ฟังก์ชันนั้นก็จะสามารถลดทอนตัวเองได้ (หรือที่เรียกว่าการลดทอนตัวเองแบบสม่ำเสมอที่ไม่ปรับตัว ) ในการลดทอนตัวเองแบบสุ่ม อินสแตนซ์กรณีที่เลวร้ายที่สุดx ใดๆในโดเมนของfจะถูกแมปไปยังชุดอินสแตนซ์สุ่มy ₁ , ..., y _kโดยทำเช่นนี้เพื่อให้ สามารถคำนวณ f ( x ) ได้ในเวลาพหุนาม เมื่อกำหนดลำดับการโยนเหรียญจากการแมปxและf ( y ₁ ), ..., f ( y _k ) ดังนั้น เมื่อหาค่าเฉลี่ยโดยสัมพันธ์กับการกระจายที่เกิดขึ้นบนy _iความซับซ้อนในกรณีเฉลี่ยของfจะเหมือนกัน (ภายในปัจจัยพหุนาม) กับความซับซ้อนแบบสุ่มในกรณีที่เลวร้ายที่สุด  ของ f

กรณีพิเศษที่ควรสังเกตคือ เมื่อแต่ละอินสแตนซ์แบบสุ่มy _iกระจายอย่างสม่ำเสมอทั่วทั้งเซตขององค์ประกอบในโดเมนของfที่มีความยาวเท่ากับ | x | ในกรณีนี้fจะมีความยากโดยเฉลี่ยเท่ากับกรณีที่เลวร้ายที่สุด วิธีการนี้มีข้อจำกัดที่สำคัญสองประการ ประการแรก การสร้างy ₁ , ..., y _kจะดำเนินการแบบไม่ปรับเปลี่ยน ซึ่งหมายความว่าy ₂จะถูกเลือกก่อนที่ จะทราบ f ( y ₁ ) ประการที่สอง ไม่จำเป็นว่าจุดy ₁ , ..., y _kจะต้องกระจายอย่างสม่ำเสมอ

ปัญหาที่ต้องการความเป็นส่วนตัวของข้อมูล (โดยทั่วไปคือปัญหาเกี่ยวกับการเข้ารหัส ) สามารถใช้การสุ่มเพื่อรับประกันความเป็นส่วนตัวนั้นได้ อันที่จริง ระบบการเข้ารหัสที่ปลอดภัยอย่างแท้จริงเพียงระบบเดียว ( one-time pad ) นั้น ความปลอดภัยขึ้นอยู่กับความสุ่มของข้อมูลกุญแจที่ป้อนให้กับระบบโดย สิ้นเชิง

สาขาวิชาการเข้ารหัสลับใช้ประโยชน์จากข้อเท็จจริงที่ว่าฟังก์ชันทางทฤษฎีจำนวนบางอย่างสามารถลดรูปตัวเองได้แบบสุ่ม ซึ่งรวมถึงการเข้ารหัสเชิงความน่าจะเป็นและการสร้างเลขสุ่มเทียม ที่มีความแข็งแกร่งทางด้านการเข้ารหัสลับ นอกจากนี้ แผนการ ซ่อนข้อมูล (ที่อุปกรณ์ส่วนตัวที่อ่อนแอใช้อุปกรณ์สาธารณะที่แข็งแกร่งโดยไม่เปิดเผยข้อมูล) ก็สามารถยกตัวอย่างได้ง่ายๆ ด้วยการลดรูปตัวเองแบบสุ่ม

ปัญหาลอการิทึมแบบไม่ต่อเนื่องปัญหาเศษเหลือกำลังสองปัญหา การผกผัน RSAและปัญหาการคำนวณค่าถาวรของเมทริกซ์ ล้วนเป็นปัญหาที่สามารถลดรูปได้เองแบบสุ่ม

ทฤษฎีบท : กำหนดให้กลุ่มวัฏจักรGที่มีขนาด | G | ถ้าอัลกอริทึมเวลาพหุนามเชิงกำหนดAคำนวณลอการิทึมแบบไม่ต่อเนื่องสำหรับเศษส่วน 1/poly( n ) ของอินพุตทั้งหมด (โดยที่n = log | G | คือขนาดของอินพุต) แล้วจะมีอัลกอริทึมเวลาพหุนามแบบสุ่มสำหรับลอการิทึมแบบไม่ต่อเนื่องสำหรับอินพุตทั้งหมด

กำหนดให้ gเป็นตัวสร้างของกลุ่มวัฏจักรG = {  g ⁱ | 0 ≤ i < | G | } และx ∈ Gลอการิทึมแบบไม่ต่อเนื่องของxบนฐานgคือจำนวนเต็มk (0 ≤ k < | G |) โดยที่x = g ^kให้Bมีการแจกแจงแบบเอกรูปบน {0,...,| G | − 1} ดังนั้นxg ^B = g ^{k + B}ก็มีการแจกแจงแบบเอกรูปบนG เช่นกัน ดังนั้นxg ^Bจึงไม่ขึ้นอยู่กับxและสามารถคำนวณลอการิทึมของมันได้ด้วยความน่าจะเป็น 1/poly( n ) ในเวลาพหุนาม แล้ว log _g x ≡ log _g xg ^B - B (mod | G |) และลอการิทึมแบบไม่ต่อเนื่องสามารถลดรูปได้ด้วยตัวเอง

จากนิยามของค่าคงที่ถาวรของเมทริกซ์ เป็นที่ชัดเจนว่าPERM ( M ) สำหรับเมทริกซ์n x n ใดๆ MคือพหุนามหลายตัวแปรดีกรีnเหนือสมาชิกในMการคำนวณค่าคงที่ถาวรของเมทริกซ์เป็นงานคำนวณที่ยากลำบาก — PERMได้รับการพิสูจน์แล้วว่าเป็นปัญหา#P-complete ( พิสูจน์ ) ยิ่งไปกว่านั้น ความสามารถในการคำนวณPERM ( M ) สำหรับเมทริกซ์ส่วนใหญ่บ่งบอกถึงการมีอยู่ของโปรแกรมสุ่มที่คำนวณPERM ( M ) สำหรับเมทริกซ์ทั้งหมด ซึ่งแสดงให้เห็นว่าPERMสามารถลดรูปตัวเองได้แบบสุ่ม การอภิปรายด้านล่างนี้พิจารณากรณีที่สมาชิกของเมทริกซ์ถูกดึงมาจากฟิลด์จำกัดFp สำหรับ จำนวนเฉพาะ p _บางตัวและการคำนวณทางคณิตศาสตร์ทั้งหมดดำเนินการในฟิลด์นั้น

ให้Xเป็นเมทริกซ์สุ่ม_{ขนาด n x n ที่มีสมาชิกจาก Fp}เนื่องจากสมาชิกทั้งหมดของเมทริกซ์M + kX ใดๆ เป็นฟังก์ชันเชิงเส้นของkดังนั้น โดยการประกอบฟังก์ชันเชิงเส้นเหล่านั้นกับพหุนามหลายตัวแปรดีกรีn ที่คำนวณ PERM ( M ) เราจะได้ พหุนามดีกรี n อีกตัวหนึ่ง บนkซึ่งเราจะเรียกว่าp ( k ) เห็นได้ชัดว่าp (0) เท่ากับค่าถาวรของ M

สมมติว่าเรารู้จักโปรแกรมที่คำนวณค่าที่ถูกต้องของPERM ( A ) สำหรับ เมทริก ซ์n x n ส่วนใหญ่ ที่มีสมาชิกจากFp _---โดยเฉพาะ 1 − 1/( 3n ) ของเมทริกซ์เหล่านั้น จากนั้นด้วยความน่าจะเป็นประมาณสองในสาม เราสามารถคำนวณPERM ( M + kX ) สำหรับk = 1, 2, ..., n + 1 ได้ เมื่อเรามี ค่า n + 1 ค่าเหล่านั้นแล้ว เราสามารถหาค่าสัมประสิทธิ์ของp ( k ) โดยใช้การประมาณค่าในช่วง (จำไว้ว่าp ( k ) มีดีกรีn ) เมื่อเรารู้ ค่า p ( k ) ที่แน่นอนแล้ว เราจะประเมินค่าp (0) ซึ่งเท่ากับPERM ( M )

ถ้าเราทำเช่นนั้น เรามีความเสี่ยงที่จะผิดพลาด 1 ใน 3 ของเวลา แต่โดยการสุ่มเลือกX หลายๆ ตัว และทำซ้ำขั้นตอนข้างต้นหลายๆ ครั้ง และให้คำตอบเฉพาะคำตอบที่ได้รับเสียงส่วนใหญ่ เราสามารถลดอัตราความผิดพลาดลงได้อย่างมาก

• หาก ปัญหา NP-completeสามารถลดรูปตัวเองได้แบบสุ่มโดยไม่ปรับตัว ลำดับชั้นพหุนาม จะยุบตัวลง เหลือΣ ₃
• ถ้า ปัญหา CoNP-hardสามารถลดรูปตัวเองแบบสุ่มได้ในO ( log n / n ) แล้ว Σ ₂ = Π ₂