ในทฤษฎีความซับซ้อนของการคำนวณบทพิสูจน์การสลับของ Håstadเป็นเครื่องมือสำคัญในการพิสูจน์ขอบเขตล่างของขนาดวงจรบูลีนที่ มีความลึกคงที่ Johan Håstadเป็นผู้นำเสนอบทพิสูจน์นี้เป็นครั้งแรกเพื่อพิสูจน์ว่าวงจรบูลีนAC ⁰ที่มีความลึกkต้องการขนาดเพื่อคำนวณฟังก์ชันพาริตีบนบิต^{[ 1 ]}ต่อมาเขาได้รับรางวัลGödel Prizeสำหรับผลงานนี้ในปี 1994 ${\displaystyle \exp(\Omega (n^{1/(k-1)}))}$${\displaystyle n}$

ทฤษฎีบทการสลับ (switching lemma) อธิบายพฤติกรรมของวงจรระดับความลึก 2 ภายใต้ข้อจำกัดแบบสุ่มกล่าวคือ เมื่อกำหนดค่าพิกัดส่วนใหญ่แบบสุ่มให้เป็น 0 หรือ 1 โดยเฉพาะอย่างยิ่ง จากทฤษฎีบทนี้ จะเห็นได้ว่าสูตรในรูปแบบปกติแบบเชื่อมโยง (นั่นคือ AND ของ OR) จะกลายเป็นสูตรในรูปแบบปกติแบบแยก (OR ของ AND) ภายใต้ข้อจำกัดแบบสุ่ม และในทางกลับกัน การ "สลับ" นี้เองที่ทำให้ทฤษฎีบทนี้ได้ชื่อว่า "สลับ"

พิจารณาสูตรความกว้างในรูปแบบปกติแบบแยกส่วน (ย่อว่า DNF) ซึ่งเป็นการ รวมกัน ของประโยคเงื่อนไขแบบOR และการรวมกัน ของ ตัวอักษรเงื่อนไขแบบ AND ( หรือการปฏิเสธของมัน) ตัวอย่างเช่นเป็นตัวอย่างของสูตรในรูปแบบนี้ที่มีความกว้าง 2 ${\displaystyle w}$${\displaystyle F=C_{1}\vee C_{2}\vee \cdots \vee C_{m}}$${\displaystyle C_{\ell }}$${\displaystyle w}$${\displaystyle x_{i}}$${\displaystyle \neg x_{i}}$${\displaystyle (\neg x_{1}\wedge x_{2})\vee (x_{2}\wedge x_{3})\vee (x_{2}\wedge x_{3})}$

ให้แทนสูตรภายใต้ข้อจำกัดแบบสุ่ม: แต่ละถูกกำหนดให้เป็น 0 หรือ 1 อย่างอิสระด้วยความน่าจะเป็นแล้ว สำหรับค่าคงที่C ที่มีขนาดใหญ่พอสมควร ทฤษฎีบทการสลับกล่าวว่า ${\displaystyle F|R_{p}}$${\displaystyle x_{i}}$${\displaystyle (1-p)/2}$

${\displaystyle \Pr[\operatorname {DT} (F\mid R_{p})\geq t]<C(pw)^{t},}$

โดยที่แสดงถึงความซับซ้อนของต้นไม้ตัดสินใจจำนวนบิตที่ จำเป็นในการ คำนวณฟังก์ชัน^{[ 2 ]}${\displaystyle \operatorname {DT} (f)}$${\displaystyle x}$${\displaystyle f}$

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

การพิสูจน์ดั้งเดิมของทฤษฎีบทการสลับ ( Håstad 1987 ) เกี่ยวข้องกับการใช้ความน่าจะเป็นแบบมีเงื่อนไขต่อมามีการพิสูจน์ที่ง่ายกว่าโดยRazborov (1993)และBeame (1994)สำหรับข้อมูลเบื้องต้น โปรดดูบทที่ 14 ในArora & Barak (2009 )

ทฤษฎีบทการสลับเป็นเครื่องมือสำคัญที่ใช้ในการทำความเข้าใจคลาสความซับซ้อนของวงจรAC ⁰ซึ่งประกอบด้วยวงจรที่มีความลึกคงที่ซึ่งประกอบด้วย AND, OR และ NOT การประยุกต์ใช้ทฤษฎีบทนี้ครั้งแรกของ Håstad คือการสร้างขอบเขตล่างแบบเลขชี้กำลังที่แน่นหนาสำหรับวงจรดังกล่าวที่คำนวณPARITYโดยปรับปรุงขอบเขตล่างแบบซูเปอร์พหุนามก่อนหน้าของMerrick Furst , James SaxeและMichael Sipser ^{[ 3 ]}และMiklós Ajtaiอย่าง อิสระ ^{[ 4 ]}การทำเช่นนี้ทำได้โดยการประยุกต์ใช้ทฤษฎีบทการสลับหลายครั้ง โดยที่คือความลึกของวงจร: การประยุกต์ใช้แต่ละครั้งจะลบชั้นของวงจรออกจนเหลือวงจรที่ง่ายมาก ในขณะที่ PARITY ยังคงเป็น PARITY ภายใต้ข้อจำกัดแบบสุ่ม ดังนั้นจึงยังคงมีความซับซ้อน ดังนั้นวงจรที่คำนวณ PARITY ต้องมีความลึกสูง^{[ 5 ]}${\displaystyle d-1}$${\displaystyle d}$

บทพิสูจน์การสลับเป็นพื้นฐานสำหรับขอบเขตของสเปกตรัมฟูริเยร์ของวงจร AC ^{0 [ 5 ]}และอัลกอริธึมสำหรับการเรียนรู้วงจรดังกล่าว^{[ 6 ]}

• เอซี⁰
• วงจรบูลีน
• ความสามารถในการทำให้วงจรเป็นจริง
• ปัญหาค่าวงจร
• ฟังก์ชันพาริตี