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

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

การขยายขอบของเซต${\displaystyle X}$จำนวนจุดยอดในกราฟ${\displaystyle G}$ถูกกำหนดให้เป็น$${\displaystyle {\frac {|\partial X|}{|X|}},}$$ โดยที่เส้นแนวตั้งแสดงถึงจำนวนสมาชิกของเซตและ${\displaystyle \partial X}$หมายถึงเซตของขอบที่มีจุดปลายหนึ่งอยู่ใน${\displaystyle X}$และจุดปลายอีกจุดหนึ่งที่เป็นส่วนเติมเต็ม^[ก]ตัวเลขนี้อาจต่ำถึงศูนย์ได้ เมื่อ${\displaystyle X}$เป็นส่วนประกอบที่เชื่อมต่อกันของกราฟ เนื่องจากในกรณีนี้ไม่มีเส้นเชื่อมระหว่างกัน${\displaystyle X}$ไปยังส่วนอื่นๆ ของกราฟ กราฟนั้นเรียกว่ากราฟปกติหรือ กราฟทั่วไป${\displaystyle d}$-ปกติ เมื่อทุกจุดยอดเชื่อมต่อกับจำนวนขอบเท่ากัน${\displaystyle d}$ระดับ ของ กราฟสำหรับ${\displaystyle d}$-กราฟปกติ การขยายขอบสูงสุดที่เป็นไปได้คือ${\displaystyle d}$การขยายนี้เกิดขึ้นได้จากเซตย่อยใดๆ${\displaystyle X}$ซึ่งก่อให้เกิดเซตอิสระเช่น ในกรณีนี้คือขอบทั้งหมดที่สัมผัสกับจุดยอดใน${\displaystyle X}$เป็นของ${\displaystyle \partial X}$[ ^{1 ] [ 2 ]​}

การขยายขอบของกราฟด้วย${\displaystyle n}$จุดยอดถูกกำหนดให้เป็นการขยายขอบขั้นต่ำในกลุ่มย่อยของมัน โดยมีจำนวนจุดยอดไม่เกิน${\displaystyle n/2}$จุดยอด^{[ b ]}ในทางกลับกันการขยายเซตขนาดเล็กถูกกำหนดให้เป็นค่าต่ำสุดเดียวกัน แต่เฉพาะกับเซตย่อยที่เล็กกว่าเท่านั้น ซึ่งมีค่าสูงสุดไม่เกิน${\displaystyle n/\log _{2}n}$จุดยอด โดยทั่วไปแล้ว ตัวขยายเซตขนาดเล็กคือกราฟที่มีการขยายเซตขนาดเล็กขนาดใหญ่^{[ 1 ] [ c ]}

สมมติฐานการขยายเซตขนาดเล็กใช้จำนวนจริง${\displaystyle \varepsilon }$ใช้เป็นพารามิเตอร์เพื่อกำหนดความหมายของการขยายเซตขนาดเล็กของกราฟว่าจะมีขนาดใหญ่หรือเล็ก โดยระบุว่า สำหรับทุกๆ${\displaystyle \varepsilon >0}$การแยกแยะความแตกต่างระหว่างสิ่งเหล่านี้เป็นปัญหา NP-hard${\displaystyle d}$-กราฟ ปกติที่มีการขยายเซตขนาดเล็กอย่างน้อย${\displaystyle (1-\varepsilon )d}$(ตัวขยายขนาดเล็กที่ดี) และ${\displaystyle d}$-กราฟ ปกติที่มีการขยายเซตเล็กน้อยที่สุด${\displaystyle \varepsilon d}$(ห่างไกลจากการเป็นตัวขยายเซตขนาดเล็กมาก) ที่นี่ ระดับ${\displaystyle d}$เป็นตัวแปรที่อาจขึ้นอยู่กับการเลือก${\displaystyle \varepsilon }$ซึ่งแตกต่างจากการใช้งานกราฟขยายหลายๆ อย่างที่ถือว่าดีกรีเป็นค่าคงที่^{[ 1 ] [ c ]}

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

