Loading AI tools
จากวิกิพีเดีย สารานุกรมเสรี
ในเชิงของ ทฤษฎีความซับซ้อนในการคำนวณ พี เป็นกลุ่มความซับซ้อนที่ประกอบด้วยปัญหาการตัดสินใจที่สามารถหาคำตอบได้ในเวลาที่เป็นฟังก์ชันพหุนามกับขนาดของอินพุต (polynomial time)
พี ประกอบด้วย ปัญหาที่สำคัญหลายอย่างที่มีประโยชน์ในชีวิต เช่น ปัญหาการหาตัวหารร่วมมากระหว่างจำนวนสองจำนวน ปัญหาการจับคู่มากที่สุด (Maximum Matching) ปัญหาจำนวนเฉพาะ ปัญหากำหนดการเชิงเส้น (Linear program)
พี เป็นกลุ่มความซับซ้อนที่นักวิจัยเรียกว่า "ง่าย" แม้ว่าในความเป็นจริงแล้วปัญหาที่ใช้เวลาในการหาคำตอบ ไม่น่าจะถือว่าง่ายก็ตาม
มีหลายเหตุผลที่การทำงานเป็นพหุนามกับขนาดของอินพุตเป็นตัวแทนของความง่าย ตัวอย่างของเหตุผลเหล่านั้นก็คือ
เราพิจารณาความสัมพันธ์ระหว่างพีกับกลุ่มที่ใกล้เคียงกับพี ความสัมพันธ์ในปัจจุบันที่รู้คือ
ดังนั้นองค์ประกอบที่เป็นไปได้ทั้งหมดของเครื่องจักรทัวริงที่ใช้เนื้อที่ไม่เกิน จะเป็นฟังก์ชันพหุนามกับขนาดของอินพุต
ปัญหาที่ยากที่สุดที่อยู่ในพีก็คือ พีบริบูรณ์
หากเราสนใจกลุ่มความซับซ้อนพี แบบที่เป็น non-uniform เราจะได้นิยามของ P/poly ซึ่งเป็นกลุ่มความซับซ้อนที่ปัญหาภายในกลุ่มสามารถแก้ได้ด้วยกลุ่มของวงจร (family of circuit) ที่มีขนาดเป็นฟังก์ชันพหุนามกับขนาดของอินพุต (แท้จริงแล้ว พี/โพลี สามารถนิยามได้อีกแบบหนึ่งด้วยการใช้เครื่องจักรทัวริงที่รับคำแนะนำได้ และนิยามทั้งสองแบบนี้พิสูจน์ได้ว่าเหมือนกัน)
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.