คำถาม: ทฤษฎีความซับซ้อนในการคำนวณเป็นสาขาหนึ่งของอะไร?

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

text: ภายหลังจากที่สามารถระบุได้ว่า ปัญหาใดสามารถแก้ได้ และปัญหาใดที่แก้ไม่ได้ เรามักจะเกิดคำถามขึ้นอีกว่าในบรรดาปัญหาที่แก้ได้ ซึ่งเป็นกลุ่มของฟังก์ชันที่คำนวณได้นั้น มีความซับซ้อนอยู่ในระดับใด จุดนี้เป็นความสนใจหลักของ ทฤษฎีความซับซ้อนในการคำนวณ
title: ทฤษฎีความซับซ้อนในการคำนวณ

text: ริชาร์ด คาร์ป (Richard Karp) เป็นนักวิทยาศาสตร์คอมพิวเตอร์ที่มีชื่อเสียงอย่างมากในผลงานวิจัยที่เกี่ยวกับ ขั้นตอนวิธี กับ ทฤษฎีความซับซ้อนในการคำนวณ ปัจจุบันเป็นอาจารย์อยู่ที่มหาวิทยาลัยแคลิฟอร์เนียเบิร์คลีย์ คาร์ปได้รับรางวัลมากมายในสาขาของวิทยาการคอมพิวเตอร์เชิงทฤษฎี แต่รางวัลที่ใหญ่ที่สุดก็คือ รางวัลทัวริง ที่ได้รับในปี 2528
title: ริชาร์ด คาร์ป

text: ในเชิงของ ทฤษฎีความซับซ้อนในการคำนวณ พี เป็นกลุ่มความซับซ้อนที่ประกอบด้วยปัญหาการตัดสินใจที่สามารถหาคำตอบได้ในเวลาที่เป็นฟังก์ชันพหุนามกับขนาดของอินพุต (polynomial time)
title: พี (ความซับซ้อน)

text: เครื่องจักรทัวริง () คือเครื่องจักรนามธรรมที่แอลัน ทัวริงได้คิดค้นขึ้นใน ค.ศ. 1936 (พ.ศ. 2479) เพื่อการนิยามขั้นตอนวิธีหรือ 'กระบวนการเชิงกล' อย่างชัดเจนแบบคณิตศาสตร์ เครื่องจักรทัวริงได้ถูกใช้อย่างแพร่หลายในการศึกษาวิทยาการคอมพิวเตอร์เชิงทฤษฎี โดยเฉพาะในทฤษฎีความซับซ้อนในการคำนวณและทฤษฎีการคำนวณ ข้อปัญหา (thesis) ที่ว่าโมเดลของเครื่องจักรทัวริงนั้นครอบคลุมกระบวนการเชิงกลทั้งหมด ในการคำนวณทางตรรกศาสตร์และคณิตศาสตร์ เป็นที่รู้จักกันในชื่อข้อปัญหาของเชิร์ช-ทัวริง
title: เครื่องทัวริง

