ในทฤษฎีความซับซ้อนของการคำนวณ P /polyคือกลุ่มความซับซ้อนที่สามารถนิยามได้ทั้งในความซับซ้อนของวงจรและความซับซ้อนที่ไม่สม่ำเสมอเนื่องจากนิยามทั้งสองนั้นเทียบเท่ากัน แนวคิดนี้จึงเชื่อมโยงทั้งสองด้านเข้าด้วยกัน

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

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

ตัวอย่างเช่นการทดสอบความเป็นจำนวนเฉพาะของมิลเลอร์-ราบิน ที่นิยมใช้ สามารถกำหนดเป็น อัลกอริทึม P/polyได้ โดย "คำแนะนำ" คือรายการค่าตัวเลือกที่จะทดสอบ เป็นไปได้ที่จะคำนวณรายการล่วงหน้าได้${\displaystyle O(n)}$ค่าต่างๆ เช่นนั้น จำนวน nบิตประกอบทุกจำนวนจะต้องมีพยานaในรายการ^{[ 3 ]}ตัวอย่างเช่น ในการตรวจสอบความเป็นจำนวนเฉพาะของจำนวน 32 บิตอย่างถูกต้อง ก็เพียงพอที่จะทดสอบ${\displaystyle a\in \{2,7,61\}}$[ ^{4 ] [ 5 ]}การมีอยู่ของรายการสั้นๆ ของพยานผู้สมัครเป็นผลมาจากข้อเท็จจริงที่ว่าสำหรับแต่ละจำนวนประกอบnสามในสี่ของค่าผู้สมัครสามารถตรวจจับได้ว่าn เป็นจำนวนประกอบ จากนี้ การโต้แย้ง ^การนับอย่างง่ายที่คล้ายกับในข้อพิสูจน์ที่ว่า${\displaystyle {\mathsf {BPP}}\subset {\mathsf {P/poly}}}$ด้านล่างแสดงให้เห็นว่ามีรายการค่าผู้สมัครที่เหมาะสมสำหรับขนาดอินพุตทุกขนาด และยิ่งไปกว่านั้น รายการค่าผู้สมัครที่ยาวเพียงพอส่วนใหญ่จะทำงานได้อย่างถูกต้อง แม้ว่าการค้นหารายการที่รับประกันว่าจะทำงานได้อาจมีค่าใช้จ่ายสูง^{[ 3 ]}

P/polyแตกต่างจากคลาสเวลาพหุนามอื่นๆ เช่นPหรือBPPตรงที่โดยทั่วไปแล้วไม่ถือว่าเป็นคลาสที่ใช้งานได้จริงสำหรับการคำนวณ อันที่จริง มันประกอบด้วยภาษาเอกภาคที่ ไม่สามารถตัดสินได้ทุก ภาษา ซึ่งไม่มีภาษาใดที่คอมพิวเตอร์จริงสามารถแก้ได้โดยทั่วไป ในทางกลับกัน หากความยาวของอินพุตถูกจำกัดด้วยจำนวนที่ค่อนข้างน้อยและสตริงคำแนะนำสั้น มันสามารถใช้เพื่อจำลองอัลกอริทึมที่ใช้งานได้จริง โดยมีขั้นตอนการประมวลผลล่วงหน้าที่มีค่าใช้จ่ายสูงและขั้นตอนการประมวลผลที่รวดเร็วแยกต่างหาก ดังเช่นในตัวอย่างของ Miller–Rabin

ระดับความซับซ้อนP/polyสามารถกำหนดได้ในแง่ของขนาดดังนี้:

${\displaystyle {\mathsf {P/poly}}=\bigcup _{c\in \mathbb {N} }{\mathsf {SIZE}}(n^{c}),}$

ที่ไหน${\displaystyle {\mathsf {SIZE}}(n^{c})}$คือชุดของปัญหาการตัดสินใจที่สามารถแก้ไขได้โดยตระกูลวงจรที่มีไม่เกิน${\displaystyle n^{c}}$ประตูบนอินพุตขนาด${\displaystyle n}$.

