ในทฤษฎีความซับซ้อนของการคำนวณโมเดลต้นไม้ตัดสินใจเป็นโมเดลการคำนวณที่สามารถพิจารณาได้ว่าอัลกอริทึม เป็น ต้นไม้ตัดสินใจ กล่าว คือ เป็นลำดับของการสอบถามหรือการทดสอบที่ดำเนินการอย่างปรับเปลี่ยนได้ ดังนั้นผลลัพธ์ของการทดสอบก่อนหน้าจึงสามารถส่งผลต่อการทดสอบที่ดำเนินการต่อไปได้

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

แบบจำลองต้นไม้ตัดสินใจมีบทบาทสำคัญในการกำหนดขอบเขตล่างของความซับซ้อนของปัญหาการคำนวณและอัลกอริธึมบางประเภท มีการนำเสนอแบบจำลองต้นไม้ตัดสินใจหลายรูปแบบ โดยขึ้นอยู่กับแบบจำลองการคำนวณและประเภทของคำถามที่อัลกอริธึมสามารถดำเนินการได้

ตัวอย่างเช่น การใช้เหตุผลแบบแผนผังการตัดสินใจแสดงให้เห็นว่า การเรียง ลำดับ แบบเปรียบเทียบจะต้องทำการเปรียบเทียบ สำหรับการเรียงลำดับแบบเปรียบเทียบ คำถามคือการเปรียบเทียบสองรายการโดยมีผลลัพธ์สองอย่าง (โดยสมมติว่าไม่มีรายการใดเท่ากัน): หรือการเรียงลำดับแบบเปรียบเทียบสามารถแสดงเป็นแผนผังการตัดสินใจในแบบจำลองนี้ได้ เนื่องจากอัลกอริธึมการเรียงลำดับดังกล่าวจะทำเฉพาะคำถามประเภทนี้เท่านั้น ${\displaystyle n}$${\displaystyle n\log(n)}$${\displaystyle a,b}$${\displaystyle a<b}$${\displaystyle a>b}$

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

