ในทางทฤษฎีความซับซ้อนในการคำนวณ เอ็นพีบริบูรณ์ (อังกฤษ: NP-complete) เป็นกลุ่มความซับซ้อนที่ยากที่สุดในเอ็นพี กล่าวคือปัญหาใด ๆ ในกลุ่มปัญหา เอ็นพี สามารถลดรูป (Reduce) มาเป็นปัญหาใน เอ็นพีบริบูรณ์ ได้ แม้ยังไม่ได้รับการพิสูจน์แต่เชื่อกันว่าเป็นกลุ่มปัญหาที่ไม่น่าจะมีขั้นตอนวิธีที่มีประสิทธิภาพใช้แก้ไขได้ ปัญหาในกลุ่มเอ็นพีบริบูรณ์สามารถเปลี่ยนแปลงไปมาเป็นปัญหาอื่นในกลุ่มเดียวกันได้ด้วย polynomial time ดังนั้นการที่มีขั้นตอนวิธีที่มีประสิทธิภาพสำหรับปัญหาใดปัญหาหนึ่งในเอ็นพีบริบูรณ์ ส่งผลให้เราสามารถแก้ปัญหาทั้งหมดในกลุ่มเอ็นพีได้อย่างมีประสิทธิภาพ กลุ่มความซับซ้อนเอ็นพีบริบูรณ์ในบางครั้งถูกเรียกสั้น ๆ ว่า NP-C
แผนภาพออยเลอร์แสดงความสัมพันธ์ของ
พี,
เอ็นพี เอ็นพีบริบูรณ์ และเอ็นพีแบบยาก สำหรับทั้งสองกรณีที่พีเท่ากับเอ็นพี และพีไม่เท่ากับเอ็นพี
เราจะเรียกปัญหาการตัดสินใจ C ว่าเป็น เอ็นพีบริบูรณ์ เมื่อ
- C เป็นปัญหาเอ็นพี
- C เป็นปัญหาเอ็นพีแบบยาก (นั่นก็คือทุกปัญหาในเอ็นพีสามารถลดรูปเป็น C ได้)
วิธีการแก้ปัญหาเอ็นพีบริบูรณ์ ในกรณีที่เราต้องการแก้ปัญหาแบบหาคำตอบดีที่สุด ของปัญหาที่เป็นเอ็นพีบริบูรณ์ เช่น ต้องการหากลุ่มพรรคพวกที่ใหญ่ที่สุดในกราฟ ๆ หนึ่ง เรามีความหวังเพียงน้อยนิดที่จะหาคำตอบแบบดีที่สุดได้ทุกครั้งด้วยขั้นตอนวิธีที่มีประสิทธิภาพ (อาจจะหาได้สำหรับตัวอย่างที่มีขนาดเล็ก) โดยทั่วไปแล้วเราจะยอมตอบผิดบ้าง ซึ่งวิธีที่อาจจะนำมาใช้มีดังต่อไปนี้
- ใช้การประมาณ เพื่อหาคำตอบที่พิสูจน์ได้ว่าไม่แย่เกินไปนัก
- ใช้ขั้นตอนวิธีที่มีประสิทธิภาพสำหรับบางรูปแบบการกระจายตัวของอินพุต
- จงใจตอบเฉพาะกรณีพิเศษ
- ใช้ฮิวริสติก ซึ่งจะทำให้ขั้นตอนวิธีทำงานได้ดีในหลาย ๆ กรณี แต่ไม่สามารถพิสูจน์อะไรได้เลย ในบางทีอาจจะได้คำตอบที่แย่เกินกว่าจะรับได้
เอ, นพ, บร, รณ, บทความน, ไม, การอ, างอ, งจากแหล, งท, มาใดกร, ณาช, วยปร, บปร, งบทความน, โดยเพ, มการอ, างอ, งแหล, งท, มาท, าเช, อถ, เน, อความท, ไม, แหล, งท, มาอาจถ, กค, ดค, านหร, อลบออก, เร, ยนร, าจะนำสารแม, แบบน, ออกได, อย, างไรและเม, อไร, ในทางทฤษฎ, ความซ, บซ,. bthkhwamniimmikarxangxingcakaehlngthimaidkrunachwyprbprungbthkhwamni odyephimkarxangxingaehlngthimathinaechuxthux enuxkhwamthiimmiaehlngthimaxacthukkhdkhanhruxlbxxk eriynruwacanasaraemaebbnixxkidxyangiraelaemuxir inthangthvsdikhwamsbsxninkarkhanwn exnphibriburn xngkvs NP complete epnklumkhwamsbsxnthiyakthisudinexnphi klawkhuxpyhaid inklumpyha exnphi samarthldrup Reduce maepnpyhain exnphibriburn id aemyngimidrbkarphisucnaetechuxknwaepnklumpyhathiimnacamikhntxnwithithimiprasiththiphaphichaekikhid pyhainklumexnphibriburnsamarthepliynaeplngipmaepnpyhaxuninklumediywkniddwy polynomial time dngnnkarthimikhntxnwithithimiprasiththiphaphsahrbpyhaidpyhahnunginexnphibriburn sngphliherasamarthaekpyhathnghmdinklumexnphiidxyangmiprasiththiphaph klumkhwamsbsxnexnphibriburninbangkhrngthukeriyksn wa NP Caephnphaphxxyelxraesdngkhwamsmphnthkhxngphi exnphi exnphibriburn aelaexnphiaebbyak sahrbthngsxngkrnithiphiethakbexnphi aelaphiimethakbexnphiniyam aekikheracaeriykpyhakartdsinic C waepn exnphibriburn emux C epnpyhaexnphi C epnpyhaexnphiaebbyak nnkkhuxthukpyhainexnphisamarthldrupepn C id withikaraekpyhaexnphibriburn aekikhinkrnithieratxngkaraekpyhaaebbhakhatxbdithisud khxngpyhathiepnexnphibriburn echn txngkarhaklumphrrkhphwkthiihythisudinkraf hnung eramikhwamhwngephiyngnxynidthicahakhatxbaebbdithisudidthukkhrngdwykhntxnwithithimiprasiththiphaph xaccahaidsahrbtwxyangthimikhnadelk odythwipaelweracayxmtxbphidbang sungwithithixaccanamaichmidngtxipni ichkarpraman ephuxhakhatxbthiphisucnidwaimaeyekinipnk ichkhntxnwithithimiprasiththiphaphsahrbbangrupaebbkarkracaytwkhxngxinphut cngictxbechphaakrniphiess ichhiwristik sungcathaihkhntxnwithithanganiddiinhlay krni aetimsamarthphisucnxairidely inbangthixaccaidkhatxbthiaeyekinkwacarbid bthkhwamniyngepnokhrng khunsamarthchwywikiphiediyidodyephimkhxmulekhathungcak https th wikipedia org w index php title exnphibriburn amp oldid 6047505, wikipedia, วิกิ หนังสือ, หนังสือ, ห้องสมุด,
บทความ
, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม
