ในทางคณิตศาสตร์ฟังก์ชันบูลีนแบบหลีกเลี่ยง (ของตัวแปร) คือฟังก์ชันบูลีนที่อัลกอริทึมต้นไม้ตัดสินใจ ทุกตัว มีเวลาทำงานเท่ากับ พอดีดังนั้นอัลกอริทึมต้นไม้ตัดสินใจ ทุกตัว ที่แสดงถึงฟังก์ชันนี้จะมีเวลาทำงานในกรณีที่เลวร้ายที่สุดคือ ${\displaystyle f}$${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$

ประเภทของอัลกอริธึมที่พิจารณาในคำจำกัดความของฟังก์ชันบูลีนแบบหลีกเลี่ยงคือต้นไม้ตัดสินใจซึ่งแต่ละโหนดภายในจะทดสอบค่าของตัวแปรบูลีนที่กำหนดตัวใดตัวหนึ่ง และแยกสาขาตามนั้น โหนดใบแต่ละโหนดของต้นไม้จะระบุค่าของฟังก์ชันสำหรับอินพุตที่เข้าถึงโหนดนั้นความซับซ้อนของต้นไม้ตัดสินใจ ในกรณีที่เลวร้ายที่สุด ของต้นไม้ตัดสินใจที่กำหนดคือจำนวนตัวแปรที่ตรวจสอบบนเส้นทางจากรากไปยังใบที่ยาวที่สุดของต้นไม้ฟังก์ชันที่มีตัวแปร n ตัวทุกฟังก์ชันจะมีอัลกอริธึมต้นไม้ตัดสินใจที่ตรวจสอบตัวแปร n ตัวบนอินพุตทั้งหมด โดยใช้ต้นไม้ตัดสินใจซึ่งโหนดทั้งหมดในระดับ n จะทดสอบตัวแปรที่ n ฟังก์ชันจะหลีกเลี่ยงหากไม่มีต้นไม้ตัดสินใจอื่นสำหรับฟังก์ชันเดียวกันที่มีความซับซ้อนน้อยกว่า สำหรับฟังก์ชันแบบหลีกเลี่ยง ต้นไม้ตัดสินใจใดๆ จะต้องมีอินพุตอย่างน้อยหนึ่งตัวที่นำไปสู่เส้นทางในต้นไม้ซึ่งตัวแปรอินพุตทั้งหมดจะถูกตรวจสอบ^{[ 1 ]}${\displaystyle n}$${\displaystyle n}$${\displaystyle i}$${\displaystyle i}$

การสร้างฟังก์ชันที่ไม่หลีกเลี่ยงการตรวจสอบนั้นทำได้ง่ายมาก โดยการสร้างแผนผังการตัดสินใจที่แต่ละสาขาจะสิ้นสุดลงก่อนที่จะทดสอบตัวแปรทั้งหมด ตัวอย่างเช่น ฟังก์ชันที่เป็นจริงเสมอจะมีแผนผังการตัดสินใจที่ไม่มีการทดสอบใดๆ สำหรับตัวอย่างที่ซับซ้อนกว่านั้น ซึ่งใช้ตัวแปรทั้งหมดในการกำหนดค่าของฟังก์ชัน ลองพิจารณาฟังก์ชันที่มีตัวแปรสามตัว คือ, , และที่ส่งคืนค่าหรือขึ้นอยู่กับว่าเป็นจริงหรือเท็จตามลำดับ ฟังก์ชันนี้มีแผนผังการตัดสินใจที่ทดสอบ ก่อนแล้วจึงทดสอบเพียงหนึ่งในหรือในแต่ละสาขา ${\displaystyle x}$${\displaystyle y}$${\displaystyle z}$${\displaystyle y}$${\displaystyle z}$${\displaystyle x}$${\displaystyle x}$${\displaystyle y}$${\displaystyle z}$

หากกิ่งของต้นไม้ตัดสินใจสิ้นสุดลงก่อนที่จะทดสอบตัวแปรทั้งหมด แสดงว่าต้นไม้นั้นให้ค่าฟังก์ชันสำหรับชุดค่าผสมของอาร์กิวเมนต์ที่เป็นจำนวนคู่: ชุดค่าผสม โดยที่คือจำนวนตัวแปร และคือจำนวนที่ทดสอบตามกิ่งนั้น ดังนั้น หากฟังก์ชันบูลีนมีชุดค่าผสมของอาร์กิวเมนต์ที่เป็นจำนวนคี่ที่ทำให้ฟังก์ชันนั้นเป็นจริง ฟังก์ชันนั้นจะต้องหลีกเลี่ยง^{[ 1 ]}ตัวอย่างเช่น ฟังก์ชันตรรกะ andและ ฟังก์ชัน ตรรกะ orเป็นจริงสำหรับชุดค่าผสมของอาร์กิวเมนต์ 1 และ ตามลำดับ ซึ่งทั้งสองเป็นจำนวนคี่ (สำหรับ) ดังนั้นจึงหลีกเลี่ยง ${\displaystyle 2^{nt}}$${\displaystyle n}$${\displaystyle t}$${\displaystyle 2^{n}-1}$${\displaystyle n>0}$

แนวคิดของฟังก์ชันหลบเลี่ยงได้รับการแนะนำโดยเชื่อมโยงกับการศึกษาอัลกอริทึมกราฟสำหรับกราฟที่กำหนดใน แบบ จำลองกราฟโดยปริยาย ซึ่งอัลกอริทึมสามารถเข้าถึงกราฟได้เฉพาะผ่านรูทีนย่อยสำหรับการทดสอบความติดกันของจุดยอด ในแอปพลิเคชันนี้คุณสมบัติของกราฟสามารถอธิบายได้ว่าเป็นฟังก์ชันบูลีนซึ่งตัวแปรอินพุตจะเป็นจริงหากมีขอบอยู่ระหว่างจุดยอดสองจุด และคุณสมบัติจะหลบเลี่ยงได้หากทุกอัลกอริทึมต้อง (บนอินพุตบางอย่าง) ทดสอบการมีอยู่ของขอบที่เป็นไปได้แต่ละขอบ งานในช่วงแรกในด้านนี้พิสูจน์แล้วว่าต้องทดสอบขอบจำนวนคงที่สำหรับคุณสมบัติกราฟแบบโมโนโทนที่ไม่ธรรมดาใดๆ โดยที่ "ไม่ธรรมดา" หมายความว่าฟังก์ชันมีค่ามากกว่าหนึ่งค่า และ "โมโนโทน" หมายความว่าการเพิ่มขอบลงในกราฟไม่สามารถเปลี่ยนค่าของฟังก์ชันจากจริงเป็นเท็จได้ ผลลัพธ์บางส่วนเหล่านี้เป็นแรงบันดาลใจให้เกิดการกำหนดสมมติฐาน Aanderaa–Karp–Rosenbergซึ่งยังไม่ได้รับการพิสูจน์ โดยที่คุณสมบัติกราฟแบบโมโนโทนที่ไม่ธรรมดาทั้งหมดนั้นหลบเลี่ยงได้^{[ 1 ]}

ข้อสันนิษฐานของ Aanderaa–Karp–Rosenberg จะเป็นผลมาจากข้อสันนิษฐานทั่วไปเกี่ยวกับการหลีกเลี่ยงของฟังก์ชันบูลีน: ว่าฟังก์ชันบูลีนโมโนโทนที่ไม่ธรรมดาทุกฟังก์ชันที่มีสมมาตรที่แปลงตัวแปรใดๆ ไปเป็นตัวแปรอื่นใดๆ นั้นเป็นฟังก์ชันที่หลีกเลี่ยง ข้อสันนิษฐานนี้ยังไม่ได้รับการพิสูจน์ แต่เป็นที่ทราบกันว่าเป็นจริงสำหรับค่าบางค่าของรวมถึงกำลังของจำนวนเฉพาะ [ ^{1 ] [ 2 ] มัน}ถูกเรียกว่า ข้อสันนิษฐาน การหลีกเลี่ยง^{[ 3 ]}${\displaystyle n}$