text: อารมณ์ (affect) ในที่นี้หมายถึงความรู้สึกเช่นความกลัว ความยินดีสนุกสนาน และความประหลาดใจ
ซึ่งมีอายุสั้นกว่า "พื้นอารมณ์" (mood) และเกิดขึ้นได้อย่างรวดเร็วอย่างไม่ได้ตั้งใจ เป็นปฏิกิริยาต่อสิ่งเร้า
เช่นการอ่านคำว่า "มะเร็งปอด" อาจจะทำให้รู้สึกสยอง 
หรืออ่านคำว่า "ความรักของคุณแม่" อาจทำให้รู้สึกถึงความรักและความอบอุ่น
เมื่อเราใช้อารมณ์ (ความรู้สึกที่เกิดขึ้นเองทันทีโดยไม่ได้คิด) เพื่อตัดสินประโยชน์และความเสี่ยงของเรื่อง ๆ หนึ่ง เรากำลังใช้ฮิวริสติกโดยอารมณ์ 
การใช้ฮิวริสติกโดยอารมณ์สามารถอธิบายว่า ทำไมความสื่อสารที่กระตุ้นอารมณ์ จึงชักชวนใจได้ดีกว่าความที่แสดงความจริง
มีทฤษฎีที่แข่งกันหลายอย่างเกี่ยวกับการตัดสินใจของมนุษย์ ซึ่งต่างกันในประเด็นว่า การใช้ฮิวริสติกถือว่าเป็นการกระทำที่ไม่สมเหตุสมผล (irrational) หรือไม่
ทฤษฎีแนว "ความขี้เกียจทางประชาน" เสนอว่า การใช้ฮิวริสติกเป็นทางลัดที่ช่วยไม่ได้เนื่องจากสมรรถภาพอันจำกัดของสมองมนุษย์
ส่วนทฤษฎีแนว "การประเมินผลที่เป็นไปตามธรรมชาติ" เสนอว่า สมองได้ทำการคำนวณผลที่ซับซ้อนอย่างรวดเร็วและเป็นไปโดยอัตโนมัติเป็นบางอย่างแล้ว
และการตัดสินใจที่เหลือก็เลยใช้กระบวนการทางลัดเหล่านี้ แทนที่จะทำการคำนวณมาตั้งแต่เริ่มต้น
แนวคิดเช่นนี้นำไปสู่ทฤษฎีที่เรียกว่า "attribute substitution" (การทดแทนลักษณะ)
ซึ่งเสนอว่า เราเผชิญหน้ากับปัญหาที่ซับซ้อน โดยวิธีตอบปัญหาคนละปัญหาแต่เกี่ยวเนื่องกัน โดยที่ไม่รู้ว่าตนกำลังใช้วิธีอย่างนี้ 
ส่วนทฤษฎีแนวที่สามเสนอว่า ฮิวริสติกใช้ได้ดีเท่ากับกระบวนการตัดสินใจที่ซับซ้อนกว่านี้ แต่ว่าทำได้เร็วกว่าโดยมีข้อมูลน้อยกว่า
เป็นแนวคิดที่เน้น "ความรวดเร็วและความมัธยัสถ์" ของฮิวริสติก
title: ฮิวริสติกในการประเมินและการตัดสินใจ

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

text: ในศาสตร์ของทฤษฎีความซับซ้อนของปัญหานั้น ตัวอย่างของปัญหาที่มีคำตอบเป็น "ใช่" มักจะมีความแตกต่างจากตัวอย่างของปัญหาที่มีคำตอบเป็น "ไม่ใช่" เช่น กลุ่มปัญหาเอ็นพี (NP) ประกอบด้วยปัญหาการตัดสินใจทั้งหมดที่ตัวอย่างปัญหาที่มีคำตอบเป็น "ใช่" สามารถตรวจสอบได้อย่างมีประสิทธิภาพ และในทางกลับกัน กลุ่มปัญหาโค-เอ็นพี (co-NP) ประกอบด้วยปัญหาการตัดสินใจที่ตัวอย่างของปัญหาที่มีคำตอบเป็น "ไม่ใช่" สามารถตรวจสอบได้อย่างมีประสิทธิภาพ (คำว่า co ในที่นี้หมายถึง ส่วนกลับ หรือ complement) ซึ่งส่วนกลับของปัญหาหนึ่งก็คือปัญหาเดิมที่มีการสลับตัวอย่างปัญหาที่มีคำตอบคือ "ใช่" กับตัวอย่างปัญหาที่มีคำตอบคือ "ไม่ใช่" ตัวอย่างเช่นปัญหา "IS-PRIME" เป็นส่วนกลับของปัญหา "IS-COMPOSITE"
title: ทฤษฎีความซับซ้อนในการคำนวณ

text: ปัญหาของพีและเอ็นพีนั้น ทำให้เกิดการสร้างแนวความคิดที่สำคัญมากในการวิจัยสาขานี้ขึ้นมา ซึ่งก็คือแนวความคิดเกี่ยวกับ "ความยาก (hardness)" และ "ความบริบูรณ์ (completeness)" เราจะเรียกเซตของปัญหา X ว่ายากสำหรับเซตของปัญหา Y เมื่อปัญหาทุกปัญหาใน Y สามารถลดรูปอย่างง่ายไปเป็นปัญหาบางปัญหาใน X ได้ (สำหรับรายละเอียดการลดรูป ขอละไว้ในที่นี้) สำหรับคำว่า "ง่าย" ในการลดรูปนั้นจะมีความหมายแตกต่างกันไปขึ้นอยู่กับบริบทที่สนใจ เซตที่เป็น "เซตยาก" ที่เราสนใจมากที่สุดนั้นก็คือเซต เอ็นพีแบบยาก (NP-hard) และคำว่า "ง่าย" ในการลดรูปที่มักจะเป็นที่สนใจก็คือการลดรูปที่ใช้เวลาเป็นฟังก์ชันพหุนามของขนาดของข้อมูลป้อนเข้า
title: ทฤษฎีความซับซ้อนในการคำนวณ

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

