ดูต้นฉบับสำหรับ พี (ความซับซ้อน)


ในเชิงของ [[ทฤษฎีความซับซ้อนในการคำนวณ]] '''พี''' เป็น[[กลุ่มความซับซ้อน]]ที่ประกอบด้วย[[ปัญหาการตัดสินใจ]]ที่สามารถหาคำตอบได้ในเวลาที่เป็นฟังก์ชันพหุนามกับขนาดของอินพุต (polynomial time)

พี ประกอบด้วย ปัญหาที่สำคัญหลายอย่างที่มีประโยชน์ในชีวิต เช่น ปัญหาการหาตัวหารร่วมมากระหว่างจำนวนสองจำนวน ปัญหาการจับคู่มากที่สุด (Maximum Matching) ปัญหาจำนวนเฉพาะ ปัญหากำหนดการเชิงเส้น (Linear program) 

พี เป็นกลุ่มความซับซ้อนที่นักวิจัยเรียกว่า "ง่าย" แม้ว่าในความเป็นจริงแล้วปัญหาที่ใช้เวลาในการหาคำตอบ <math>n^{100000} </math> ไม่น่าจะถือว่าง่ายก็ตาม 

== ทำไมจึงเรียกพีว่า "ง่าย" == 
มีหลายเหตุผลที่การทำงานเป็นพหุนามกับขนาดของอินพุตเป็นตัวแทนของความง่าย ตัวอย่างของเหตุผลเหล่านั้นก็คือ

* การเพิ่มขนาดของอินพุตเป็นสองเท่าส่งผลให้เวลาการทำงานโตขึ้นเป็นค่าคงที่เท่านั้น (ในแง่นี้ให้เปรียบเทียบกับฟังก์ชันที่เป็น exponential) ซึ่งการเพิ่มขนาดของอินพุตเป็นสองเท่าอาจจะทำให้เวลาการทำงานโตขึ้นเป็นกำลังสองหรือมากกว่านั้น 

* ฟังก์ชันพหุนามมีสมบัติการปิดภายใต้ composition นั่นก็คือ หากเรามีขั้นตอนวิธี A ที่ทำงานรวดเร็ว (เป็นฟังก์ชันพหุนามกับขนาดของอินพุต) และขั้นตอนวิธี B สามารถเรียกใช้ขั้นตอนวิธี A เพื่อทำงานได้ หากเรารู้ว่า B เรียกใช้ A เป็นจำนวนครั้งที่เป็นฟังก์ชันพหุนาม เวลาการทำงานรวมก็จะยังเป็นฟังก์ชันพหุนามอยู่ หรือหากจะพูดให้เป็นทางการก็คือ  <math>P^P =P </math> (ปัญหาที่อยู่ในพี มีสมบัติการปิดภายใต้การเรียกใช้ออราเคิล) สมบัตินี้ทำให้เราสามารถออกแบบขั้นตอนวิธีที่มีประสิทธิภาพโดยการมองอีกขั้นตอนวิธีหนึ่งเป็นกล่องดำ (Black Box) ได้

== ความสัมพันธ์กับกลุ่มอื่นๆ ==
เราพิจารณาความสัมพันธ์ระหว่างพีกับกลุ่มที่ใกล้เคียงกับพี ความสัมพันธ์ในปัจจุบันที่รู้คือ 

:<math>L \subseteq NL \subseteq P= AL \subseteq NP \subseteq PSPACE \subseteq EXP </math>

* เรารู้ว่า [[พี (ความซับซ้อน)|พี]] ไม่เท่ากับ [[อีเอ็กซ์พี]] เนื่องมาจาก [[ทฤษฎีลำดับชั้นของเวลา]] 
* เรารู้ว่า [[แอล (ความซับซ้อน)| แอล]] ไม่เท่ากับ [[พีสเปซ]] เนื่องมาจาก [[ทฤษฎีลำดับชั้นของเนื้อที่]]
* แอลกับเอ็นแอลเล็กกว่าพีเพราะว่า เวลาในการทำงานถูกจำกัดด้วยจำนวนของ configuration ที่เป็นไปได้ทั้งหมด ซึ่งมีค่าขึ้นกับ
** ตำแหน่งของหัวอ่าน (head position) 
** สถานะของ[[เครื่องจักรทัวริง]] (state)
** ข้อมูลบนเทป (tape content)
ดังนั้นองค์ประกอบที่เป็นไปได้ทั้งหมดของเครื่องจักรทัวริงที่ใช้เนื้อที่ไม่เกิน <math>O(\log n)</math> จะเป็นฟังก์ชันพหุนามกับขนาดของอินพุต 
* พีและเอ็นพีเล็กกว่าพีเสปซเพราะว่าเราสามารถจำลองการทำงานของเครื่องจักรทัวริงเชิงไม่กำหนดได้ โดยใช้หลักการของ Depth First Search และขนาดของแสต็กที่ใช้จะไม่เกินฟังก์ชันพหุนามกับขนาดของอินพุต 

ปัญหาที่ยากที่สุดที่อยู่ในพีก็คือ [[พีบริบูรณ์]] 

หากเราสนใจกลุ่มความซับซ้อนพี แบบที่เป็น non-uniform เราจะได้นิยามของ [[พี/โพลี|P/poly]] ซึ่งเป็นกลุ่มความซับซ้อนที่ปัญหาภายในกลุ่มสามารถแก้ได้ด้วยกลุ่มของวงจร (family of circuit) ที่มีขนาดเป็นฟังก์ชันพหุนามกับขนาดของอินพุต (แท้จริงแล้ว พี/โพลี สามารถนิยามได้อีกแบบหนึ่งด้วยการใช้เครื่องจักรทัวริงที่รับคำแนะนำได้ และนิยามทั้งสองแบบนี้พิสูจน์ได้ว่าเหมือนกัน)

== คุณสมบัติ == 

[[หมวดหมู่:ทฤษฎีความซับซ้อนในการคำนวณ]]