ในการเข้ารหัสและทฤษฎีการคำนวณการทดสอบบิตถัดไป^{[ 1 ]}เป็นการทดสอบกับตัวสร้างเลขสุ่มเทียมเรากล่าวว่าลำดับของบิตผ่านการทดสอบบิตถัดไปสำหรับตำแหน่งใดๆ${\displaystyle i}$ในลำดับนั้น หากผู้โจมตีคนใดที่รู้ลำดับนั้น${\displaystyle i}$บิตแรกๆ (แต่ไม่ใช่ค่าเริ่มต้น) ไม่สามารถทำนายได้${\displaystyle (i+1)}$st ที่มีกำลังการประมวลผลที่เหมาะสม

อนุญาต${\displaystyle P}$เป็นพหุนาม และ${\displaystyle S=\{S_{k}\}}$เป็นชุดของเซตต่างๆ โดยที่${\displaystyle S_{k}}$ประกอบด้วย${\displaystyle P(k)}$ลำดับที่มีความยาว -บิต นอกจากนี้ ให้${\displaystyle \mu _{k}}$ให้เป็นการกระจายความน่าจะเป็นของสตริงใน${\displaystyle S_{k}}$.

ต่อไปนี้เราจะกำหนดการทดสอบบิตถัดไปในสองวิธีที่แตกต่างกัน

การทดสอบบิตถัดไปเป็นกรณีเฉพาะของการทดสอบของเหยาสำหรับลำดับสุ่ม และการผ่านการทดสอบนี้จึงเป็น เงื่อนไข ที่จำเป็นสำหรับการผ่านการทดสอบของเหยาอย่างไรก็ตาม เหยาได้แสดงให้เห็นแล้วว่าเป็นเงื่อนไขที่เพียงพอ^{[ 1 ]}

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

อนุญาต${\displaystyle {\mathcal {M}}}$เป็นตัวแยกแยะสำหรับการทดสอบของเหยาในเวอร์ชันเชิงความน่าจะเป็น กล่าวคือ เครื่องจักรทัวริงเชิงความน่าจะเป็นที่ทำงานในเวลาพหุนาม โดยที่มีพหุนามอยู่${\displaystyle Q}$โดยที่สำหรับจำนวนอนันต์${\displaystyle k}$

${\displaystyle |p_{k,S}^{\mathcal {M}}-p_{k,U}^{\mathcal {M}}|\geq {\frac {1}{Q(k)}}}$

อนุญาต${\displaystyle R_{k,i}=\{s_{1}\ldots s_{i}u_{i+1}\ldots u_{P(k)}|s\in S_{k},u\in \{0,1\}^{P(k)}\}}$เรามี:${\displaystyle R_{k,0}=\{0,1\}^{P(k)}}$และ${\displaystyle R_{k,P(k)}=S_{k}}$จากนั้นเราก็สังเกตเห็นว่า${\displaystyle \sum _{i=0}^{P(k)}|p_{k,R_{k,i+1}}^{\mathcal {M}}-p_{k,R_{k,i}}^{\mathcal {M}}|\geq |p_{k,R_{k,P(k)}}^{\mathcal {M}}-p_{k,R_{k,0}}^{\mathcal {M}}|=|p_{k,S}^{\mathcal {M}}-p_{k,U}^{\mathcal {M}}|\geq {\frac {1}{Q(k)}}}$ดังนั้น อย่างน้อยหนึ่งในนั้น${\displaystyle |p_{k,R_{k,i+1}}^{\mathcal {M}}-p_{k,R_{k,i}}^{\mathcal {M}}|}$ไม่ควรเล็กกว่า${\displaystyle {\frac {1}{Q(k)P(k)}}}$.

ต่อไป เราจะพิจารณาการแจกแจงความน่าจะเป็น${\displaystyle \mu _{k,i}}$และ${\displaystyle {\overline {\mu _{k,i}}}}$บน${\displaystyle R_{k,i}}$. การกระจาย${\displaystyle \mu _{k,i}}$คือการแจกแจงความน่าจะเป็นของการเลือก${\displaystyle i}$ส่วนแรกใน${\displaystyle S_{k}}$โดยมีความน่าจะเป็นที่กำหนดโดย${\displaystyle \mu _{k}}$และ${\displaystyle P(k)-i}$บิตที่เหลือจะถูกสุ่มอย่างสม่ำเสมอ ดังนั้นเราจึงได้ดังนี้:

ดังนั้นเราจึงมี${\displaystyle \mu _{k,i}={\frac {1}{2}}(\mu _{k,i+1}+{\overline {\mu _{k,i+1}}})}$(เทคนิคแคลคูลัสอย่างง่ายแสดงให้เห็นสิ่งนี้) ดังนั้นการแจกแจง${\displaystyle \mu _{k,i+1}}$และ${\displaystyle {\overline {\mu _{k,i+1}}}}$สามารถแยกแยะได้โดย${\displaystyle {\mathcal {M}}}$โดยไม่เสียความเป็นทั่วไป เราสามารถสมมติได้ว่า${\displaystyle p_{\mu _{k,i+1}}^{\mathcal {M}}-p_{\overline {\mu _{k,i+1}}}^{\mathcal {M}}\geq {\frac {1}{2}}+{\frac {1}{R(k)}}}$, กับ${\displaystyle R}$พหุนาม

สิ่งนี้ทำให้เราสามารถสร้างเครื่องจักรทัวริงที่แก้ปัญหาการทดสอบบิตถัดไปได้: เมื่อได้รับ${\displaystyle i}$ส่วนแรกๆ ของลำดับ${\displaystyle {\mathcal {N}}}$เติมข้อมูลอินพุตนี้ด้วยการคาดเดาบิต${\displaystyle l}$แล้วก็${\displaystyle P(k)-i-1}$บิตสุ่มที่เลือกด้วยความน่าจะเป็นสม่ำเสมอ จากนั้นจึงเริ่มทำงาน${\displaystyle {\mathcal {M}}}$และผลลัพธ์${\displaystyle l}$ถ้าผลลัพธ์คือ${\displaystyle 1}$, และ${\displaystyle 1-l}$อื่น.