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

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

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

ประสิทธิภาพโดยเฉลี่ยของอัลกอริทึมได้รับการศึกษามาตั้งแต่มีการพัฒนาแนวคิดสมัยใหม่เกี่ยวกับประสิทธิภาพการคำนวณในช่วงทศวรรษ 1950 งานเริ่มต้นส่วนใหญ่มุ่งเน้นไปที่ปัญหาที่ทราบอัลกอริทึมเวลาพหุนามในกรณีที่เลวร้ายที่สุดอยู่แล้ว^{[ 3 ]}ในปี 1973 Donald Knuth ^{[ 4 ]}ได้ตีพิมพ์เล่มที่ 3 ของArt of Computer Programmingซึ่งสำรวจประสิทธิภาพโดยเฉลี่ยของอัลกอริทึมสำหรับปัญหาที่สามารถแก้ไขได้ในเวลาพหุนามในกรณีที่เลวร้ายที่สุดอย่างกว้างขวาง เช่น การเรียงลำดับและการหาค่ามัธยฐาน

โดยทั่วไปแล้ว อัลกอริทึมที่มีประสิทธิภาพสำหรับ ปัญหา NP -completeจะมีลักษณะเป็นอัลกอริทึมที่ทำงานได้ในเวลาพหุนามสำหรับอินพุตทั้งหมด ซึ่งเทียบเท่ากับการต้องการความซับซ้อนในกรณีที่เลวร้ายที่สุดที่มีประสิทธิภาพ อย่างไรก็ตาม อัลกอริทึมที่ไม่มีประสิทธิภาพสำหรับอินพุตจำนวน "น้อย" อาจยังคงมีประสิทธิภาพสำหรับอินพุต "ส่วนใหญ่" ที่เกิดขึ้นในทางปฏิบัติ ดังนั้นจึงเป็นที่พึงปรารถนาที่จะศึกษาคุณสมบัติของอัลกอริทึมเหล่านี้ในกรณีที่ความซับซ้อนในกรณีเฉลี่ยอาจแตกต่างจากความซับซ้อนในกรณีที่เลวร้ายที่สุด และหาวิธีเชื่อมโยงทั้งสองเข้าด้วยกัน

แนวคิดพื้นฐานของความซับซ้อนในกรณีเฉลี่ยได้รับการพัฒนาโดยLeonid Levinในปี 1986 เมื่อเขาตีพิมพ์เอกสารหนึ่งหน้า^{[ 5 ]}ซึ่งกำหนดความซับซ้อนและความสมบูรณ์ในกรณีเฉลี่ย พร้อมทั้งยกตัวอย่างปัญหาที่สมบูรณ์สำหรับdistNP ซึ่งเป็นอนาล็อกของ NPใน กรณีเฉลี่ย

งานแรกคือการกำหนดความหมายของอัลกอริทึมที่มีประสิทธิภาพ "โดยเฉลี่ย" อย่างแม่นยำ ความพยายามเบื้องต้นอาจกำหนดอัลกอริทึมที่มีประสิทธิภาพโดยเฉลี่ยว่าเป็นอัลกอริทึมที่ทำงานในเวลาพหุนามที่คาดหวังได้สำหรับอินพุตที่เป็นไปได้ทั้งหมด คำจำกัดความดังกล่าวมีข้อบกพร่องหลายประการ โดยเฉพาะอย่างยิ่ง มันไม่ทนทานต่อการเปลี่ยนแปลงในแบบจำลองการคำนวณ ตัวอย่างเช่น สมมติว่าอัลกอริทึมAทำงานในเวลาt _A ( x )สำหรับอินพุตxและอัลกอริทึมBทำงานในเวลาt _A ( x ) ²สำหรับอินพุตxนั่นคือBช้ากว่าAในเชิงกำลังสอง โดยสัญชาตญาณ คำจำกัดความใด ๆ ของประสิทธิภาพโดยเฉลี่ยควรจับแนวคิดที่ว่าAมีประสิทธิภาพโดยเฉลี่ยก็ต่อเมื่อBมีประสิทธิภาพโดยเฉลี่ย อย่างไรก็ตาม สมมติว่าอินพุตถูกสุ่มเลือกจากการกระจายแบบเอกรูปของสตริงที่มีความยาวnและAทำงานในเวลาn ² สำหรับ อินพุตทั้งหมด ยกเว้นสตริง1 ⁿซึ่งAใช้เวลา2 ⁿจากนั้นสามารถตรวจสอบได้อย่างง่ายดายว่าเวลาการทำงานที่คาดหวังของAเป็นแบบพหุนาม แต่เวลาการทำงานที่คาดหวังของBเป็นแบบเลขชี้กำลัง^{[ 3 ]}

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