text: การวิเคราะห์ขั้นตอนวิธีเป็นส่วนที่มีความสำคัญของทฤษฎีความซับซ้อนในการคำนวณที่กว้างขึ้น ซึ่งเอื้ออำนวยสำหรับการประมาณการเชิงทฤษฎีสำหรับทรัพยากรที่จำเป็นต้องใช้โดยขั้นตอนวิธีใด ๆ สำหรับใช้ไขปัญหาที่ต้องการคำนวณ การประมาณการนี้ช่วยให้เข้าใจอย่างลึกซึ้งถึงคำสั่งที่มีเหตุผลของการค้นหาประสิทธิภาพของขั้นตอนวิธี
title: การวิเคราะห์ขั้นตอนวิธี

text: กลุ่มความซับซ้อน พี และ เอ็นพี ทฤษฎีความซับซ้อนในการคำนวณเป็นส่วนหนึ่งของทฤษฎีการคำนวณที่ศึกษาเกี่ยวกับทรัพยากรที่ต้องการ สำหรับการแก้ปัญหาหนึ่งๆ ทรัพยากรที่สนใจโดยทั่วไปคือเวลา (ต้องใช้การทำงานกี่ขั้นตอนก่อนจะแก้ปัญหาได้) และเนื้อที่ (ต้องใช้เนื้อที่เท่าใดในการแก้ปัญหา)
title: กลุ่มความซับซ้อน พี และ เอ็นพี

text: หลายครั้งเราจะกล่าวถึงความซับซ้อนด้านเวลาว่าเป็น "เวลาที่ใช้ในการแก้ปัญหา" หรือ "เวลาที่ใช้ในการทำงาน"
title: ทฤษฎีความซับซ้อนในการคำนวณ

text: หมวดหมู่:ทฤษฎีการคำนวณ
title: ทฤษฎีความซับซ้อนในการคำนวณ

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

text: ปัญหาที่สำคัญที่สุดในด้านทฤษฎีการคำนวณก็คือปัญหาที่ว่ากลุ่มความซับซ้อนของปัญหาพี และ เอ็นพี เป็นเซตที่เท่ากันหรือไม่ ซึ่งทาง Clay Mathematics Institute ได้ตั้งรางวัลไว้สำหรับผู้ที่แก้ปัญหานี้ได้เป็นมูลค่าสูงถึง หนึ่งล้านดอลลาร์ (ดูรายละเอียดของปัญหาได้ใน กลุ่มความซับซ้อน พี และ เอ็นพี และ เครื่องจักรออราเคิล)
title: ทฤษฎีความซับซ้อนในการคำนวณ

text: ทฤษฎีบทที่สำคัญอันหนึ่งในด้านทฤษฎีความซับซ้อนในการคำนวณก็คือ ไม่ว่าปัญหาของเราจะยากขนาดไหน เราจะมีปัญหาที่ยากกว่าเสมอ หากเราพิจารณาเฉพาะปัญหาที่สามารถแก้ได้ในเวลาที่เป็นฟังก์ชันพหุนามกับขนาดของข้อมูลป้อนเข้า เราสามารถอธิบายในจุดนี้ได้ด้วยทฤษฎีลำดับชั้นของเวลา (time hierarchy theorem) ที่กล่าวไว้ว่า หากเราให้คอมพิวเตอร์ของเราทำงานด้วยเวลาที่มากขึ้น ปัญหาที่เราสามารถแก้ได้ก็จะเพิ่มขึ้น (นั่นก็คือ มีปัญหาที่แก้ไม่ได้ถ้าไม่มีการเพิ่มเวลา) ทฤษฎีลำดับชั้นของเนื้อที่ (space hierarchy theorem) ก็จะกล่าวในเชิงคล้ายกัน เพียงแต่มุ่งความสนใจในเรื่องของเนื้อที่ที่อนุญาตให้มีการใช้งานได้
title: ทฤษฎีความซับซ้อนในการคำนวณ