ตัวอย่างเช่น อัลกอริทึมการเรียงลำดับจำนวนมากเป็นการเรียงลำดับแบบเปรียบเทียบซึ่งหมายความว่าอัลกอริทึมเหล่านั้นจะได้รับข้อมูลเกี่ยวกับลำดับอินพุตผ่านการเปรียบเทียบเฉพาะที่เท่านั้น กล่าวคือ การทดสอบว่า, , หรือ เป็นจริงหรือไม่ โดยสมมติว่ารายการที่จะเรียงลำดับทั้งหมดแตกต่างกันและเปรียบเทียบกันได้ เราสามารถตั้งคำถามใหม่ได้เป็นคำถามใช่หรือไม่ใช่: เป็นจริงหรือไม่? ${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$${\displaystyle x_{i}<x_{j}}$${\displaystyle x_{i}=x_{j}}$${\displaystyle x_{i}>x_{j}}$${\displaystyle x_{i}>x_{j}}$

อัลกอริทึมเหล่านี้สามารถจำลองได้เป็นต้นไม้ตัดสินใจแบบไบนารี โดยที่คำถามเป็นการเปรียบเทียบ: โหนดภายในสอดคล้องกับคำถาม และโหนดลูกของโหนดนั้นจะสอดคล้องกับคำถามถัดไปเมื่อคำตอบของคำถามนั้นเป็นใช่หรือไม่ใช่ สำหรับโหนดใบ ผลลัพธ์จะสอดคล้องกับการเรียงสับเปลี่ยน ที่อธิบายว่าลำดับอินพุตถูกสลับจากรายการที่เรียงลำดับอย่างสมบูรณ์อย่างไร (การเรียงสับเปลี่ยนผกผันนี้จะจัดเรียงลำดับอินพุตใหม่) ${\displaystyle \pi }$${\displaystyle \pi ^{-1}}$

เราสามารถแสดงให้เห็นว่าการเรียงลำดับแบบเปรียบเทียบต้องใช้การเปรียบเทียบผ่านข้อโต้แย้งง่ายๆ: สำหรับอัลกอริทึมที่ถูกต้อง จะต้องสามารถแสดงผลการเรียงสับเปลี่ยนที่เป็นไปได้ทั้งหมดขององค์ประกอบได้ มิฉะนั้น อัลกอริทึมจะล้มเหลวสำหรับการเรียงสับเปลี่ยนเฉพาะนั้นเป็นอินพุต ดังนั้น ต้นไม้ตัดสินใจที่สอดคล้องกันจะต้องมีใบอย่างน้อยเท่ากับจำนวนการเรียงสับเปลี่ยน: ใบต้นไม้ไบนารี ใดๆ ที่มีใบอย่างน้อยจะมีความลึกอย่างน้อยดังนั้น นี่จึงเป็นขอบเขตล่างของเวลาการทำงานของอัลกอริทึมการเรียงลำดับแบบ เปรียบเทียบ ในกรณีนี้ การมีอยู่ของอัลกอริทึมการเรียงลำดับแบบเปรียบเทียบจำนวนมากที่มีความซับซ้อนของเวลาดังกล่าว เช่นmergesortและheapsortแสดงให้เห็นว่าขอบเขตนั้นแน่น^{[ 2 ] : 91} ${\displaystyle \โอเมก้า (n\log(n))}$${\displaystyle n}$${\displaystyle n!}$${\displaystyle n!}$${\displaystyle \log _{2}(n!=\โอเมก้า (n\log _{2}(n))}$

ข้อโต้แย้งนี้ไม่ได้ใช้ข้อมูลใดๆ เกี่ยวกับประเภทของคำถาม ดังนั้นจึงเป็นการพิสูจน์ขอบเขตล่างสำหรับอัลกอริทึมการเรียงลำดับใดๆ ที่สามารถจำลองได้เป็นต้นไม้ตัดสินใจแบบไบนารี โดยพื้นฐานแล้ว นี่คือการเรียบเรียงใหม่ของข้อโต้แย้งเชิงทฤษฎีสารสนเทศที่ว่า อัลกอริทึมการเรียงลำดับที่ถูกต้องจะต้องเรียนรู้ข้อมูลอย่างน้อยบิตเกี่ยวกับลำดับอินพุต ดังนั้นจึงใช้ได้กับต้นไม้ตัดสินใจแบบสุ่มด้วยเช่นกัน ${\displaystyle \log _{2}(n!)}$

ขอบล่างของต้นไม้ตัดสินใจอื่นๆ ใช้ข้อเท็จจริงที่ว่าคำถามเป็นการเปรียบเทียบ ตัวอย่างเช่น ลองพิจารณาภารกิจในการใช้การเปรียบเทียบเท่านั้นเพื่อหาจำนวนที่เล็กที่สุดในบรรดาตัวเลข ก่อนที่จะสามารถกำหนดจำนวนที่เล็กที่สุดได้ ทุกจำนวนยกเว้นจำนวนที่เล็กที่สุดจะต้อง "แพ้" (เปรียบเทียบแล้วมากกว่า) อย่างน้อยหนึ่งการเปรียบเทียบ ดังนั้นจึงต้องใช้การเปรียบเทียบอย่างน้อย เพื่อหาค่าต่ำสุด (ข้อโต้แย้งเชิงทฤษฎีสารสนเทศในที่นี้ให้เพียงขอบล่างของ.) ข้อโต้แย้งที่คล้ายกันนี้ใช้ได้กับขอบล่างทั่วไปสำหรับการคำนวณสถิติลำดับ^{[ 2 ] : 214} ${\displaystyle n}$${\displaystyle n-1}$${\displaystyle \log(n)}$

ต้นไม้ตัดสินใจเชิงเส้นเป็นการขยายแนวคิดของต้นไม้ตัดสินใจเชิงเปรียบเทียบข้างต้นไปสู่การคำนวณฟังก์ชันที่รับเวกเตอร์ จำนวนจริง เป็นอินพุต การทดสอบในต้นไม้ตัดสินใจเชิงเส้นเป็นฟังก์ชันเชิงเส้น: สำหรับการเลือกจำนวนจริงเฉพาะค่าหนึ่ง จะ ให้ผลลัพธ์เป็นเครื่องหมายของ(อัลกอริทึมในแบบจำลองนี้ขึ้นอยู่กับเครื่องหมายของผลลัพธ์เท่านั้น) ต้นไม้เปรียบเทียบเป็นต้นไม้ตัดสินใจเชิงเส้น เนื่องจากการเปรียบเทียบระหว่างและสอดคล้องกับฟังก์ชันเชิงเส้นจากนิยาม ต้นไม้ตัดสินใจเชิงเส้นสามารถระบุได้เฉพาะฟังก์ชันที่มีไฟเบอร์ ซึ่ง สามารถสร้างได้โดยการรวมและการตัดกันของครึ่งพื้นที่เท่านั้น ${\displaystyle x\in \mathbb {R} ^{n}}$${\displaystyle a_{0},\dots ,a_{n}}$${\displaystyle a_{0}+\textstyle \sum _{i=1}^{n}a_{i}x_{i}}$${\displaystyle x_{i}}$${\displaystyle x_{j}}$${\displaystyle x_{i}-x_{j}}$${\displaystyle f}$

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

แบบจำลองต้นไม้ตัดสินใจเหล่านี้ ซึ่งกำหนดโดยRabin ^{[ 3 ]}และReingold [ ^{4 ]}มักใช้เพื่อพิสูจน์ขอบเขตล่างในเรขาคณิตเชิงคำนวณ [ ^{5 ] ตัวอย่าง}เช่นBen-Orแสดงให้เห็นว่าความไม่ซ้ำกันขององค์ประกอบ (งานของการคำนวณโดยที่เป็น 0 ก็ต่อเมื่อมีพิกัดที่แตกต่างกันอยู่ซึ่ง) ต้องใช้ต้นไม้ตัดสินใจเชิงพีชคณิตที่มีความลึก^[ 6 ^{]สิ่งนี้}ได้รับการแสดงเป็นครั้งแรกสำหรับแบบจำลองการตัดสินใจเชิงเส้นโดย Dobkin และ Lipton ^{[ 7 ]}พวกเขายังแสดงขอบเขตล่างสำหรับต้นไม้ตัดสินใจเชิงเส้นในปัญหาเป้สะพายหลังซึ่งได้รับการขยายไปสู่ต้นไม้ตัดสินใจเชิงพีชคณิตโดย Steele และ Yao ^{[ 8 ]}${\displaystyle f:\mathbb {R} ^{n}\to \{0,1\}}$${\displaystyle f(x)}$${\displaystyle i,j}$${\displaystyle x_{i}=x_{j}}$${\displaystyle \โอเมก้า (n\log(n))}$${\displaystyle n^{2}}$

สำหรับต้นไม้ตัดสินใจแบบบูลีน งานคือการคำนวณค่าของฟังก์ชันบูลีนnบิตสำหรับอินพุตการสอบถามแต่ละครั้งสอดคล้องกับการอ่านบิตของอินพุตและผลลัพธ์คือการสอบถามแต่ละครั้งอาจขึ้นอยู่กับการสอบถามก่อนหน้า มีแบบจำลองการคำนวณหลายประเภทที่ใช้ต้นไม้ตัดสินใจซึ่งสามารถนำมาพิจารณาได้ โดยยอมรับแนวคิดความซับซ้อนหลายแบบที่เรียกว่า มาตร วัด ความซับซ้อน${\displaystyle f:\{0,1\}^{n}\to \{0,1\}}$${\displaystyle x\in \{0,1\}^{n}}$${\displaystyle x_{i}}$${\displaystyle f(x)}$

ถ้าผลลัพธ์ของต้นไม้ตัดสินใจคือสำหรับทุกค่าของ ต้นไม้ตัดสินใจนั้นจะเรียกว่า "คำนวณ" ได้ความลึกของต้นไม้คือจำนวนการสอบถามสูงสุดที่สามารถเกิดขึ้นได้ก่อนที่จะถึงใบและได้ผลลัพธ์ ความซับซ้อนของต้นไม้ ตัดสินใจแบบกำหนดได้ของคือความลึกที่น้อยที่สุดในบรรดาต้นไม้ตัดสินใจแบบกำหนดได้ทั้งหมดที่คำนวณได้ ${\displaystyle f(x)}$${\displaystyle x\in \{0,1\}^{n}}$${\displaystyle f}$${\displaystyle D(f)}$${\displaystyle f}$${\displaystyle f}$

วิธีหนึ่งในการกำหนดต้นไม้ตัดสินใจแบบสุ่มคือการเพิ่มโหนดเพิ่มเติมลงในต้นไม้ โดยแต่ละโหนดถูกควบคุมด้วยความน่าจะเป็นอีกนิยามหนึ่งที่เทียบเท่ากันคือการกำหนดให้เป็นการแจกแจงเหนือต้นไม้ตัดสินใจแบบกำหนดได้ โดยอิงจากนิยามที่สองนี้ ความซับซ้อนของต้นไม้แบบสุ่มถูกกำหนดให้เป็นความลึกที่มากที่สุดในบรรดาต้นไม้ทั้งหมดในส่วนสนับสนุนของการแจกแจงพื้นฐาน ถูกกำหนดให้เป็นความซับซ้อนของต้นไม้ตัดสินใจแบบสุ่มที่มีความลึกน้อยที่สุด ซึ่งผลลัพธ์มีความน่าจะเป็นอย่างน้อยสำหรับทุกค่า(กล่าวคือ มีข้อผิดพลาดสองด้านที่จำกัด) ${\displaystyle p_{i}}$${\displaystyle R_{2}(f)}$${\displaystyle f(x)}$${\displaystyle 2/3}$${\displaystyle x\in \{0,1\}^{n}}$

${\displaystyle R_{2}(f)}$เรียกว่าความ ซับซ้อนของต้นไม้ตัดสินใจแบบสุ่ม มอนเตคาร์โลเนื่องจากผลลัพธ์อาจไม่ถูกต้องได้โดยมีข้อผิดพลาดสองด้านที่จำกัดความซับซ้อนของต้นไม้ตัดสินใจ แบบ ลาสเวกัสจะวัด ความลึก ที่คาดหวังของต้นไม้ตัดสินใจที่ต้องถูกต้อง (กล่าวคือ มีข้อผิดพลาดเป็นศูนย์) นอกจากนี้ยังมีเวอร์ชันข้อผิดพลาดด้านเดียวที่จำกัด ซึ่งแสดงด้วยสัญลักษณ์. ${\displaystyle R_{0}(f)}$${\displaystyle R_{1}(f)}$

ความซับซ้อนของต้นไม้ตัดสินใจแบบไม่กำหนดของฟังก์ชันนั้น มักเรียกกันว่าความซับซ้อนของใบรับรองของฟังก์ชันนั้น มันวัดจำนวนบิตอินพุตที่อัลกอริทึมแบบไม่กำหนดจะต้องพิจารณาเพื่อประเมินฟังก์ชันนั้นได้อย่างแน่นอน

ตามหลักการแล้ว ความซับซ้อนของใบรับรองของat คือขนาดของเซตย่อยที่เล็กที่สุดของดัชนีโดยที่สำหรับทุกถ้าสำหรับทุกแล้วความซับซ้อนของใบรับรองของคือความซับซ้อนของใบรับรองสูงสุดเหนือทุกแนวคิดที่คล้ายกันซึ่งต้องการเพียงให้ผู้ตรวจสอบถูกต้องด้วยความน่าจะเป็น 2/3 จะใช้สัญลักษณ์แทน ${\displaystyle f}$${\displaystyle x}$${\displaystyle S\subseteq [n]}$${\displaystyle y\in \{0,1\}^{n}}$${\displaystyle y_{i}=x_{i}}$${\displaystyle i\in S}$${\displaystyle f(y)=f(x)}$${\displaystyle f}$${\displaystyle x}$${\displaystyle RC(f)}$

ความซับซ้อนของต้นไม้ตัดสินใจควอนตัมคือความลึกของต้นไม้ตัดสินใจควอนตัมที่มีความลึกน้อยที่สุดซึ่งให้ผลลัพธ์ด้วยความน่าจะเป็นอย่างน้อยสำหรับทุกค่าอีกปริมาณหนึ่งถูกกำหนดให้เป็นความลึกของต้นไม้ตัดสินใจควอนตัมที่มีความลึกน้อยที่สุดซึ่งให้ผลลัพธ์ด้วยความน่าจะเป็น 1 ในทุกกรณี (กล่าวคือ คำนวณได้อย่างแม่นยำ) และมักเรียกกันว่าความซับซ้อนของการสอบถามควอนตัมเนื่องจากนิยามโดยตรงของต้นไม้ตัดสินใจควอนตัมนั้นซับซ้อนกว่าในกรณีคลาสสิก เช่นเดียวกับกรณีแบบสุ่ม เรากำหนดและ ตาม ลำดับ ${\displaystyle Q_{2}(f)}$${\displaystyle f(x)}$${\displaystyle 2/3}$${\displaystyle x\in \{0,1\}^{n}}$${\displaystyle Q_{E}(f)}$${\displaystyle f(x)}$${\displaystyle f}$${\displaystyle Q_{2}(f)}$${\displaystyle Q_{E}(f)}$${\displaystyle Q_{0}(f)}$${\displaystyle Q_{1}(f)}$

แนวคิดเหล่านี้โดยทั่วไปถูกจำกัดด้วยแนวคิดของดีกรีและดีกรีโดยประมาณดีกรีของซึ่งเขียนแทนด้วยคือดีกรีที่เล็กที่สุดของพหุนามใดๆที่สอดคล้องกับเงื่อนไขสำหรับทุก ดีกรี โดยประมาณของซึ่งเขียนแทนด้วยคือดีกรีที่เล็กที่สุดของพหุนามใดๆที่สอดคล้องกับเงื่อนไขเมื่อใดก็ตามและ เมื่อ ใด ก็ตาม${\displaystyle f}$${\displaystyle \deg(f)}$${\displaystyle p}$${\displaystyle f(x)=p(x)}$${\displaystyle x\in \{0,1\}^{n}}$${\displaystyle f}$${\displaystyle {\widetilde {\deg }}(f)}$${\displaystyle p}$${\displaystyle p(x)\in [0,1/3]}$${\displaystyle f(x)=0}$${\displaystyle p(x)\in [2/3,1]}$${\displaystyle f(x)=1}$

Beals และคณะได้พิสูจน์แล้วว่าและ^{[ 9 ]}${\displaystyle Q_{0}(f)\geq \deg(f)/2}$${\displaystyle Q_{2}(f)\geq {\widetilde {\deg }}(f)/2}$

จากนิยามดังกล่าว จึงสรุปได้ทันทีว่า สำหรับฟังก์ชันบูลีน n บิต ทั้งหมด , , และการค้นหาขอบเขตบนที่ดีที่สุดในทิศทางตรงกันข้ามเป็นเป้าหมายสำคัญในสาขาความซับซ้อนของการค้นหาข้อมูล ${\displaystyle n}$${\displaystyle f}$${\displaystyle Q_{2}(f)\leq R_{2}(f)\leq R_{1}(f)\leq R_{0}(f)\leq D(f)\leq n}$${\displaystyle Q_{2}(f)\leq Q_{0}(f)\leq D(f)\leq n}$

ความซับซ้อนของแบบสอบถามทุกประเภทเหล่านี้มีความสัมพันธ์แบบพหุนาม Blum และ Impagliazzo ^{[ 10 ]} Hartmanis และ Hemachandra ^{[ 11 ]}และ Tardos ^{[ 12 ]}ค้นพบโดยอิสระว่าNoam Nisanพบว่าความซับซ้อนของต้นไม้ตัดสินใจแบบสุ่ม Monte Carlo ก็มีความสัมพันธ์แบบพหุนามกับความซับซ้อนของต้นไม้ตัดสินใจแบบกำหนดเช่นกัน: ^{[ 13 ]} (Nisan ยังแสดงให้เห็นว่า) ความสัมพันธ์ที่แน่นแฟ้นยิ่งขึ้นเป็นที่รู้จักระหว่างแบบจำลอง Monte Carlo และ Las Vegas: [ ^{14 ] ความ}สัมพันธ์นี้เหมาะสมที่สุดจนถึงปัจจัยพหุลอการิทึม^{[ 15 ]}สำหรับความซับซ้อนของต้นไม้ตัดสินใจควอนตัมและขอบเขตนี้แน่น^{[ 16 ] [ 15 ]} Midrijanis แสดงให้เห็นว่า[ ^{17 ] [ 18 ] ปรับปรุง}ขอบเขตควอติกเนื่องจาก Beals et al. ^{[ 9 ]}${\displaystyle D(f)\leq R_{0}(f)^{2}}$${\displaystyle D(f)=O(R_{2}(f)^{3})}$${\displaystyle D(f)=O(R_{1}(f)^{2})}$${\displaystyle R_{0}(f)=O(R_{2}(f)^{2}\log R_{2}(f))}$${\displaystyle D(f)=O(Q_{2}(f)^{4})}$${\displaystyle D(f)=O(Q_{0}(f)^{3})}$

ความสัมพันธ์พหุนามเหล่านี้ใช้ได้เฉพาะกับฟังก์ชันบูลีนทั้งหมด เท่านั้น สำหรับ ฟังก์ชันบูลีนบางส่วนที่มีโดเมนเป็นเซตย่อยของการแยกแบบเลขชี้กำลังระหว่างและนั้นเป็นไปได้ ตัวอย่างแรกของปัญหาดังกล่าวถูกค้นพบโดยDeutsch และ Jozsa ${\displaystyle \{0,1\}^{n}}$${\displaystyle Q_{0}(f)}$${\displaystyle D(f)}$

สำหรับฟังก์ชันบูลีน ความไวของฟังก์ชันถูกกำหนดให้เป็นความไวสูงสุดของฟังก์ชันตลอดช่วงทั้งหมดโดยที่ความไวของฟังก์ชันที่จุดคือจำนวนการเปลี่ยนแปลงบิตเดียวในฟังก์ชันที่ทำให้ค่าของฟังก์ชันเปลี่ยนแปลงความไวมีความสัมพันธ์กับแนวคิดของอิทธิพลโดยรวมจากการวิเคราะห์ฟังก์ชันบูลีนซึ่งเท่ากับ ความไว เฉลี่ยตลอดช่วงทั้งหมด ${\displaystyle f:\{0,1\}^{n}\to \{0,1\}}$${\displaystyle f}$${\displaystyle f}$${\displaystyle x}$${\displaystyle f}$${\displaystyle x}$${\displaystyle x}$${\displaystyle f(x)}$${\displaystyle x}$

ข้อสันนิษฐานเรื่องความไว (sensitivity conjecture)คือข้อสันนิษฐานที่ว่าความไวมีความสัมพันธ์แบบพหุนามกับความซับซ้อนของการสอบถาม (query complexity) กล่าวคือ มีเลขชี้กำลังอยู่ค่าหนึ่งที่ทำให้ สำหรับทุกค่าและสามารถแสดงได้ด้วยการอ้างเหตุผลอย่างง่ายว่าดังนั้นข้อสันนิษฐานนี้จึงเกี่ยวข้องกับการหาขอบล่างของความไวโดยเฉพาะ เนื่องจากมาตรวัดความซับซ้อนทั้งหมดที่กล่าวถึงก่อนหน้านี้มีความสัมพันธ์แบบพหุนาม ประเภทของมาตรวัดความซับซ้อนจึงไม่สำคัญ อย่างไรก็ตาม โดยทั่วไปแล้วคำถามนี้มักถูกถามในแง่ของความสัมพันธ์ระหว่างความไวกับความไวของบล็อก ${\displaystyle c,c'}$${\displaystyle f}$${\displaystyle D(f)=O(s(f)^{c})}$${\displaystyle s(f)=O(D(f)^{c'})}$${\displaystyle s(f)\leq D(f)}$