${\displaystyle \Pr _{x\in _{R}D_{n}}\left[t_{A}(x)\geq t\right]\leq {\frac {p(n)}{t^{\epsilon }}}}$

สำหรับทุกn , t > 0และพหุนามpโดยที่t _A ( x )แทนเวลาการทำงานของอัลกอริทึมAบนอินพุตxและεเป็นค่าคงที่บวก^{[ 6 ]}หรืออีกทางหนึ่ง สามารถเขียนได้ดังนี้

${\displaystyle E_{x\in _{R}D_{n}}\left[{\frac {t_{A}(x)^{\epsilon }}{n}}\right]\leq C}$

สำหรับค่าคงที่Cและ ε บางค่า โดยที่n = | x | ^{[ 7 ]}กล่าวอีกนัยหนึ่ง อัลกอริทึมAมีความซับซ้อนในกรณีเฉลี่ยที่ดี หากหลังจากดำเนินการเป็นเวลาt A ₍ n )ขั้นตอนAสามารถแก้ปัญหาได้ทั้งหมด ยกเว้น a ⁠เอ็น^ซี/( t _A ( n )) ^εเศษส่วนของอินพุตที่มีความยาว nสำหรับ ε บาง ตัว c > 0 ^{[ 3 ]}

ขั้นตอนต่อไปคือการกำหนดอินพุต "เฉลี่ย" สำหรับปัญหาเฉพาะ ซึ่งทำได้โดยการเชื่อมโยงอินพุตของแต่ละปัญหากับการกระจายความน่าจะเป็นเฉพาะ นั่นคือ ปัญหา "กรณีเฉลี่ย" ประกอบด้วยภาษาLและการกระจายความน่าจะเป็นD ที่เกี่ยวข้อง ซึ่งก่อให้เกิดคู่( L , D ) ^{[ 7 ]}คลาสการกระจายที่พบบ่อยที่สุดสองคลาสที่อนุญาตคือ:

1. การแจกแจงที่คำนวณได้ในเวลาพหุนาม ( P -computable): คือการแจกแจงที่สามารถคำนวณความหนาแน่นสะสมของอินพุตx ใดๆ ได้ กล่าวอย่างเป็นทางการมากขึ้นคือ เมื่อกำหนดการแจกแจงความน่าจะเป็นμและสตริงx ∈ {0, 1} ^{n แล้ว}สามารถคำนวณค่าได้ในเวลาพหุนาม ซึ่งหมายความว่าPr[ x ]ก็สามารถคำนวณได้ในเวลาพหุนามเช่นกัน${\displaystyle \mu (x)=\sum \limits _{y\in \{0,1\}^{n}:y\leq x}\Pr[y]}$
2. การแจกแจงที่สามารถสุ่มตัวอย่างได้ในเวลาพหุนาม ( P -samplable): คือการแจกแจงที่สามารถสุ่มตัวอย่างแบบสุ่มได้ในเวลาพหุนาม