โดยเฉพาะอย่างยิ่ง มีการลดทอนแบบพหุนามเวลาจากการรับรู้ตัวขยายเซตขนาดเล็กไปสู่ปัญหาของการกำหนดค่าโดยประมาณของเกมที่ไม่ซ้ำกัน ซึ่งแสดงให้เห็นว่าสมมติฐานการขยายเซตขนาดเล็กบ่งชี้ถึง ข้อ สันนิษฐานเกมที่ไม่ซ้ำกัน^{[ 1 ] [ 2 ]} Boaz Barakได้เสนอแนะอย่างชัดเจนยิ่งขึ้นว่าสมมติฐานทั้งสองนี้เทียบเท่ากัน^{[ 1 ]}ในความเป็นจริง สมมติฐานการขยายเซตขนาดเล็กเทียบเท่ากับรูปแบบที่จำกัดของข้อสันนิษฐานเกมที่ไม่ซ้ำกัน ซึ่งยืนยันความยากของอินสแตนซ์เกมที่ไม่ซ้ำกันซึ่งกราฟพื้นฐานเป็นตัวขยายเซตขนาดเล็ก^{[ 3 ]}ในทางกลับกัน เป็นไปได้ที่จะแก้ปัญหาอินสแตนซ์เกมที่ไม่ซ้ำกันได้อย่างรวดเร็วซึ่งกราฟเป็นตัวขยายเซตขนาดเล็กที่ "รับรองได้" ในแง่ที่ว่าการขยายของพวกมันสามารถตรวจสอบได้โดยการเพิ่มประสิทธิภาพผลรวมของกำลังสอง^{[ 4 ]}

อีกหนึ่งการประยุกต์ใช้สมมติฐานการขยายเซตขนาดเล็กเกี่ยวข้องกับปัญหาการคำนวณในการประมาณค่า treewidthของกราฟ ซึ่งเป็นพารามิเตอร์เชิงโครงสร้างที่เกี่ยวข้องอย่างใกล้ชิดกับการขยาย สำหรับกราฟที่มี treewidth${\displaystyle w}$อัตราส่วนการประมาณค่าที่ดีที่สุดที่ทราบสำหรับอัลกอริธึมการประมาณค่าแบบพหุนามคือ${\displaystyle O({\sqrt {\log w}})}$[ ^{5 ]}สมมติฐานการขยายเซตขนาดเล็ก หากเป็นจริง แสดงว่าไม่มีอัลกอริทึมการประมาณค่าสำหรับปัญหานี้ที่มีอัตราส่วนการประมาณค่าคงที่^{[ 6 ] นอกจาก}นี้ยังสามารถใช้เพื่อบ่งชี้ถึงความไม่สามารถประมาณค่าได้ของการค้นหากราฟสองส่วนสมบูรณ์ที่มีจำนวนขอบสูงสุด (อาจจำกัดให้มีจำนวนจุดยอดเท่ากันในแต่ละด้านของการแบ่งสองส่วน) ในกราฟขนาดใหญ่^{[ 7 ]}

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

สมมติฐานการขยายเซตขนาดเล็กได้รับการกำหนดและเชื่อมโยงกับสมมติฐานเกมที่ไม่ซ้ำกันโดยPrasad RaghavendraและDavid Steurerในปี 2010 ^{[ 2 ]}ซึ่งเป็นส่วนหนึ่งของผลงานที่ทำให้พวกเขาได้รับรางวัล Michael and Sheila Held Prize ประจำปี 2018 จากNational Academy of Sciences ^{[ 9 ]}

แนวทางหนึ่งในการแก้ปัญหาข้อสมมติฐานการขยายเซตขนาดเล็กคือการค้นหาอัลกอริทึมประมาณค่าสำหรับการขยายขอบของเซตจุดยอดขนาดเล็กที่จะดีพอที่จะแยกแยะกราฟสองประเภทในข้อสมมติฐานได้ ในแง่นี้ การประมาณค่าที่ดีที่สุดที่ทราบสำหรับการขยายขอบของเซตย่อยที่มีขนาดไม่เกิน${\displaystyle n/\log n}$จุดยอดใน${\displaystyle d}$-กราฟปกติ มีอัตราส่วนการประมาณค่าเท่ากับ${\displaystyle O({\sqrt {\log n\log \log n}})}$สิ่งนี้ไม่แข็งแกร่งพอที่จะหักล้างสมมติฐานได้ การทำเช่นนั้นจะต้องค้นหาอัลกอริทึมที่มีอัตราส่วนการประมาณค่าที่จำกัด^{[ 10 ]}