โลโก้
ยูเนี่ยนพีเดีย
การสื่อสาร
ดาวน์โหลดได้จาก Google Play
ใหม่! ดาวน์โหลด ยูเนี่ยนพีเดีย บน Android ™ของคุณ!
ดาวน์โหลด
เร็วกว่าเบราว์เซอร์!
 

เอ็นพี (ความซับซ้อน)

ดัชนี เอ็นพี (ความซับซ้อน)

ในทฤษฎีความซับซ้อนในการคำนวณ กลุ่มปัญหา เอ็นพี (NP: Non-deterministic Polynomial time) สามารถนิยามได้สองวิธี ซึ่งเราสามารถพิสูจน์ได้ไม่ยากนักว่านิยามทั้งสองแบบนี้สมมูลกัน.

8 ความสัมพันธ์: พหุนามพี (ความซับซ้อน)ทฤษฎีความซับซ้อนในการคำนวณปัญหาความสอดคล้องแบบบูลโรคจอตามีสารสีเอ็นพี (ความซับซ้อน)เอ็นพีบริบูรณ์เซต (แก้ความกำกวม)

พหุนาม

upright พหุนาม ในคณิตศาสตร์ หมายถึง นิพจน์ที่สร้างจากตัวแปรอย่างน้อยหนึ่งตัวและสัมประสิทธิ์ โดยใช้การดำเนินการแค่ การบวก การลบ การคูณ และการยกกำลังโดยที่เลขชี้กำลังเป็นจำนวนเต็มที่ไม่เป็นลบเท่านั้น ตัวอย่างของพหุนามตัวแปรเดียวที่มี เป็นตัวแปร เช่น ซึ่งเป็นฟังก์ชันกำลังสอง พหุนามสามารถนำไปใช้ในสาขาต่าง ๆ ของคณิตศาสตร์และวิทยาศาสตร์ได้อย่างกว้างขวาง ตัวอย่างเช่น สมการพหุนาม ซึ่งสามารถนำไปใช้ในการแก้ปัญหาได้อย่างกว้างขวาง จากโจทย์ปัญหาพื้นฐาน ไปจนถึงปัญหาที่ซับซ้อนทางวิทยาศาสตร์ และยังใช้ในการนิยาม ฟังก์ชันพหุนาม ซึ่งนำไปใช้ตั้งแต่พื้นฐานของเคมีและฟิสิกส์ ไปจนถึงเศรษฐศาสตร์และสังคมศาสตร์ รวมถึงการนำไปใช้ในแคลคูลัส และการวิเคราะห์เชิงตัวเลข ซึ่งคล้ายคลึงกับฟังก์ชันต่าง ๆ ในคณิตศาสตร์ขั้นสูงนั้น พหุนามยังใช้ในการสร้างวงล้อพหุนาม และความหลากหลายทางพีชคณิต และเป็นแนวคิดสำคัญในพีชคณิต และเรขาคณิตเชิงพีชคณิตอีกด้ว.

ใหม่!!: เอ็นพี (ความซับซ้อน)และพหุนาม · ดูเพิ่มเติม »

พี (ความซับซ้อน)

ในเชิงของ ทฤษฎีความซับซ้อนในการคำนวณ พี เป็นกลุ่มความซับซ้อนที่ประกอบด้วยปัญหาการตัดสินใจที่สามารถหาคำตอบได้ในเวลาที่เป็นฟังก์ชันพหุนามกับขนาดของอินพุต (polynomial time) พี ประกอบด้วย ปัญหาที่สำคัญหลายอย่างที่มีประโยชน์ในชีวิต เช่น ปัญหาการหาตัวหารร่วมมากระหว่างจำนวนสองจำนวน ปัญหาการจับคู่มากที่สุด (Maximum Matching) ปัญหาจำนวนเฉพาะ ปัญหากำหนดการเชิงเส้น (Linear program) พี เป็นกลุ่มความซับซ้อนที่นักวิจัยเรียกว่า "ง่าย" แม้ว่าในความเป็นจริงแล้วปัญหาที่ใช้เวลาในการหาคำตอบ n^ ไม่น่าจะถือว่าง่ายก็ตาม.

ใหม่!!: เอ็นพี (ความซับซ้อน)และพี (ความซับซ้อน) · ดูเพิ่มเติม »

ทฤษฎีความซับซ้อนในการคำนวณ

ทฤษฎีความซับซ้อนในการคำนวณ (Computational Complexity Theory) เป็นสาขาหนึ่งของทฤษฎีการคำนวณ ที่มุ่งเน้นไปในการวิเคราะห์เวลาและเนื้อที่สำหรับการแก้ปัญหาหนึ่ง ๆ โดยปกติแล้วคำว่า "เวลา" ที่เราพูดถึงนั้น จะเป็นการนับจำนวนขั้นตอนที่ใช้ในการแก้ปัญหา ส่วนในเรื่องของ "เนื้อที่" เราจะพิจารณาเนื้อที่ ๆ ใช้ในการทำงานเท่านั้น (ไม่นับเนื้อที่ ๆ ใช้ในการเก็บข้อมูลป้อนเข้า).

