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

คำถาม " เท่ากับ หรือไม่ ?" เป็นคำถามเกี่ยวกับว่าพหุนามสองตัวเหมือนกันหรือไม่ เช่นเดียวกับคำถามทดสอบเอกลักษณ์ของพหุนามใดๆ ก็ตาม คำถามนี้สามารถแปลงเป็นคำถาม "พหุนามที่กำหนดเท่ากับ 0 หรือไม่?" ได้อย่างง่ายดาย ในกรณีนี้เราสามารถถามว่า "เท่ากับหรือไม่?" หากเราได้รับพหุนามเป็นนิพจน์พีชคณิต (แทนที่จะเป็นกล่องดำ) เราสามารถยืนยันความเท่าเทียมกันได้โดยการคูณและการบวกแบบใช้กำลังทั้งหมด แต่ความซับซ้อนของเวลาของวิธีการแบบใช้กำลังทั้งหมดจะเพิ่มขึ้นตาม โดยที่คือจำนวนตัวแปร (ในที่นี้: คือตัวแรกและคือตัวที่สอง) และคือดีกรีของพหุนาม (ในที่นี้) ถ้าและมีค่ามากทั้งคู่จะเพิ่มขึ้นแบบเลขชี้กำลัง^{[ 1 ]}${\displaystyle (x+y)(xy)}$${\displaystyle x^{2}-y^{2}}$${\displaystyle (x+y)(xy)-(x^{2}-y^{2})=0}$${\displaystyle {\tbinom {n+d}{d}}}$${\displaystyle n}$${\displaystyle n=2}$${\displaystyle x}$${\displaystyle y}$${\displaystyle d}$${\displaystyle d=2}$${\displaystyle n}$${\displaystyle d}$${\displaystyle {\tbinom {n+d}{d}}}$

PIT เกี่ยวข้องกับว่าพหุนามนั้นเหมือนกับพหุนามศูนย์หรือไม่ มากกว่าว่าฟังก์ชันที่ดำเนินการโดยพหุนามนั้นจะประเมินค่าเป็นศูนย์เสมอในโดเมนที่กำหนดหรือไม่ ตัวอย่างเช่น ฟิลด์ที่มีสององค์ประกอบGF(2)ประกอบด้วยองค์ประกอบ 0 และ 1 เท่านั้น ใน GF(2) จะประเมินค่าเป็นศูนย์เสมอ แม้ว่าจะเป็นเช่นนั้น PIT ก็ไม่ถือว่าเท่ากับพหุนามศูนย์^{[ 2 ]}${\displaystyle x^{2}-x}$${\displaystyle x^{2}-x}$

การกำหนดความซับซ้อนในการคำนวณที่จำเป็นสำหรับการทดสอบเอกลักษณ์พหุนามเป็นหนึ่งในปัญหาเปิดที่สำคัญที่สุดในสาขาย่อยทางคณิตศาสตร์ที่เรียกว่า "ความซับซ้อนในการคำนวณเชิงพีชคณิต" ^{[ 1 ] [ 3 ]}การศึกษา PIT เป็นองค์ประกอบพื้นฐานสำหรับพื้นที่อื่นๆ ของความซับซ้อนในการคำนวณ เช่น การพิสูจน์ว่าIP = PSPACE ^{[ 1 ] [ 4 ]}นอกจากนี้ PIT ยังมีการประยุกต์ใช้กับเมทริกซ์ Tutteและการทดสอบความเป็นจำนวนเฉพาะซึ่งเทคนิค PIT นำไปสู่การทดสอบความเป็นจำนวนเฉพาะ AKS ซึ่งเป็นอัลกอริทึม เวลาพหุนามเชิง กำหนดตัวแรก (แม้ว่า จะใช้งานจริงไม่ได้) สำหรับการทดสอบความเป็นจำนวนเฉพาะ^{[ 1 ]}

กำหนดวงจรเลขคณิตที่คำนวณพหุนามในฟิลด์ให้พิจารณาว่าพหุนามนั้นเท่ากับพหุนามศูนย์หรือไม่ (นั่นคือพหุนามที่ไม่มีพจน์ที่ไม่เป็นศูนย์) ^{[ 1 ]}

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

อัลกอริทึม Schwartz –Zippelให้โซลูชันเชิงความน่าจะเป็นที่ใช้งานได้จริง โดยการทดสอบอินพุตแบบสุ่มและตรวจสอบว่าเอาต์พุตเป็นศูนย์หรือไม่ เป็นอัลกอริทึม PIT แบบสุ่มเวลาพหุนาม ตัวแรกที่ได้รับการพิสูจน์ว่าถูกต้อง ^{[ 1 ]}ยิ่งโดเมนที่ดึงอินพุตมามีขนาดใหญ่เท่าใด โอกาสที่ Schwartz–Zippel จะล้มเหลวก็จะยิ่งน้อยลงเท่านั้น หากบิตสุ่มมีจำนวนจำกัด อัลกอริทึม Chen-Kao (บนจำนวนตรรกยะ) หรืออัลกอริทึม Lewin-Vadhan (บนฟิลด์ใดๆ) จะต้องใช้บิตสุ่มน้อยกว่า แต่ต้องแลกมาด้วยเวลาการทำงานที่มากขึ้น^{[ 2 ]}

PIT แบบเบาบางจะ มีพจน์เอก นามที่ไม่เป็นศูนย์ไม่เกินจำนวนหนึ่ง PIT แบบเบาบางสามารถแก้ไขได้แบบกำหนดได้ในเวลาพหุนามของขนาดวงจรและจำนวนเอกนาม^{[ 1 ]}ดูเพิ่มเติม^{[ 5 ]}${\displaystyle m}$${\displaystyle m}$

ปัญหา PIT ที่มีดีกรีต่ำจะมีขอบเขตบนของดีกรีของพหุนาม ปัญหา PIT ที่มีดีกรีต่ำใดๆ สามารถลดขนาดวงจรลงได้ใน เวลา ต่ำกว่าเลขชี้กำลังของขนาดวงจรให้กลายเป็นปัญหา PIT สำหรับวงจรที่มีความลึกสี่ระดับ ดังนั้น ปัญหา PIT สำหรับวงจรที่มีความลึกสี่ระดับ (และต่ำกว่า) จึงได้รับการศึกษาอย่างเข้มข้น^{[ 1 ]}

• การประยุกต์ใช้ทฤษฎีบท Schwartz–Zippel

• เอกสารประกอบการบรรยายเรื่อง "การทดสอบเอกลักษณ์พหุนามโดยใช้ทฤษฎีบท Schwartz-Zippel"
• การทดสอบเอกลักษณ์พหุนาม โดย ไมเคิล ฟอร์บส์ - MITบน YouTube
• ผู้ชนะรางวัลการทดสอบเอกลักษณ์พหุนาม