text: การพิจารณาว่าปัญหาการตัดสินใจหนึ่งๆ เป็นปัญหาที่มีความซับซ้อนอย่างไรเมื่อเทียบกับปัญหาการตัดสินใจอื่นๆ เป็นประเด็นที่สำคัญในทฤษฎีความซับซ้อนในการคำนวณ ทฤษฎีความซับซ้อนในการคำนวณ จึงได้นิยามศัพท์คำว่าความบริบูรณ์ของปัญหา โดยนิยามว่า
title: ปัญหาการตัดสินใจ

text: เคมีการคำนวณ () เป็นสาขาหนึ่งของเคมีทฤษฎี (theoretical chemistry) มีความคาบเกี่ยวกันระหว่างวิทยาศาสตร์คอมพิวเตอร์ (computer science) วิชาเคมี (chemistry) วิชาฟิสิกส์ และวิชาคณิตศาสตร์วัตถุประสงค์หลักก็คือการใช้แนวคิดทางทฤษฎีที่พิสูจน์ได้ทางฟิสิกส์และเคมีมาออกแบบหรือสร้างระบบจำลองที่มีประสิทธิภาพ ยกตัวอย่างเช่น ระบบจำลองของแข็ง ระบบจำลองดีเอ็นเอ ระบบจำลองโปรตีน เป็น้ตน ซึ่งในการประมาณการ (approximation) ทางคณิตศาสตร์จะใช้โปรแกรมการคำนวณ (computer program) มาคำนวณ เนื่องจากมีความซับซ้อนและความยุ่งยากทางคณิตศาสตร์มากเกินกว่าที่มนุษย์จะกระทำได้ ซึ่งคอมพิวเตอร์สมรรถนะสูงนี้เองที่เป็นเครื่องมือที่ช่วยให้นักเคมีคำนวณลดระยะเวลาในการ simulation ลงอย่างมากอีกด้วย สำหรับสิ่งที่ต้องการจะศึกษาก็มีปลายรูปแบบแตกต่างกันไป ขึ้นกับระบบนั้น ๆ โดยส่วนมากจะใช้คำนวณหรือศึกษาคุณสมบัติของโมเลกุล (molecule) เช่น
title: เคมีการคำนวณ

text: เราจะนิยาม ความซับซ้อนด้านเวลา (time complexity) สำหรับปัญหาหนึ่ง ๆ ว่าเป็นจำนวนขั้นตอนที่ใช้ในการแก้ตัวอย่างปัญหาสำหรับปัญหานั้น ในรูปฟังก์ชันของขนาดของข้อมูลป้อนเข้า (ซึ่งโดยปกติแล้วเราจะคิดขนาดเป็นบิต) โดยใช้ขั้นตอนวิธีที่มีประสิทธิภาพที่สุด ยกตัวอย่างเช่น ในปัญหา ๆ หนึ่ง สำหรับทุกตัวอย่างปัญหาที่มีขนาด n {\displaystyle n} บิต ถ้าเราสามารถแก้ตัวอย่างปัญหานี้ได้ภายใน n 2 {\displaystyle n^{2}} ขั้นตอน เราสามารถพูดได้ว่าปัญหานี้มีความซับซ้อนด้านเวลาเป็น n 2 {\displaystyle n^{2}} ซึ่งในการกล่าวถึงเวลาที่ใช้นั้น แน่นอนว่าเครื่องจักร หรือ คอมพิวเตอร์แต่ละเครื่องก็ใช้เวลาในการคำนวณแตกต่างกันไป เพื่อที่จะหลีกเลี่ยงความแตกต่างในจุดนี้ เราจะใช้สัญกรณ์โอใหญ่ (Big O notation) ปัญหาที่มีความซับซ้อนด้านเวลาเป็น O ( n 2 ) {\displaystyle O(n^{2})} ในเครื่องคอมพิวเตอร์เครื่องหนึ่ง จะมีความซับซ้อนด้านเวลาเป็น O ( n 2 ) {\displaystyle O(n^{2})} บนเครื่องอื่นๆด้วยเช่นกัน จะเห็นได้ว่าสัญกรณ์โอใหญ่ช่วยเราหลีกเลี่ยงการกล่าวถึงรายละเอียด ที่เป็นความแตกต่างระหว่างเครื่องคอมพิวเตอร์
title: ทฤษฎีความซับซ้อนในการคำนวณ