ใหม่!!: เอ็นพี (ความซับซ้อน)และทฤษฎีความซับซ้อนในการคำนวณ · ดูเพิ่มเติม »

ปัญหาความสอดคล้องแบบบูล

ปัญหาความสอดคล้องแบบบูล หรือ SAT (Boolean satisfiability) เป็นปัญหาการตัดสินใจอย่างหนึ่งที่ถูกกล่าวถึงบ่อย ๆ ในศาสตร์ทางด้านทฤษฎีความซับซ้อนในการคำนวณ ตัวอย่างของปัญหา (instance) สำหรับปัญหานี้ก็คือ นิพจน์บูลีน (boolean expression) ที่ประกอบด้วยตัวแปร ตัวเชื่อมต่าง ๆ และวงเล็บ ปัญหานี้ถามคำถามที่ว่า สำหรับนิพจน์บูลีนที่กำหนด เราสามารถทำให้นิพจน์เป็นจริงโดยการกำหนดค่าให้กับตัวแปรได้หรือไม่ ในกรณีที่เราสามารถกำหนดค่าความจริงให้กับตัวแปรแล้วทำให้นิพจน์เป็นจริงได้ เราจะกล่าวว่านิพจน์นั้น สามารถทำให้เป็นจริงได้ (satisfiable) ปัญหา SAT จัดอยู่ในกลุ่มของปัญหาเอ็นพีบริบูรณ์ (NP-complete) ในบางครั้งเราอาจจะสนใจศึกษาความซับซ้อนของรูปแบบที่ต่างกันออกไปของปัญหา SAT ยกตัวอย่างเช่นปัญหา SAT แบบที่นิพจน์บูลีนอยู่ในรูปมาตรฐานแบบเชื่อม (หรือ Conjunctive Normal Form---CNF) ในกรณีนี้ถ้าแต่ละประพจน์เลือก (disjunct) ประกอบด้วยตัวแปรไม่เกิน 3 ตัวแปรเราจะเรียกปัญหาว่า 3-SAT ซึ่งเป็นปัญหาเอ็นพีบริบูรณ์เช่นเดียวกัน อย่างไรก็ตาม ในกรณีที่ตัวแปรในแต่ละประพจน์เลือกมีไม่เกิน 2 ตัวแปร (เรียกว่าปัญหา 2-SAT) นั้น เรามีอัลกอริธึมที่มีประสิทธิภาพในการแก้ปัญหาได้ นั่นก็คือ 2SAT \in P หรือหากจะพูดให้ชัดเจนกว่านั้น 2SAT \in NL \subseteq P (ทั้งนี้เนื่องจากขั้นตอนวิธีที่ใช้แก้ปัญหา 2-SAT เป็นขั้นตอนวิธีที่ทำงานโดยใช้เนื้อที่เป็นลอการิธึมบนเครื่องจักรทัวริงเชิงไม่กำหนดเท่านั้น).

ใหม่!!: เอ็นพี (ความซับซ้อน)และปัญหาความสอดคล้องแบบบูล · ดูเพิ่มเติม »

โรคจอตามีสารสี

