ในวิทยาการคอมพิวเตอร์ (โดยเฉพาะด้านอัลกอริธึม ) แผนการประมาณค่าแบบใช้เวลาพหุนาม ( PTAS ) เป็น อัลกอริธึมประมาณค่าประเภทหนึ่งสำหรับปัญหาการหาค่าเหมาะสมที่สุด (ส่วนใหญ่จะ เป็นปัญหาการหาค่าเหมาะสมที่สุด แบบ NP-hard )

PTAS เป็นอัลกอริทึมที่รับอินสแตนซ์ของปัญหาการหาค่าเหมาะสมที่สุดและพารามิเตอร์ε > 0และสร้างโซลูชันที่อยู่ภายในปัจจัย1 + εของค่าเหมาะสมที่สุด (หรือ1 – εสำหรับปัญหาการหาค่าสูงสุด) ตัวอย่างเช่น สำหรับปัญหาพนักงานขายเดินทาง แบบยุคลิด PTAS จะสร้างเส้นทางที่มีความยาวไม่เกิน(1 + ε) Lโดยที่Lคือความยาวของเส้นทางที่สั้นที่สุด^{[ 1 ]}

เวลาในการทำงานของ PTAS จะต้องเป็นพหุนามตามขนาดของปัญหาสำหรับค่า ε ที่กำหนดไว้ แต่สามารถแตกต่างกันได้สำหรับค่า ε ที่แตกต่างกัน ดังนั้นอัลกอริทึมที่ทำงานในเวลาO ( n ^1/ε )หรือแม้แต่O ( n ^exp(1/ε) )ก็ถือว่าเป็น PTAS

ปัญหาในทางปฏิบัติของอัลกอริธึม PTAS คือเลขชี้กำลังของพหุนามอาจเพิ่มขึ้นอย่างมากเมื่อ ε ลดลง ตัวอย่างเช่น หากเวลาในการทำงานคือO ( n ^(1/ε)! )วิธีหนึ่งในการแก้ไขปัญหานี้คือการกำหนดรูปแบบการประมาณค่าแบบพหุนามที่มีประสิทธิภาพหรือEPTASซึ่งเวลาในการทำงานจะต้องเป็นO ( n ^c )สำหรับค่าคงที่c ที่ ไม่ขึ้นอยู่กับεวิธีนี้ทำให้มั่นใจได้ว่าการเพิ่มขนาดของปัญหาจะมีผลกระทบต่อเวลาในการทำงานในระดับเดียวกันโดยไม่คำนึงถึงค่า ε ที่ใช้ อย่างไรก็ตาม ค่าคงที่ภายใต้Big-Oยังคงสามารถขึ้นอยู่กับ ε ได้ตามอำเภอใจ กล่าวอีกนัยหนึ่ง EPTAS ทำงานใน เวลา FPTโดยที่พารามิเตอร์คือ ε

ข้อจำกัดที่เข้มงวดกว่าและมีประโยชน์ในทางปฏิบัติคือแผนการประมาณค่าแบบใช้เวลาพหุนามอย่างสมบูรณ์หรือFPTASซึ่งกำหนดให้ขั้นตอนวิธีต้องเป็นพหุนามทั้งในขนาดของปัญหาnและ1/ ε

เว้นแต่ว่าP = NPจะถือว่าFPTAS ⊊ PTAS ⊊ APX [ ^{2 ] ดังนั้น}ภายใต้สมมติฐานนี้ ปัญหา APX-hardจึงไม่มี PTAS

อีกรูปแบบหนึ่งของ PTAS ที่กำหนดได้แน่นอนคือแผนการประมาณค่าแบบกึ่งพหุนามเวลาหรือQPTAS QPTAS มีความซับซ้อนของเวลาเท่ากับn ^{polylog ( n )}สำหรับแต่ละค่าε > 0 ที่กำหนดไว้ ยิ่งไปกว่านั้น PTAS สามารถทำงานได้ใน เวลา FPTสำหรับการกำหนดพารามิเตอร์บางอย่างของปัญหา ซึ่งนำไปสู่แผนการประมาณค่าแบบมีพารามิเตอร์

ปัญหาบางอย่างที่ไม่มี PTAS อาจยอมรับอัลกอริทึมแบบสุ่มที่มีคุณสมบัติคล้ายกัน นั่นคือโครงการประมาณค่าแบบสุ่มในเวลาพหุนามหรือPRAS PRAS คืออัลกอริทึมที่รับอินสแตนซ์ของปัญหาการหาค่าเหมาะสมที่สุดหรือการนับ และพารามิเตอร์ε > 0และสร้างคำตอบในเวลาพหุนามซึ่งมีโอกาสสูงที่จะอยู่ภายในปัจจัยεของค่าที่เหมาะสมที่สุด โดยทั่วไป "โอกาสสูง" หมายถึงโอกาสมากกว่า 3/4 แม้ว่าเช่นเดียวกับคลาสความซับซ้อนเชิงความน่าจะเป็นส่วนใหญ่ คำจำกัดความนี้จะมีความยืดหยุ่นต่อการเปลี่ยนแปลงในค่าที่แน่นอนนี้ (ข้อกำหนดขั้นต่ำโดยทั่วไปจะมากกว่า 1/2) เช่นเดียวกับ PTAS, PRAS ต้องมีเวลาในการประมวลผลเป็นพหุนามในnแต่ไม่จำเป็นต้องเป็นพหุนามในεด้วยข้อจำกัดเพิ่มเติมเกี่ยวกับเวลาในการประมวลผลในεเราสามารถกำหนดโครงการประมาณค่าแบบสุ่มในเวลาพหุนามที่มีประสิทธิภาพหรือEPRASที่คล้ายกับ EPTAS และโครงการประมาณค่าแบบสุ่มในเวลาพหุนามอย่างสมบูรณ์หรือFPRASที่คล้ายกับ FPTAS ^{[ 3 ]}

คำว่า PTAS อาจใช้เพื่ออ้างถึงคลาสของปัญหาการเพิ่มประสิทธิภาพที่มี PTAS PTAS เป็นเซตย่อยของAPXและเว้นแต่ว่าP = NPจะเป็นเซตย่อยที่เข้มงวด^{[ 2 ]}

การเป็นสมาชิกของ PTAS สามารถแสดงได้โดยใช้การลดรูป PTAS , การลดรูป Lหรือการลดรูป Pซึ่งทั้งหมดนี้จะรักษาสถานะการเป็นสมาชิกของ PTAS ไว้ และยังสามารถใช้เพื่อแสดงความสมบูรณ์ของ PTAS ได้อีกด้วย ในทางกลับกัน การแสดงว่าไม่ได้เป็นสมาชิกของ PTAS (กล่าวคือ การไม่มีอยู่ของ PTAS) สามารถทำได้โดยการแสดงว่าปัญหานั้นยากระดับ APX หลังจากนั้น การมีอยู่ของ PTAS จะแสดงว่า P = NP ความยากระดับ APX มักแสดงผ่านการลดรูป PTAS หรือ การ ลด รูป AP

• แผนการประมาณค่าแบบพารามิเตอร์ซึ่งเป็นแผนการประมาณค่าที่ทำงานในเวลาFPT

• Complexity Zoo: PTAS , EPTAS .
• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek KarpinskiและGerhard Woeginger , คู่มือรวมปัญหาการหาค่าเหมาะสมที่สุดแบบ NP – รายชื่อปัญหาการหาค่าเหมาะสมที่สุดแบบ NP ที่มี PTAS