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

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

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

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

9 ความสัมพันธ์: พี (ความซับซ้อน)กลุ่มความซับซ้อนการลดรูป (ความซับซ้อน)วิทยาการศึกษาสำนึกทฤษฎีความซับซ้อนในการคำนวณขั้นตอนวิธีปัญหาการตัดสินใจเอ็นพี (ความซับซ้อน)NP

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

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

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

กลุ่มความซับซ้อน

หน้านี้ประกอบด้วยกลุ่มความซับซ้อนที่สำคัญทั้งหมดในด้านของทฤษฎีความซับซ้อนในการคำนวณ.

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

การลดรูป (ความซับซ้อน)

ในด้านของ ทฤษฎีการคำนวณได้ และ ทฤษฎีความซับซ้อนในการคำนวณ คำว่า การลดรูป นั้นหมายถึงการพิจารณาการแก้ปัญหาอย่างหนึ่งให้ไปเป็นการแก้ปัญหาอีกปัญหาหนึ่ง ซึ่งบางทีอาจจะรู้สึกว่าปัญหานั้นไม่เกี่ยวกันเลยก็ได้ ถ้าเรากล่าวว่า A ลดรูปเป็น B เราหมายความว่าการแก้ปัญหา B ได้จะส่งผลให้เราสามารถแก้ปัญหา A ได้ด้วย เพราะฉะนั้น A จะไม่ยากไปกว่า B.

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

วิทยาการศึกษาสำนึก

วริสติก เป็นทั้งศาสตร์และศิลป์ของการค้นหาและการประดิษฐ์ มาจากภาษากรีกเช่นเดียวกับคำว่า ยูเรก้า (eureka, εὑρισκ&omega) ซึ่งหมายถึง ข้าพเจ้าพบแล้ว ("I find") การค้นพบฮิวริสติกเป็นผลมาจากความพยายามไตร่ตรองอย่างถึงที่สุด นักคณิตศาสตร์ชื่อ จอร์จ โพลยา (George Polya) ทำให้ฮิวริสติกได้รับความนิยมในคริสต์ศตวรรษที่ 20 ในหนังสือของเขาที่ชื่อ แก้ปัญหาอย่างไร (How to Solve It) ปกติแล้วเมื่อนักเรียนได้เรียนบทพิสูจน์ทางคณิตศาสตร์แล้ว พวกเขามักไม่ทราบว่าจะหาบทพิสูจน์ดังกล่าวได้อย่างไรเพราะเป็นเรื่องที่ยากมาก หนังสือ แก้ปัญหาอย่างไร ได้เก็บรวบรวมไอเดียเกี่ยวกับฮิวริสติกที่เขาใช้สอนนักศึกษา ซึ่งหนังสือนี้เป็นสิ่งที่ช่วยแนะแนวทางที่มองปัญหาและวิธีการแก้ปัญหาได้;ฮิวริสติกที่ใช้ทั่วไป.

ใหม่!!: เอ็นพีบริบูรณ์และวิทยาการศึกษาสำนึก · ดูเพิ่มเติม »

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

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

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

ขั้นตอนวิธี

ั้นตอนวิธี หรือ อัลกอริทึม (algorithm) หมายถึงกระบวนการแก้ปัญหาที่สามารถเข้าใจได้ มีลำดับหรือวิธีการในการแก้ไขปัญหาใดปัญหาหนึ่งอย่างเป็นขั้นเป็นตอนและชัดเจน เมื่อนำเข้าอะไร แล้วจะต้องได้ผลลัพธ์เช่นไร ซึ่งแตกต่างจากการแก้ปัญหาแบบสามัญสำนึก หรือฮิวริสติก (heuristic) โดยทั่วไป ขั้นตอนวิธี จะประกอบด้วย วิธีการเป็นขั้นๆ และมีส่วนที่ต้องทำแบบวนซ้ำ (iterate) หรือ เวียนเกิด (recursive) โดยใช้ตรรกะ (logic) และ/หรือ ในการเปรียบเทียบ (comparison) ในขั้นตอนต่างๆ จนกระทั่งเสร็จสิ้นการทำงาน ในการทำงานอย่างเดียวกัน เราอาจจะเลือกขั้นตอนวิธีที่ต่างกันเพื่อแก้ปัญหาได้ โดยที่ผลลัพธ์ที่ได้ในขั้นสุดท้ายจะออกมาเหมือนกันหรือไม่ก็ได้ และจะมีความแตกต่าง ที่จำนวนและชุดคำสั่งที่ใช้ต่างกันซึ่งส่งผลให้ เวลา (time), และขนาดหน่วยความจำ (space) ที่ต้องการต่างกัน หรือเรียกได้อีกอย่างว่ามีความซับซ้อน (complexity) ต่างกัน การนำขั้นตอนวิธีไปใช้ ไม่จำกัดเฉพาะการเขียนโปรแกรมคอมพิวเตอร์ แต่สามารถใช้กับปัญหาอื่น ๆ ได้เช่น การออกแบบวงจรไฟฟ้า, การทำงานเครื่องจักรกล, หรือแม้กระทั่งปัญหาในธรรมชาติ เช่น วิธีของสมองมนุษย์ในการคิดเลข หรือวิธีการขนอาหารของแมลง หนึ่งในขั้นตอนวิธีอย่างง่าย คือ ขั้นตอนวิธีที่ใช้หาจำนวนที่มีค่ามากที่สุดในรายการ (ซึ่งไม่ได้เรียงลำดับไว้) ในการแก้ปัญหานี้ เราจะต้องดูจำนวนทุกจำนวนในรายการ ซึ่งมีขั้นตอนวิธีดังนี้.

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

ปัญหาการตัดสินใจ

ปัญหาการตัดสินใจ เป็นปัญหาในทฤษฎีการคำนวณได้และทฤษฎีความซับซ้อนในการคำนวณ ซึ่งพิจารณาค่าอินพุตและตอบเพียงว่า "ใช่" หรือ "ไม่ใช่" เท่านั้น เช่นปัญหาที่ถามว่าจำนวนเต็ม x เป็นจำนวนเฉพาะใช่หรือไม.

ใหม่!!: เอ็นพีบริบูรณ์และปัญหาการตัดสินใจ · ดูเพิ่มเติม »

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

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

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

NP

อ็นพี NP หรือ Np เป็นอักษรย่อภาษาอังกฤษ สามารถหมายถึง.

ใหม่!!: เอ็นพีบริบูรณ์และNP · ดูเพิ่มเติม »

เปลี่ยนเส้นทางที่นี่:

NP-completeปัญหาเอ็นพีบริบูรณ์

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