หรืออีกทางเลือกหนึ่ง${\displaystyle {\mathsf {P/poly}}}$สามารถนิยามได้โดยใช้เครื่องจักรทัวริงที่ "รับคำแนะนำ" เครื่องจักรดังกล่าวจะมีสตริงคำแนะนำ สำหรับแต่ละ n${\displaystyle \alpha _{n}}$ซึ่งสามารถนำมาใช้ในการคำนวณได้เมื่อใดก็ตามที่อินพุตมีขนาดnเพื่อช่วยให้เห็นภาพความเท่าเทียมกันนี้ ลองจินตนาการว่าคำแนะนำสำหรับแต่ละnคือคำอธิบายของวงจรบูลีนที่มี อินพุต nตัว และเครื่องจักรทัวริงสำหรับภาษานั้นเพียงแค่ประเมินวงจรบูลีนที่กำหนดบนอินพุตที่มีความยาวnเท่านั้น

อนุญาต${\displaystyle T,a:\mathbb {N} \rightarrow \mathbb {N} }$เป็นฟังก์ชัน กลุ่มของภาษาที่ตัดสินได้โดยเครื่องจักรทัวริง เวลา T(n) ที่มี${\displaystyle a(n)}$คำแนะนำ ซึ่งหมายถึง${\displaystyle {\mathsf {DTIME}}(T(n))/a(n)}$ประกอบด้วยทุกภาษาLซึ่งมีลำดับอยู่${\displaystyle \{\alpha _{n}\}_{n\in \mathbb {N} }}$ของสตริงที่มี${\displaystyle \alpha _{n}\in \{0,1\}^{a(n)}}$และ TM Mที่น่าพอใจ

${\displaystyle M(x,\alpha _{n})=1\Leftrightarrow x\in L}$

สำหรับทุกๆ${\displaystyle x\in \{0,1\}^{n}}$โดยที่เมื่อป้อนข้อมูลเข้าไป${\displaystyle (x,\alpha _{n})}$เครื่องจักรMทำงานได้นานที่สุด${\displaystyle O(T(n))}$ขั้นตอน^{[ 6 ]}

P/polyเป็นคลาสที่สำคัญด้วยเหตุผลหลายประการ สำหรับวิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎี มีคุณสมบัติสำคัญหลายประการที่ขึ้นอยู่กับP/poly ดังนี้ :

• ถ้าNP ⊆ P/polyแล้วPH ( ลำดับชั้นพหุนาม ) จะยุบตัวลงเหลือ${\displaystyle \Sigma _{2}^{\mathsf {P}}}$ผลลัพธ์นี้คือทฤษฎีบท Karp–Liptonยิ่งไปกว่านั้น NP ⊆ P/polyบ่งชี้ว่าAM = MA ^{[ 7 ]}
• ถ้าPSPACE ⊆ P/polyแล้ว${\displaystyle {\mathsf {PSPACE}}=\Sigma _{2}^{\mathsf {P}}\cap \Pi _{2}^{\mathsf {P}}}$แม้ว่าPSPACEจะเท่ากับMAก็ตาม

บทพิสูจน์: พิจารณาภาษาLจากPSPACEเป็นที่ทราบกันว่ามีระบบพิสูจน์แบบโต้ตอบสำหรับL อยู่ โดยที่การกระทำของผู้พิสูจน์สามารถดำเนินการโดย เครื่อง PSPACEได้ ตามสมมติฐาน ผู้พิสูจน์สามารถแทนที่ด้วยวงจรขนาดพหุนามได้ ดังนั้นL จึง มี โปรโตคอล MA : เมอร์ลินส่งวงจรเป็นหลักฐาน และอาร์เธอร์สามารถจำลอง โปรโตคอล IPได้ด้วยตนเองโดยไม่ต้องอาศัยความช่วยเหลือเพิ่มเติมใดๆ

