ผลต่างระหว่างรุ่นของ "พี (ความซับซ้อน)"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
ล +cat |
ไม่มีความย่อการแก้ไข |
||
บรรทัด 1:
ในเชิงของ [[ทฤษฎีความซับซ้อนในการคำนวณ]] '''พี''' เป็น[[กลุ่มความซับซ้อน]]ที่ประกอบด้วย[[ปัญหาการตัดสินใจ]]ที่สามารถหาคำตอบได้ในเวลาที่เป็นฟังก์ชันพหุนามกับขนาดของอินพุต (polynomial time)
พี ประกอบด้วย
พี เป็นกลุ่มความซับซ้อนที่นักวิจัยเรียกว่า "ง่าย" แม้ว่าในความเป็นจริงแล้วปัญหาที่ใช้เวลาในการหาคำตอบ <math>n^{100000} </math> ไม่น่าจะถือว่าง่ายก็ตาม
บรรทัด 10:
* การเพิ่มขนาดของอินพุตเป็นสองเท่าส่งผลให้เวลาการทำงานโตขึ้นเป็นค่าคงที่เท่านั้น (ในแง่นี้ให้เปรียบเทียบกับฟังก์ชันที่เป็น exponential) ซึ่งการเพิ่มขนาดของอินพุตเป็นสองเท่าอาจจะทำให้เวลาการทำงานโตขึ้นเป็นกำลังสองหรือมากกว่านั้น
* ฟังก์ชันพหุนามมีสมบัติปิดภายใต้ composition นั่นก็คือ หากเรามีอัลกอริทึม A ที่ทำงานรวดเร็ว (เป็นฟังก์ชันพหุนามกับขนาดของอินพุต) และอัลกอริทึม B สามารถเรียกใช้อัลกอริทึม A เพื่อทำงานได้ หากเรารู้ว่า B
== ความสัมพันธ์กับกลุ่มอื่นๆ ==
บรรทัด 24:
** ข้อมูลบนเทป (tape content)
ดังนั้น configuration ที่เป็นไปได้ทั้งหมดของ เครื่องจักรทัวริงที่ใช้เนื้อที่ไม่เกิน <math>O(\log n) </math> จะเป็นฟังก์ชันพหุนามกับขนาดของอินพุต
* P และ NP เล็กกว่า PSPACE เพราะว่าเราสามารถ simulate การทำงานของเครื่องจักรทัวริงเชิงไม่กำหนดได้โดย
ปัญหาที่ยากที่สุดที่อยู่ในพีก็คือ [[พีบริบูรณ์]]
| |||