ในวิทยาการคอมพิวเตอร์ PPAD ( “Polynomial Parity Arguments on Directed graphs”) เป็นคลาสความซับซ้อน ที่ Christos Papadimitriouแนะนำในปี 1994 PPAD เป็นคลาสย่อยของTFNPโดยอิงจากฟังก์ชันที่สามารถแสดงให้เห็นว่าสมบูรณ์ได้ด้วยการอ้างเหตุผลความเท่าเทียมกัน คลาสนี้ได้รับความสนใจอย่างมากในสาขาทฤษฎีเกมเชิงอั ลกอริทึม เนื่องจากมีปัญหาการคำนวณสมดุลแนช : ปัญหานี้ได้รับการพิสูจน์แล้วว่าสมบูรณ์สำหรับ PPAD โดย Daskalakis, Goldberg และ Papadimitriou โดยมีผู้เล่นอย่างน้อย 3 คน และต่อมาได้รับการขยายโดย Chen และ Deng เป็น 2 คน

PPAD เป็นเซตย่อยของคลาสTFNPซึ่งเป็นคลาสของปัญหาฟังก์ชันในFNPที่รับประกันได้ว่าเป็นปัญหา แบบสมบูรณ์ นิยามอย่างเป็นทางการ ของ TFNPมีดังต่อไปนี้:

ความสัมพันธ์ทวิภาค P( x , y ) อยู่ใน TFNP ก็ต่อเมื่อมีอัลกอริทึมเวลาพหุนามเชิงกำหนดที่สามารถตรวจสอบได้ว่า P( x , y ) เป็นจริงหรือไม่ เมื่อกำหนดทั้งxและyและสำหรับทุกxจะมีyที่ทำให้ P( x , y ) เป็นจริง

กลุ่มย่อยของ TFNP ถูกกำหนดโดยอิงจากประเภทของการพิสูจน์ทางคณิตศาสตร์ที่ใช้พิสูจน์ว่ามีคำตอบอยู่เสมอ โดยทั่วไปแล้ว PPAD เป็นกลุ่มย่อยของ TFNP ที่การรับประกันว่ามีyที่ทำให้ P( x , y ) เป็นจริงนั้นขึ้นอยู่กับการพิสูจน์ความเท่าเทียมกันบนกราฟแบบมีทิศทาง กลุ่มนี้ถูกกำหนดอย่างเป็นทางการโดยการระบุปัญหาที่สมบูรณ์ข้อหนึ่งของกลุ่ม ซึ่งเรียกว่าEnd-Of-The-Line :

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

ถ้าหากมี s อยู่ tดังกล่าวจะต้องมีอยู่เพราะโครงสร้างของ G หมายความว่าจุดยอดที่มีเพื่อนบ้านเพียงหนึ่งเดียวจะมาเป็นคู่ โดยเฉพาะอย่างยิ่ง เมื่อกำหนดsแล้ว เราสามารถหาt ดังกล่าวได้ ที่ปลายอีกด้านของสตริงที่เริ่มต้นจากs (โปรดทราบว่าอาจใช้เวลาแบบเลขชี้กำลังหากเราประเมิน f ซ้ำๆ)

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

อย่างไรก็ตาม มีบางกรณีที่รับประกันว่าจะมีคำตอบที่เป็นจำนวนตรรกยะ สำหรับกรณีดังกล่าว Filos-Ratsikas, Hansen, Høgh และ Hollender นำเสนอวิธีการทั่วไปในการพิสูจน์ว่าการคำนวณ คำตอบ ที่แน่นอนเป็นของ PPAD

PPAD อยู่ใน (แต่ไม่ทราบว่าเท่ากับ) PPA (คลาสที่สอดคล้องกันของอาร์กิวเมนต์ความเท่าเทียมกันสำหรับ กราฟ ที่ไม่มีทิศทาง ) ซึ่งอยู่ใน TFNP PPAD ยังอยู่ใน (แต่ไม่ทราบว่าเท่ากับ) PPP ซึ่ง คลาสย่อยอื่นของ TFNP ประกอบด้วยCLS [

PPAD เป็นกลุ่มปัญหาที่เชื่อกันว่ายาก แต่การบรรลุ PPAD-completeness เป็นหลักฐานที่อ่อนกว่าของการแก้ไม่ได้เมื่อเทียบกับการบรรลุNP-completenessปัญหา PPAD ไม่สามารถเป็น NP-complete ได้ด้วยเหตุผลทางเทคนิคที่ว่า NP เป็นกลุ่มปัญหาการตัดสินใจ แต่คำตอบของปัญหา PPAD มักจะเป็นใช่เสมอ เนื่องจากทราบว่ามีวิธีแก้ปัญหาอยู่ แม้ว่าการหาวิธีแก้ปัญหานั้นอาจจะยากก็ตามอย่างไรก็ตาม PPAD และ NP มีความสัมพันธ์กันอย่างใกล้ชิด ในขณะที่คำถามว่ามีสมดุลแนชสำหรับเกมที่กำหนดหรือไม่นั้นไม่สามารถเป็น NP-hard ได้เพราะคำตอบคือใช่เสมอ แต่คำถามว่า มีสมดุล ที่สอง หรือไม่ นั้นเป็น NP-complete ตัวอย่างของปัญหา PPAD-complete ได้แก่ การหาสมดุลแนชการคำนวณจุดคงที่ใน ฟังก์ชัน Brouwerและการหาสมดุล Arrow-Debreuในตลาด

Fearnley, Goldberg, Hollender และ Savani [ ว่าคลาสความซับซ้อนที่เรียกว่าCLSเท่ากับการตัดกันของ PPAD และPLS

Etessami และ Yannakakis (ผู้คิดค้นคลาสFIXP ที่เกี่ยวข้อง ) เขียนว่า " ส่วนย่อย เชิงเส้นแบบเป็นช่วงของ FIXP เท่ากับ PPAD" กล่าวอีกนัยหนึ่งปัญหาใน PPAD คือปัญหาใน FIXP ซึ่งฟังก์ชันอินพุตเป็นเชิงเส้นแบบเป็นช่วง

• สมดุล จุดคงที่ และคลาสความซับซ้อน: การสำรวจ

• การค้นหาสมดุลแนชในเกมที่มีผู้เล่น 2 คนหรือสมดุลเอปซิลอนในเกมที่มีผู้เล่นจำนวนเท่าใดก็ได้

• การค้นหาจุดสามสีในทฤษฎีบทของสเปอร์เนอร์
• การค้นหาวิธีการตัดเค้กที่ปราศจากความอิจฉาเมื่อฟังก์ชันอรรถประโยชน์กำหนดโดยอัลกอริทึมเวลาพหุนาม