text: ความตื่นตัวในการพัฒนาทฤษฎีความอลวนนี้ เกิดขึ้นในช่วงกลางของศตวรรษที่ 20 เมื่อเป็นที่ประจักษ์ว่า ทฤษฎีของระบบเชิงเส้นนั้นไม่สามารถใช้อธิบายพฤติกรรมบางอย่าง แม้กระทั่งพฤติกรรมของระบบที่ไม่ซับซ้อนอย่าง แมพลอจิสติก (Logistic map) อีกปัจจัยหนึ่งที่ส่งผลให้พัฒนาการของทฤษฎีความอลวนเป็นไปอย่างรวดเร็วก็คือ คอมพิวเตอร์ การคำนวณในทฤษฎีความอลวนนั้น โดยส่วนใหญ่จะมีลักษณะที่เป็นการคำนวณค่าแบบซ้ำ ๆ จากสูตรคณิตศาสตร์ และสามารถใช้คอมพิวเตอร์ช่วยในการคำนวณได้อย่างมีประสิทธิภาพ
เอ็ดเวิร์ด ลอเรนซ์ () เป็นผู้ริเริ่มบุกเบิกทฤษฎีความอลวน เขาได้สังเกตพฤติกรรมความอลวน ในขณะทำการทดลองทางด้านการพยากรณ์อากาศ ในปี ค.ศ. 1961 ลอเรนซ์ใช้คอมพิวเตอร์ซิมูเลชันแบบจำลองสภาพอากาศ ซึ่งในการคำนวณครั้งถัดมาเขาไม่ต้องการเริ่มซิมูเลชันจากจุดเริ่มต้นใหม่ เพื่อประหยัดเวลาในการคำนวณ เขาจึงใช้ข้อมูลในการคำนวณก่อนหน้านี้เพื่อเป็นค่าเริ่มต้น ปรากฏว่าค่าที่คำนวณได้มีความแตกต่างไปจากเดิมอย่างสิ้นเชิง เขาพบว่าสาเหตุเกิดจากการปัดเศษ ของค่าที่พิมพ์ออกมา จากค่าที่ใช้ในคอมพิวเตอร์ ซึ่งมีค่าน้อยมาก แต่สามารถนำไปสู่ความแตกต่างอย่างมากมาย เรียกว่า ไวต่อสภาวะเริ่มต้น
title: ทฤษฎีความอลวน

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

text: การวิเคราะห์เชิงคำนวณของการเรียนรู้ของเครื่อง และการวัดประสิทธิภาพการเรียนรู้ เป็นอีกสาขาหนึ่งทางวิทยาศาสตร์คอมพิวเตอร์สายทฤษฎีที่รู้จักกันในชื่อ ทฤษฎีการเรียนรู้เชิงคำนวณ อย่างไรก็ตาม ทฤษฎีก็ไม่สามารถรับประกันประสิทธิภาพของอัลกอริทึมได้เพราะข้อมูลนั้นมีจำกัดและอนาคตมีความไม่แน่นอน แต่ทฤษฎีก็สามารถบอกขอบเขตบนความน่าจะเป็นได้ว่า ประสิทธิภาพน่าจะอยู่ในช่วงใด นอกจากนี้ นักวิทยาศาสตร์ด้านนี้ยังได้ศึกษาดูต้นทุนทางเวลาและความเป็นไปได้ของการเรียนรู้ของเครื่องด้วย โดยการคำนวณที่ถือว่าเป็นไปได้ในการเรียนรู้นั้นจะต้องสามารถเรียนรู้ได้ในเวลาโพลิโนเมียล
title: การเรียนรู้ของเครื่อง