Retinitis pigmentosaหรือว่า โรคอาร์พี (ตัวย่อ RP) เป็นโรคจอตาเสื่อมที่สามารถสืบทอดทางกรรมพันธุ์ที่เป็นเหตุแห่งความเสียหายต่อการเห็นอย่างรุนแรงบ่อยครั้งถึงขั้นตาบอด แต่ว่าการเสื่อมของ RP มีความต่าง ๆ กัน บางคนแสดงอาการตั้งแต่เป็นทารก บางคนอาจจะไม่เห็นอาการอะไรจนกระทั่งเลยวัยกลางคนไป โดยทั่วไป ยิ่งปรากฏอาการสายเท่าไร ความเสื่อมก็ยิ่งเป็นไปเร็วเท่านั้น บุคคลผู้ไม่มีอาร์พีสามารถเห็นได้ 90 องศาโดยรอบ (จากตรงกลางของลานสายตา) แต่บางคนที่มีอาร์พีเห็นได้น้อยกว่า 90 องศา โดยเป็นประเภทหนึ่งของโรคจอตาเสื่อม (retinopathy) อาร์พีเกิดจากความผิดปกติของเซลล์รับแสง (คือเซลล์รูปแท่งและเซลล์รูปกรวย) หรือของเซลล์ retinal pigment epithelium (ในชั้น pigmented layer) ในเรตินาที่มีผลเป็นเป็นการสูญเสียการเห็นไปตามลำดับ ผู้ที่มีโรคนี้อาจประสบความผิดปกติในการปรับตัวจากที่สว่างไปที่มืด หรือจากที่มืดไปที่สว่าง เป็นอาการที่ใชเรียกว่า ตาบอดแสง (nyctalopia หรือ night blindness) ซึ่งเป็นผลจากความเสื่อมลานสายตาส่วนรอบ ๆ แต่บางครั้ง จะมีการสูญเสียการเห็นในส่วนตรงกลางก่อน ทำให้บุคคลนั้นต้องแลดูวัตถุต่าง ๆ ทางข้างตา ผลของการมีอาร์พีเห็นได้ง่ายถ้าเปรียบเทียบกับทีวีหรือจอคอมพิวเตอร์ คือ แสงจากพิกเซลที่สร้างภาพบนจอเหมือนกับเซลล์รับแสงเป็นล้าน ๆ ตัวในเรตินา ยิ่งมีพิกเซลน้อยลงเท่าไร ภาพที่เห็นก็ชัดน้อยลงเท่านั้น มีเซลล์รับแสงจำนวนน้อยกว่า 10% ที่สามารถรับภาพสี โดยเป็นแสงมีความเข้มสูงเหมือนกับที่มีในช่วงกลางวัน เซลล์เหล่านี้อยู่ตรงกลางของเรตินาที่มีรูปเป็นวงกลม เซลล์รับแสงกว่า 90% ที่เหลือรับแสงมีความเข้มต่ำ เป็นภาพขาวดำ ซึ่งใช้ในที่สลัวและในตอนกลางคืน เป็นเซลล์ซึ่งอยู่รอบ ๆ เรตินา RP ทำลายเซลล์รับแสงจากนอกเข้ามาส่วนตรงกลาง หรือจากส่วนตรงกลางออกไปด้านนอก หรือทำลายเป็นย่อม ๆ ที่ทำให้เซลล์ส่วนตรงนั้นมีประสิทธิภาพในการตรวจจับแสงได้น้อยลง ความเสื่อมจากโรคนี้จะมีการลุกลาม และยังไม่มีวิธีรักษ.

ใหม่!!: เอ็นพี (ความซับซ้อน)และโรคจอตามีสารสี · ดูเพิ่มเติม »

เอ็นพี (ความซับซ้อน)

ในทฤษฎีความซับซ้อนในการคำนวณ กลุ่มปัญหา เอ็นพี (NP: Non-deterministic Polynomial time) สามารถนิยามได้สองวิธี ซึ่งเราสามารถพิสูจน์ได้ไม่ยากนักว่านิยามทั้งสองแบบนี้สมมูลกัน.

ใหม่!!: เอ็นพี (ความซับซ้อน)และเอ็นพี (ความซับซ้อน) · ดูเพิ่มเติม »

เอ็นพีบริบูรณ์

อ็นพี เอ็นพีบริบูรณ์ และเอ็นพีแบบยาก สำหรับทั้งสองกรณีที่พีเท่ากับเอ็นพี และพีไม่เท่ากับเอ็นพี ในทางทฤษฎีความซับซ้อนในการคำนวณ เอ็นพีบริบูรณ์ (NP-complete.) เป็นกลุ่มความซับซ้อนที่ยากที่สุดในเอ็นพี กล่าวคือปัญหาใด ๆ ในกลุ่มปัญหา เอ็นพี สามารถลดรูป (Reduce) มาเป็นปัญหาใน เอ็นพีบริบูรณ์ ได้ แม้ยังไม่ได้รับการพิสูจน์แต่เชื่อกันว่าเป็นกลุ่มปัญหาที่ไม่น่าจะมีขั้นตอนวิธีที่มีประสิทธิภาพใช้แก้ไขได้ ปัญหาในกลุ่มเอ็นพีบริบูรณ์สามารถเปลี่ยนแปลงไปมาเป็นปัญหาอื่นในกลุ่มเดียวกันได้ด้วย polynomial time ดังนั้นการที่มีขั้นตอนวิธีที่มีประสิทธิภาพสำหรับปัญหาใดปัญหาหนึ่งในเอ็นพีบริบูรณ์ ส่งผลให้เราสามารถแก้ปัญหาทั้งหมดในกลุ่มเอ็นพีได้อย่างมีประสิทธิภาพ กลุ่มความซับซ้อนเอ็นพีบริบูรณ์ในบางครั้งถูกเรียกสั้น ๆ ว่า NP-C.

ใหม่!!: เอ็นพี (ความซับซ้อน)และเอ็นพีบริบูรณ์ · ดูเพิ่มเติม »

เซต (แก้ความกำกวม)

ซต สามารถหมายถึง.

ใหม่!!: เอ็นพี (ความซับซ้อน)และเซต (แก้ความกำกวม) · ดูเพิ่มเติม »

ขาออกขาเข้า
Hey! เราอยู่ใน Facebook ตอนนี้! »