ສະ​ມາ​ຊິກ : ເຂົ້າ​ສູ່​ລະ​ບົບ |ຫມັກ​ສະ​ມາ​ຊິກ |ຄວາມ​ຮູ້ Upload
ຄົ້ນ​ຫາ​ສໍາ​ລັບ
ທິດສະດີຄວາມສັບສົນຂອງຄອມພິວເຕີ້ [ປັບ​ປຸງ​ແກ້​ໄຂ ]
ທິດສະດີຄວາມສັບສົນຂອງຄອມພິວເຕີ້ແມ່ນສາຂາຂອງທິດສະດີຂອງການຄິດໄລ່ໃນວິທະຍາສາດຄອມພິວເຕີທິດສະດີທີ່ສຸມໃສ່ການຈໍາແນກບັນຫາດ້ານຄອມພິວເຕີຕາມຄວາມຫຍຸ້ງຍາກຂອງພວກເຂົາແລະການພົວພັນລະຫວ່າງຊັ້ນຮຽນກັບກັນ. ບັນຫາຄອມພິວເຕີແມ່ນຄວາມເຂົ້າໃຈທີ່ວ່າມັນເປັນວຽກງານທີ່ສາມາດແກ້ໄຂໄດ້ໂດຍຄອມພິວເຕີ, ເຊິ່ງທຽບເທົ່າກັບການລະບຸວ່າບັນຫາອາດຈະໄດ້ຮັບການແກ້ໄຂໂດຍການນໍາໃຊ້ກົນຈັກຂອງຂັ້ນຕອນຄະນິດສາດເຊັ່ນ: ວິທີການຄິດໄລ່.
ບັນຫາແມ່ນຖືວ່າມີຄວາມຫຍຸ້ງຍາກໂດຍທໍາມະດາຖ້າການແກ້ໄຂຂອງມັນຮຽກຮ້ອງໃຫ້ມີຊັບພະຍາກອນທີ່ສໍາຄັນ, ເຖິງແມ່ນວ່າວິທີການທີ່ໃຊ້. ທິດສະດີ formalizes intuition ນີ້, ໂດຍນໍາສະເຫນີແບບຈໍາລອງຄະນິດສາດຂອງການຄິດໄລ່ເພື່ອສຶກສາບັນຫາເຫຼົ່ານີ້ແລະ quantifying ຈໍານວນເງິນທີ່ຕ້ອງການເພື່ອແກ້ໄຂໃຫ້ເຂົາເຈົ້າເຊັ່ນ: ເວລາແລະການເກັບຮັກສາ. ມາດຕະການຄວາມສັບສົນອື່ນໆຍັງຖືກນໍາໃຊ້ເຊັ່ນ: ຈໍານວນການສື່ສານ (ໃຊ້ໃນຄວາມສັບສົນໃນການສື່ສານ), ຈໍານວນປະຕູໃນວົງຈອນ (ໃຊ້ໃນຄວາມສັບສົນຂອງວົງຈອນ) ແລະຈໍານວນຂອງໂປເຊດເຊີ (ໃຊ້ໃນຄອມພິວເຕີ້ຂະຫນານ). ຫນຶ່ງໃນບົດບາດຂອງທິດສະດີຄວາມສັບສົນຂອງຄອມພິວເຕີ້ແມ່ນການກໍານົດຂອບເຂດການປະຕິບັດກ່ຽວກັບຄອມພິວເຕີທີ່ສາມາດແລະບໍ່ສາມາດເຮັດໄດ້.
ພາກສະຫນາມທີ່ກ່ຽວຂ້ອງຢ່າງໃກ້ຊິດໃນວິທະຍາສາດຄອມພິວເຕີທິດສະດີແມ່ນການວິເຄາະຂອງສູດແລະທິດສະດີສາມາດເຂົ້າໃຈໄດ້. ຄວາມແຕກຕ່າງທີ່ສໍາຄັນລະຫວ່າງການວິເຄາະຂອງສູດແລະທິດສະດີຄວາມສັບສົນຂອງຄອມພິວເຕີ້ແມ່ນວ່າອະດີດແມ່ນ devoted ກັບການວິເຄາະຈໍານວນຊັບພະຍາກອນທີ່ຕ້ອງການໂດຍລະບົບວິທີການແກ້ໄຂບັນຫາໃນຂະນະທີ່ພາກສະເຫນີຄໍາຖາມທົ່ວໄປກ່ຽວກັບທຸກໆລະບົບທີ່ສາມາດນໍາໃຊ້ໄດ້ ແກ້ໄຂບັນຫາດຽວກັນ. ຫຼາຍທີ່ສຸດ, ທິດສະດີຄວາມສັບສົນຂອງຄອມພິວເຕີ້ພະຍາຍາມຈັດປະເພດບັນຫາທີ່ສາມາດຫຼືບໍ່ສາມາດແກ້ໄຂໄດ້ດ້ວຍຊັບພະຍາກອນຖືກຈໍາກັດຢ່າງຖືກຕ້ອງ. ໃນເວລານັ້ນ, ການຈໍາກັດຂໍ້ກໍານົດກ່ຽວກັບຊັບພະຍາກອນທີ່ມີຢູ່ແມ່ນສິ່ງທີ່ແຕກຕ່າງກັນຈາກຄວາມສັບສົນຂອງຄອມພິວເຕີ້ຈາກທິດສະດີທີ່ສາມາດຄິດໄລ່ໄດ້: ທິດສະດີດ້ານຫລັງບອກວ່າປະເພດຂອງບັນຫາສາມາດເປັນແນວໃດ, ໂດຍວິທີການແກ້ໄຂວິທີການແກ້ໄຂ.
[ລະບົບວິເຄາະ]
1.ບັນຫາຄອມພິວເຕີ
1.1.ຕົວຢ່າງບັນຫາ
1.2.ຕົວແທນບັນຫາທີ່ເກີດຂື້ນ
1.3.ບັນຫາການຕັດສິນໃຈເປັນພາສາທີ່ເປັນທາງການ
1.4.ບັນຫາຂອງບັນຫາ
1.5.ການວັດແທກຂະຫນາດຂອງຕົວຢ່າງ
2.ຕົວແບບເຄື່ອງແລະມາດຕະການສັບຊ້ອນ
2.1.Turing machine
2.2.ແບບເຄື່ອງຈັກອື່ນໆ
2.3.ມາດຕະການສັບຊ້ອນ
2.4.ຄວາມສັບສົນໃນກໍລະນີທີ່ດີທີ່ສຸດ, ທີ່ຮ້າຍແຮງແລະສະເລ່ຍ
2.5.ຂອບເຂດເທິງແລະຕ່ໍາສຸດຄວາມສັບສົນຂອງບັນຫາ
3.ຊັ້ນຮຽນທີ່ສັບສົນ
3.1.ກໍານົດລະດັບຄວາມສັບສົນ
3.2.ຊັ້ນຮຽນຄວາມສັບສົນທີ່ສໍາຄັນ
3.3.ທິດສະດີ Hierarchy
3.4.ການຫຼຸດຜ່ອນ
4.ບັນຫາທີ່ສໍາຄັນທີ່ເປີດ
4.1.P ທຽບກັບບັນຫາ NP
4.2.ບັນຫາໃນ NP ທີ່ບໍ່ຮູ້ວ່າຈະຢູ່ໃນ P ຫຼື NP-complete
4.3.ການແບ່ງແຍກລະຫວ່າງສະລັບສັບຊ້ອນອື່ນໆ
5.Intractability
6.ປະວັດສາດ
[ອັບ​ໂຫຼດ ເພີ່ມ​ເຕີມ ເນື້ອ​ໃນ ]


ລິ​ຂະ​ສິດ @2018 Lxjkh