ผลต่างระหว่างรุ่นของ "พี (ความซับซ้อน)"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
บรรทัด 21:
* แอลกับเอ็นแอลเล็กกว่าพีเพราะว่า เวลาในการทำงานถูกจำกัดด้วยจำนวนของ configuration ที่เป็นไปได้ทั้งหมด ซึ่งมีค่าขึ้นกับ
** ตำแหน่งของหัวอ่าน (head position)
** สถานะของ[[เครื่องจักรทัวริง]] (state)
** ข้อมูลบนเทป (tape content)
ดังนั้น
* พีและเอ็นพีเล็กกว่าพีเสปซเพราะว่าเราสามารถ
ปัญหาที่ยากที่สุดที่อยู่ในพีก็คือ [[พีบริบูรณ์]]
|