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