• ถ้าP ^#P ⊆ P/polyแล้วP ^#P = MA ^{[ 8} ] การพิสูจน์คล้ายกับข้างต้น โดยอาศัยโปรโตคอลแบบโต้ตอบสำหรับความถาวรและ^ความสมบูรณ์ #P ของความถาวร
• ถ้าEXPTIME ⊆ P/polyแล้ว${\displaystyle {\mathsf {EXPTIME}}=\Sigma _{2}^{\mathsf {P}}\cap \Pi _{2}^{\mathsf {P}}}$(ทฤษฎีบทของเมเยอร์) แม้ว่าEXPTIME = MAก็ตาม
• ถ้าNEXPTIME ⊆ P/polyแล้วNEXPTIME = EXPTIMEแม้ว่าNEXPTIME = MAก็ตาม ในทางกลับกัน ถ้าNEXPTIME = MAแสดงว่าNEXPTIME ⊆ P/poly ^{[ 9 ]}
• ถ้าEXP ^NP ⊆ P/polyแล้ว${\displaystyle {\mathsf {EXP^{NP}}}=\Sigma _{2}^{\mathsf {P}}\cap \Pi _{2}^{\mathsf {P}}}$(บูร์แมน, โฮเมอร์) ^{[ 10 ]}
• เป็นที่ทราบกันว่าMA ซึ่งเป็นรูปแบบเลขชี้กำลังของMAนั้นไม่มีอยู่ในP/ poly

บทพิสูจน์: ถ้าMA ⊆ P/polyแล้วPSPACE = MA (ดูด้านบน) โดยการเติมช่องว่าง EXPSPACE = MA ดังนั้นEXPSPACE ⊆ P/poly แต่สามารถพิสูจน์ได้ ว่าไม่ถูกต้องโดยใช้การหาค่าเฉพาะของเมทริกซ์ทแยงมุม

• ขอบเขตที่เป็นที่รู้จักดีที่สุดสำหรับปัญหาผลรวมรากที่สองอยู่ในระดับที่สี่ของลำดับชั้นการนับ และเป็นปัญหาที่ยังไม่ได้รับการแก้ไขว่ามีความซับซ้อนที่ดีกว่านี้เป็นไปได้หรือไม่ แต่เวอร์ชันเอกภาคของปัญหานี้อยู่ในP/ poly ^{[ 11 ]}

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

P/polyยังถูกนำไปใช้ในสาขาการเข้ารหัสลับด้วยความปลอดภัยมักถูกนิยามว่า 'ป้องกัน' จากผู้โจมตี แบบ P/polyนอกจากจะรวมถึงแบบจำลองการคำนวณที่ใช้งานได้จริงส่วนใหญ่ เช่นBPPแล้ว ยังยอมรับความเป็นไปได้ที่ผู้โจมตีสามารถทำการคำนวณล่วงหน้าอย่างหนักสำหรับข้อมูลป้อนเข้าที่มีความยาวไม่เกินระดับหนึ่ง เช่น ในการสร้างตารางเรนโบว์

แม้ว่าภาษาทั้งหมดในP/polyจะ ไม่ใช่ ภาษาแบบเบาบางแต่ก็มีการลดทอนทัวริงแบบพหุนามจากภาษาใดๆ ในP/polyไปยังภาษาแบบเบาบาง^{[ 12 ]}

ทฤษฎีบทของ Adleman ระบุว่าBPP ⊆ P/polyโดยที่BPPคือเซตของปัญหาที่สามารถแก้ไขได้ด้วยอัลกอริทึมแบบสุ่มที่มีข้อผิดพลาดสองด้านในเวลาพหุนาม ผลลัพธ์ที่อ่อนกว่าได้รับการพิสูจน์ครั้งแรกโดยLeonard Adlemanกล่าวคือRP ⊆ P/poly [ ^{13 ] และ}ผลลัพธ์นี้ได้รับการขยายไปสู่​​BPP ⊆ P/polyโดยBennettและ Gill ^{[ 14 ]} รูปแบบต่างๆ ของทฤษฎีบทแสดงให้เห็นว่าBPLอยู่ในL/polyและAMอยู่ในNP/ poly