text: กลุ่มความซับซ้อนของปัญหา พี (P) คือเซตของปัญหาการตัดสินใจที่สามารถหาคำตอบได้ ในเวลาที่เป็นฟังก์ชันพหุนามของขนาดข้อมูลป้อนเข้า ด้วยเครื่องจักรทัวริงเชิงกำหนด (deterministic turing machine) นิยามนี้สอดคล้องกับแนวคิดของปัญหาที่สามารถหาคำตอบได้อย่างมีประสิทธิภาพ
title: ทฤษฎีความซับซ้อนในการคำนวณ

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

text: การลดรูปที่กล่าวมาทั้งหมดเป็นการลดรูปจากปัญหาหนึ่งไปอีกปัญหาหนึ่ง นอกจากนี้ยังมีการลดรูประหว่างปัญหาเดียวกันที่เรียกว่า การลดรูปตัวเอง (Self-reduction) และการลดรูปตัวเองแบบสุ่ม (Random self-reduction) ซึ่งมีประโยชน์อย่างมากในการศึกษาทฤษฎีความซับซ้อนในการคำนวณเช่นกัน
title: การลดรูป (ความซับซ้อน)

text: การลดรูปในเชิงของทฤษฎีความซับซ้อนในการคำนวณนั้นมีมากมายหลายรูปแบบ แต่ละแบบจะนำมาใช้ในแง่ที่แตกต่างกัน แล้วแต่ว่าเรากำลังสนใจปัญหาแบบใด เช่นถ้าเราสนใจปัญหาของการนับ เราจะบอกว่าการนับจำนวนในเซ็ต A ลดรูปไปเป็นการนับจำนวนในเซ็ต B รูปแบบของการลดรูปที่เรานำมาใช้ก็ควรเป็นการลดรูปที่ไม่ทำให้จำนวนนั้นเปลี่ยนไป การลดรูปแบบนี้เรียกว่า (parsimonious reduction) การลดรูปที่มักจะใช้กันบ่อยๆก็คือทั้งสามแบบที่กล่าวมานี้เป็นการลดรูปแบบใช้เวลาเป็นพหุนามกับขนาดของอินพุต และถูกสร้างขึ้นมาเพื่อใช้นิยามความยากของเอ็นพี การลดรูปคุกจะมีลักษณะเหมือนกับการลดรูปทัวริง (Turing reduction) ในเชิงของทฤษฎีการคำนวณได้ (ที่ไม่สนใจว่าเวลาในการทำงานที่ใช้เป็นเท่าไร แต่จะเน้นที่การคำนวณได้เท่านั้น) การลดรูปคาร์ปจะเหมือนกับการลดรูปแบบเอ็ม (m-reduction or many-to-one reduction)
title: การลดรูป (ความซับซ้อน)

text: ปัญหาพีและเอ็นพีเป็นปัญหาสำคัญทางวิทยาการคอมพิวเตอร์และทฤษฎีการคำนวณ ซึ่งศึกษาความซับซ้อนในการคำนวณ ระหว่างกลุ่มความซับซ้อนพี (P) ซึ่งเป็นกลุ่มปัญหาที่สามารถ "ค้นหา" (search) คำตอบได้ในเวลาพหุนาม กับกลุ่มความซับซ้อนเอ็นพี (NP) ซึ่งเป็นกลุ่มปัญหาที่สามารถ "ตรวจสอบ" (verify) คำตอบได้ในเวลาพหุนาม 
title: ปัญหารางวัลมิลเลนเนียม

text: การประยุกต์ใช้คอมพิวเตอร์กับงานระบบควบคุม: พัฒนาการของคอมพิวเตอร์ มีส่วนสำคัญในการพัฒนาทฤษฎีต่าง ๆ ของระบบควบคุม เนื่องจากทำให้สามารถสร้างอุปกรณ์ควบคุมที่สามารถทำงานซับซ้อนได้ รวมทั้งการใช้คอมพิวเตอร์ช่วยคำนวณในการออกแบบกฎของการควบคุม ดังนั้นจึงมีการพัฒนาระบบควบคุมแบบต่าง ๆ ขึ้นอย่างมากมาย
title: ทฤษฎีระบบควบคุม

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