ความไวของบล็อกของซึ่งแสดงด้วยถูกกำหนดให้เป็นความไวของบล็อกสูงสุดของเหนือทั้งหมดความไวของบล็อกของที่คือจำนวนสูงสุดของเซตย่อยที่ไม่ซ้ำกันโดยที่สำหรับเซตย่อยใดๆการพลิกบิตของที่สอดคล้องกับ จะเปลี่ยนค่าของ^{[ 13 ]}${\displaystyle f}$${\displaystyle bs(f)}$${\displaystyle f}$${\displaystyle x}$${\displaystyle f}$${\displaystyle x}$${\displaystyle t}$${\displaystyle S_{1},\ldots ,S_{t}\subseteq [n]}$${\displaystyle S_{i}}$${\displaystyle x}$${\displaystyle S_{i}}$${\displaystyle f(x)}$

ในปี 2019 Hao Huangได้พิสูจน์สมมติฐานความไว โดยแสดงให้เห็นว่า^{[ 19 ] [ 20 ]}${\displaystyle bs(f)=O(s(f)^{4})}$

• การเรียงลำดับแบบเปรียบเทียบ
• แผนผังการตัดสินใจ
• การคาดเดาของอาอันเดอรา–คาร์ป–โรเซนเบิร์ก
• ต้นไม้เชื่อมโยงขั้นต่ำ § ต้นไม้ตัดสินใจ