สูตรทั้งสองนี้แม้จะคล้ายกัน แต่ก็ไม่เท่ากัน หากการแจกแจง สามารถคำนวณได้ ด้วยPก็จะ สามารถสุ่มตัวอย่างได้ด้วย P เช่นกัน แต่ในทางกลับกันจะไม่เป็นจริงหากP ≠ P ^{#P [ 7 ]}

ปัญหาการกระจาย( L , D )อยู่ในคลาสความซับซ้อนAvgPหากมีอัลกอริทึมกรณีเฉลี่ยที่มีประสิทธิภาพสำหรับLตามที่กำหนดไว้ข้างต้น บางครั้งคลาสAvgPเรียกว่าdistPในเอกสาร^{[ 7 ]}

ปัญหาการกระจาย( L , D )อยู่ในคลาสความซับซ้อนdistNPถ้าLอยู่ในNPและDสามารถ คำนวณได้ แบบ Pเมื่อLอยู่ในNPและDสามารถสุ่มตัวอย่างได้แบบ^P ( L , D )อยู่ในsampNP [ ^{7 ]}

AvgPและdistNPร่วมกันกำหนดอนาล็อกกรณีเฉลี่ยของPและNPตามลำดับ^{[ 7 ]}

ให้( L , D )และ( L′ , D′ )เป็นปัญหาการแจกแจงสองปัญหา กรณีเฉลี่ยของ( L , D ) จะลดลงเหลือ ( L′ , D′ ) (เขียนว่า( L , D ) ≤ _AvgP ( L′ , D′ ) ) ถ้ามีฟังก์ชันfที่สำหรับทุกnบนอินพุตxสามารถคำนวณได้ในเวลาที่เป็นพหุนามของnและ

1. (ความถูกต้อง) x ∈ Lก็ต่อเมื่อf ( x ) ∈ L′
2. ( การครอบงำ) มีพหุนามpและm อยู่ ซึ่งสำหรับทุกnและy${\displaystyle \sum \limits _{x:f(x)=y}D_{n}(x)\leq p(n)D'_{m(n)}(y)}$

เงื่อนไขการครอบงำบังคับใช้แนวคิดที่ว่า หากปัญหา( L , D )ยากโดยเฉลี่ยแล้ว( L′ , D′ )ก็จะยากโดยเฉลี่ยเช่นกัน ตามสัญชาตญาณ การลดรูปควรให้วิธีการแก้ปัญหาตัวอย่างxของปัญหาLโดยการคำนวณf ( x )และป้อนเอาต์พุตไปยังอัลกอริทึมที่แก้ปัญหาL'หากไม่มีเงื่อนไขการครอบงำ สิ่งนี้อาจเป็นไปไม่ได้ เนื่องจากอัลกอริทึมที่แก้ปัญหาLในเวลาพหุนามโดยเฉลี่ยอาจใช้เวลามากกว่าพหุนามสำหรับอินพุตจำนวนน้อย แต่fอาจแมปอินพุตเหล่านี้ไปยังชุดD' ที่ใหญ่กว่ามาก ดังนั้นอัลกอริทึมA' จึง ไม่ทำงานในเวลาพหุนามโดยเฉลี่ยอีกต่อไป เงื่อนไขการครอบงำอนุญาตให้สตริงดังกล่าวเกิดขึ้นในเวลาพหุนามได้บ่อยเท่าในD'เท่านั้น^{[ 6 ]}

ปัญหาที่เทียบเคียงได้กับ NP -completeness ในกรณีเฉลี่ยคือdistNP -completeness ปัญหาการกระจาย( L′ , D′ )ถือว่าdistNP -complete ถ้า( L′ , D′ ⁾อยู่ในdistNPและสำหรับทุก( L , D )ในdistNP , ( L , D )สามารถลดรูปได้ในกรณีเฉลี่ยเป็น( L′ , D′ ) [ ^{7 ]}

ตัวอย่างหนึ่งของ ปัญหา distNP -complete คือปัญหาการหยุดทำงาน แบบมีขอบเขต (Bounded Halting Problem ) ( BH , D ) (สำหรับD ใดๆ ที่คำนวณได้ด้วยP ) ซึ่งกำหนดไว้ดังนี้:

${\displaystyle BH=\{(M,x,1^{t}):M{\text{ เป็นเครื่องจักรทัวริงแบบไม่กำหนดที่ยอมรับ }}x{\text{ ใน}}\leq t{\text{ ขั้นตอน}}\}}$^{[ 7 ]}

ในบทความต้นฉบับ Levin ได้แสดงตัวอย่างของปัญหาการปูพื้นแบบกระจายซึ่งเป็นNP -complete ในกรณีเฉลี่ย ^{[ 5 ]}การสำรวจ ปัญหา distNP -complete ที่รู้จักมีให้ดูทางออนไลน์^{[ 6 ]}

หนึ่งในด้านการวิจัยที่กำลังดำเนินการอยู่คือการค้นหา ปัญหา distNP -complete ใหม่ อย่างไรก็ตาม การค้นหาปัญหาดังกล่าวอาจซับซ้อนเนื่องจากผลลัพธ์ของ Gurevich ซึ่งแสดงให้เห็นว่าปัญหาการกระจายใดๆ ที่มีการกระจายแบบราบเรียบไม่สามารถเป็นdistNP -complete ได้เว้นแต่EXP = NEXP [ ^{8 ] (}การกระจายแบบราบเรียบμ คือการกระจายที่มี ε > 0อยู่ซึ่งสำหรับx ใดๆ μ ( x ) ≤ 2 ^{−| x | ε} ) ผลลัพธ์ของ Livne แสดงให้เห็นว่า ปัญหา NP -complete ตามธรรมชาติทั้งหมด มีเวอร์ชันDistNP -complete ^{[ 9 ]}อย่างไรก็ตาม เป้าหมายของการค้นหาปัญหาการกระจายตามธรรมชาติที่เป็นDistNP - complete ยังไม่บรรลุผล^{[ 10 ]}

ดังที่กล่าวไว้ข้างต้น งานวิจัยในช่วงแรกๆ ที่เกี่ยวข้องกับความซับซ้อนในกรณีเฉลี่ยส่วนใหญ่มุ่งเน้นไปที่ปัญหาที่มีอัลกอริทึมเวลาพหุนามอยู่แล้ว เช่น การเรียงลำดับ ตัวอย่างเช่น อัลกอริทึมการเรียงลำดับจำนวนมากที่ใช้ความสุ่ม เช่นQuicksort มีเวลาทำงานในกรณีที่เลวร้ายที่สุดคือ O(n²) แต่มีเวลาทำงาน^ในกรณีเฉลี่ยคือO( n log( n ))โดยที่nคือความยาวของข้อมูลที่จะเรียงลำดับ^{[ 2 ]}

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

ดังนั้น แผนการเข้ารหัสลับที่ปลอดภัยทั้งหมดจึงอาศัยการมีอยู่ของฟังก์ชันทางเดียว [ ^{3 ] แม้ว่า}การมีอยู่ของฟังก์ชันทางเดียวยังคงเป็นปัญหาที่ยังเปิดอยู่แต่ฟังก์ชันทางเดียวที่เป็นไปได้จำนวนมากนั้นอิงจากปัญหาที่ยาก เช่นการแยกตัวประกอบจำนวนเต็มหรือการคำนวณลอการิทึมแบบไม่ต่อเนื่องโปรดทราบว่าไม่เป็นที่พึงปรารถนาที่ฟังก์ชันที่เป็นไปได้จะเป็นNP -complete เนื่องจากสิ่งนี้จะรับประกันได้เพียงว่าอาจไม่มีอัลกอริทึมที่มีประสิทธิภาพในการแก้ปัญหาในกรณีที่เลวร้ายที่สุด สิ่งที่เราต้องการจริงๆ คือการรับประกันว่าไม่มีอัลกอริทึมที่มีประสิทธิภาพใดๆ ที่สามารถแก้ปัญหาได้กับอินพุตแบบสุ่ม (เช่น กรณีเฉลี่ย) ในความเป็นจริง ทั้งปัญหาการแยกตัวประกอบจำนวนเต็มและลอการิทึมแบบไม่ต่อเนื่องอยู่ในNP ∩ coNPดังนั้นจึงไม่เชื่อว่าเป็นNP -complete ^{[ 7 ]}ข้อเท็จจริงที่ว่าการเข้ารหัสลับทั้งหมดขึ้นอยู่กับการมีอยู่ของปัญหาที่แก้ไม่ได้ในกรณีเฉลี่ยในNPเป็นหนึ่งในแรงจูงใจหลักสำหรับการศึกษาความซับซ้อนในกรณีเฉลี่ย

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

ในปี พ.ศ. 2533 Impagliazzo และ Levin แสดงให้เห็นว่าหากมีอัลกอริทึมกรณีเฉลี่ยที่มีประสิทธิภาพสำหรับ ปัญหา distNPที่สมบูรณ์ภายใต้การแจกแจงแบบเอกรูป ก็จะมีอัลกอริทึมกรณีเฉลี่ยสำหรับทุกปัญหาในNPภายใต้การแจกแจงแบบสุ่มตัวอย่างในเวลาพหุนามใดๆ^{[ 13 ]}การนำทฤษฎีนี้ไปใช้กับปัญหาการแจกแจงตามธรรมชาติยังคงเป็นคำถามเปิดที่สำคัญ^{[ 3 ]}

ในปี พ.ศ. 2535 Ben-David และคณะได้แสดงให้เห็นว่าหากภาษาทั้งหมดในdistNPมีอัลกอริธึมการตัดสินใจที่ดีโดยเฉลี่ย ภาษาเหล่านั้นก็จะมีอัลกอริธึมการค้นหาที่ดีโดยเฉลี่ยเช่นกัน ยิ่งไปกว่านั้น พวกเขายังแสดงให้เห็นว่าข้อสรุปนี้ยังคงใช้ได้ภายใต้สมมติฐานที่อ่อนกว่า: หากทุกภาษาในNPง่ายโดยเฉลี่ยสำหรับอัลกอริธึมการตัดสินใจโดยสัมพันธ์กับการกระจายแบบสม่ำเสมอ ภาษาเหล่านั้นก็จะง่ายโดยเฉลี่ยสำหรับอัลกอริธึมการค้นหาโดยสัมพันธ์กับการกระจายแบบสม่ำเสมอเช่นกัน^{[ 14 ]}ดังนั้น ฟังก์ชันทางเดียวของการเข้ารหัสลับจึงสามารถมีอยู่ได้ก็ต่อเมื่อมี ปัญหา distNPบนการกระจายแบบสม่ำเสมอที่ยากโดยเฉลี่ยสำหรับอัลกอริธึมการตัดสินใจ

ในปี 1993 Feigenbaum และ Fortnow แสดงให้เห็นว่าไม่สามารถพิสูจน์ได้ภายใต้การลดแบบสุ่มที่ไม่ปรับตัวว่าการมีอยู่ของอัลกอริทึมที่ดีโดยเฉลี่ยสำหรับ ปัญหา distNP -complete ภายใต้การแจกแจงแบบเอกรูปหมายถึงการมีอยู่ของอัลกอริทึมที่มีประสิทธิภาพในกรณีที่เลวร้ายที่สุดสำหรับปัญหาทั้งหมดในNP [ ^{15 ] ใน}ปี 2003 Bogdanov และ Trevisan ได้ขยายผลลัพธ์นี้ไปยังการลดแบบไม่ปรับตัวใดๆ^{[ 16 ]}ผลลัพธ์เหล่านี้แสดงให้เห็นว่าไม่น่าจะสามารถสร้างความสัมพันธ์ใดๆ ระหว่างความซับซ้อนในกรณีเฉลี่ยและความซับซ้อนในกรณีที่เลวร้ายที่สุดผ่านการลดได้^{[ 3 ]}

• การวิเคราะห์เชิงความน่าจะเป็นของอัลกอริทึม
• ปัญหา NP-complete
• ความซับซ้อนในกรณีที่เลวร้ายที่สุด
• การวิเคราะห์แบบตัดจำหน่าย
• กรณีที่ดีที่สุด กรณีที่แย่ที่สุด และกรณีเฉลี่ย

การนำเสนอเชิงการสอน:

• Impagliazzo, R. (1995). "มุมมองส่วนตัวเกี่ยวกับความซับซ้อนในกรณีเฉลี่ย". รายงานการประชุม Structure in Complexity Theory การประชุมประจำปีครั้งที่ 10 ของ IEEE . สำนักพิมพ์ IEEE Comput. Soc. Press. หน้า  134–147 . doi : 10.1109/SCT.1995.514853 . ISBN 978-0-8186-7052-7.
• Wang, Jie (1997). "ทฤษฎีความซับซ้อนของการคำนวณกรณีเฉลี่ย". ใน Hemaspaandra, Lane A.; Selman, Alan L. (บรรณาธิการ). ทฤษฎีความซับซ้อน: ย้อนหลัง II (PDF) . เล่ม 2. Springer Science & Business Media. หน้า  295–328 .
• Goldreich, Oded (2011), "ความซับซ้อนของกรณีเฉลี่ย ทบทวนอีกครั้ง" (PDF)ใน Goldreich, Oded (บรรณาธิการ), การศึกษาเกี่ยวกับความซับซ้อนและการเข้ารหัสลับ เบ็ดเตล็ดเกี่ยวกับปฏิสัมพันธ์ระหว่างความสุ่มและการคำนวณ บันทึกการบรรยายในวิทยาศาสตร์คอมพิวเตอร์ เล่มที่ 6650 เบอร์ลิน ไฮเดล เบิร์ก : Springer Berlin Heidelberg หน้า  422–450 doi : 10.1007/978-3-642-22670-0_29 ISBN 978-3-642-22669-4
• Arora, Sanjeev; Barak, Boaz (2009). "18. ความซับซ้อนของกรณีเฉลี่ย: ทฤษฎีของ Levin" ความซับซ้อนในการคำนวณ: แนวทางสมัยใหม่เคมบริดจ์; นิวยอร์ก: สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์

งานวิจัยที่เกี่ยวข้องกับความซับซ้อนของกรณีโดยเฉลี่ยประกอบด้วยผลงานดังต่อไปนี้:

• Levin, Leonid (1986), "ปัญหาที่สมบูรณ์ในกรณีเฉลี่ย", SIAM Journal on Computing , 15 (1): 285– 286, doi : 10.1137/0215020
• Franco, John (1986), "เกี่ยวกับประสิทธิภาพเชิงความน่าจะเป็นของอัลกอริทึมสำหรับปัญหาความพึงพอใจ", Information Processing Letters , 23 (2): 103– 106, doi : 10.1016/0020-0190(86)90051-7...
• ฟลาโจเลต, ฟิลิปป์ ; Vitter, JS (สิงหาคม 1987), การวิเคราะห์กรณีเฉลี่ยของอัลกอริทึมและโครงสร้างข้อมูล , เทคโนโลยี รายงาน, Institut National de Recherche en Informatique et en Automatique, BP 105-78153 Le Chesnay Cedex France.
• Gurevich, Yuri ; Shelah, Saharon (1987), "เวลาการคำนวณที่คาดหวังสำหรับปัญหาเส้นทางแฮมิลโทเนียน ", SIAM Journal on Computing , 16 (3): 486– 502, CiteSeerX  10.1.1.359.8982 , doi : 10.1137/0216034.
• เบน-เดวิด, ชาย; ชอร์, เบนนี่ ; โกลด์ไรช์, โอเดด ; ลูบี้, ไมเคิล (1989), "เกี่ยวกับทฤษฎีความซับซ้อนของกรณีเฉลี่ย", รายงานการประชุมสัมมนาประจำปีครั้งที่ 21 ว่าด้วยทฤษฎีการคำนวณ , สมาคมเครื่องจักรคำนวณ , หน้า  204–216.
• Gurevich, Yuri (1991), "ความสมบูรณ์ของกรณีโดยเฉลี่ย", Journal of Computer and System Sciences , 42 (3): 346– 398, doi : 10.1016/0022-0000(91)90007-R , hdl : 2027.42/29307ดูฉบับร่างปี 1989 เพิ่มเติม ด้วย
• Selman, B.; Mitchell, D.; Levesque, H. ( 1992), "การแจกแจงปัญหา SAT ที่ยากและง่าย", รายงานการประชุมวิชาการระดับชาติครั้งที่ 10 ด้านปัญญาประดิษฐ์ , หน้า  459–465.
• Schuler, Rainer; Yamakami, Tomoyuki (1992), "ความซับซ้อนของกรณีเฉลี่ยเชิงโครงสร้าง", Proc. Foundations of Software Technology and Theoretical Computer Science , Lecture Notes in Computer Science, vol. 652, Springer-Verlag, pp  . 128–139.
• Reischuk, Rüdiger; Schindelhauer, Christian (1993), "ความซับซ้อนของกรณีเฉลี่ยที่แม่นยำ", Proc . 10th Annual Symposium on Theoretical Aspects of Computer Science , หน้า  650–661.
• Venkatesan, R.; Rajagopalan, S. (1992), "ความยากลำบากในการ แก้ปัญหาเมทริกซ์และไดโอแฟนไทน์ในกรณีเฉลี่ย", รายงานการประชุมสัมมนาประจำปีครั้งที่ 24 ว่าด้วยทฤษฎีการคำนวณ , สมาคมเครื่องจักรคำนวณ , หน้า  632–642.
• Cox, Jim; Ericson, Lars; Mishra, Bud (1995), ความซับซ้อนของกรณีโดยเฉลี่ยของตรรกะแบบหลายระดับ (PDF) , รายงานทางเทคนิค TR1995-711, ภาควิชาวิทยาการคอมพิวเตอร์ มหาวิทยาลัยนิวยอร์ก.