ทฤษฎีเกี่ยวกับความซับซ้อนในการคำนวณ จะสนใจกลุ่มของปัญหาการตัดสินใจใช่หรือไม่?
ส่วนใหญ่แล้ว ทฤษฎีเกี่ยวกับความซับซ้อนในการคำนวณ จะสนใจกลุ่มของปัญหาการตัดสินใจ. ซึ่งปัญหาที่อยู่ในกลุ่มนี้ จะมีคำตอบเพียงสองแบบก็คือ "ใช่" และ "ไม่ใช่" ยกตัวอย่างเช่นปัญหาที่ถามว่าจำนวนหนึ่ง ๆ เป็นจำนวนเฉพาะหรือไม่. ปัญหาในกลุ่มนี้อาจมองได้อีกแบบหนึ่งก็คือ มองเป็น ภาษา ซึ่งเป็นเซตของสตริงความยาวจำกัด. สำหรับปัญหาการตัดสินใจปัญหาหนึ่ง เราอาจจะมองว่า มันคือภาษาที่มีสมาชิกในเซตเป็นตัวอย่างปัญหาทั้งหมดที่ให้คำตอบเป็น "ใช่". ทฤษฎีความซับซ้อนในการคำนวณ () เป็นสาขาหนึ่งของทฤษฎีการคำนวณ ที่มุ่งเน้นไปในการวิเคราะห์เวลาและเนื้อที่สำหรับการแก้ปัญหาหนึ่ง ๆ โดยปกติแล้วคำว่า "เวลา" ที่เราพูดถึงนั้น จะเป็นการนับจำนวนขั้นตอนที่ใช้ในการแก้ปัญหา ส่วนในเรื่องของ "เนื้อที่" เราจะพิจารณาเนื้อที่ ๆ ใช้ในการทำงานเท่านั้น (ไม่นับเนื้อที่ ๆ ใช้ในการเก็บข้อมูลป้อนเข้า). ในบางกรณีเราอาจจะสนใจการวิเคราะห์ปริมาณอื่น ๆ ที่นอกเหนือไปจากพื้นที่กับเวลา ยกตัวอย่างเช่น ในการประมวลผลแบบขนาน เราอาจจะวิเคราะห์ว่าต้องใช้หน่วยประมวลผลกี่ตัวในการแก้ปัญหาที่กำหนด. ทฤษฎีความซับซ้อนต่างจาก ทฤษฎีการคำนวณได้ ที่จะเน้นไปในการวิเคราะห์ว่าปัญหาสามารถแก้ได้หรือไม่ โดยไม่สนใจทรัพยากรที่ใช้ในการแก้ปัญหา กลุ่มความซับซ้อน พี และ เอ็นพี ทฤษฎีความซับซ้อนในการคำนวณเป็นส่วนหนึ่งของทฤษฎีการคำนวณที่ศึกษาเกี่ยวกับทรัพยากรที่ต้องการ สำหรับการแก้ปัญหาหนึ่งๆ ทรัพยากรที่สนใจโดยทั่วไปคือเวลา (ต้องใช้การทำงานกี่ขั้นตอนก่อนจะแก้ปัญหาได้) และเนื้อที่ (ต้องใช้เนื้อที่เท่าใดในการแก้ปัญหา)
ในศาสตร์ของทฤษฎีความซับซ้อนของปัญหานั้น ตัวอย่างของปัญหาที่มีคำตอบเป็น "ใช่" มักจะมีความแตกต่างจากตัวอย่างของปัญหาที่มีคำตอบเป็น "ไม่ใช่" เช่น กลุ่มปัญหาเอ็นพี (NP) ประกอบด้วยปัญหาการตัดสินใจทั้งหมดที่ตัวอย่างปัญหาที่มีคำตอบเป็น "ใช่" สามารถตรวจสอบได้อย่างมีประสิทธิภาพ และในทางกลับกัน กลุ่มปัญหาโค-เอ็นพี (co-NP) ประกอบด้วยปัญหาการตัดสินใจที่ตัวอย่างของปัญหาที่มีคำตอบเป็น "ไม่ใช่" สามารถตรวจสอบได้อย่างมีประสิทธิภาพ (คำว่า co ในที่นี้หมายถึง ส่วนกลับ หรือ complement) ซึ่งส่วนกลับของปัญหาหนึ่งก็คือปัญหาเดิมที่มีการสลับตัวอย่างปัญหาที่มีคำตอบคือ "ใช่" กับตัวอย่างปัญหาที่มีคำตอบคือ "ไม่ใช่" ตัวอย่างเช่นปัญหา "IS-PRIME" เป็นส่วนกลับของปัญหา "IS-COMPOSITE" ทฤษฎีบทที่สำคัญอันหนึ่งในด้านทฤษฎีความซับซ้อนในการคำนวณก็คือ ไม่ว่าปัญหาของเราจะยากขนาดไหน เราจะมีปัญหาที่ยากกว่าเสมอ หากเราพิจารณาเฉพาะปัญหาที่สามารถแก้ได้ในเวลาที่เป็นฟังก์ชันพหุนามกับขนาดของข้อมูลป้อนเข้า เราสามารถอธิบายในจุดนี้ได้ด้วยทฤษฎีลำดับชั้นของเวลา () ที่กล่าวไว้ว่า หากเราให้คอมพิวเตอร์ของเราทำงานด้วยเวลาที่มากขึ้น ปัญหาที่เราสามารถแก้ได้ก็จะเพิ่มขึ้น (นั่นก็คือ มีปัญหาที่แก้ไม่ได้ถ้าไม่มีการเพิ่มเวลา) ทฤษฎีลำดับชั้นของเนื้อที่ (space hierarchy theorem) ก็จะกล่าวในเชิงคล้ายกัน เพียงแต่มุ่งความสนใจในเรื่องของเนื้อที่ที่อนุญาตให้มีการใช้งานได้ ปัญหาของพีและเอ็นพีนั้น ทำให้เกิดการสร้างแนวความคิดที่สำคัญมากในการวิจัยสาขานี้ขึ้นมา ซึ่งก็คือแนวความคิดเกี่ยวกับ "ความยาก (hardness)" และ "ความบริบูรณ์ (completeness)" เราจะเรียกเซตของปัญหา X ว่ายากสำหรับเซตของปัญหา Y เมื่อปัญหาทุกปัญหาใน Y สามารถลดรูปอย่างง่ายไปเป็นปัญหาบางปัญหาใน X ได้ (สำหรับรายละเอียดการลดรูป ขอละไว้ในที่นี้) สำหรับคำว่า "ง่าย" ในการลดรูปนั้นจะมีความหมายแตกต่างกันไปขึ้นอยู่กับบริบทที่สนใจ เซตที่เป็น "เซตยาก" ที่เราสนใจมากที่สุดนั้นก็คือเซต เอ็นพีแบบยาก (NP-hard) และคำว่า "ง่าย" ในการลดรูปที่มักจะเป็นที่สนใจก็คือการลดรูปที่ใช้เวลาเป็นฟังก์ชันพหุนามของขนาดของข้อมูลป้อนเข้า ปัญหาที่สำคัญที่สุดในด้านทฤษฎีการคำนวณก็คือปัญหาที่ว่ากลุ่มความซับซ้อนของปัญหาพี และ เอ็นพี เป็นเซตที่เท่ากันหรือไม่ ซึ่งทาง ได้ตั้งรางวัลไว้สำหรับผู้ที่แก้ปัญหานี้ได้เป็นมูลค่าสูงถึง หนึ่งล้านดอลลาร์ (ดูรายละเอียดของปัญหาได้ใน กลุ่มความซับซ้อน พี และ เอ็นพี และ เครื่องจักรออราเคิล) กลุ่มความซับซ้อนของปัญหา เอ็นพี (NP) คือเซตของปัญหาการตัดสินใจที่สามารถแก้ปัญหาได้โดยใช้เครื่องจักรทัวริงเชิงไม่กำหนดในเวลาพหุนาม ปัญหาที่อยู่ในกลุ่มนี้หลายปัญหาเป็นปัญหาที่มนุษย์ต้องการเป็นอย่างมากที่จะแก้ให้ได้อย่างมีประสิทธิภาพ ตัวอย่างของปัญหาในกลุ่มนี้ก็คือ ปัญหาความสอดคล้องแบบบูล (Boolean satisfiability problem) ปัญหาเส้นทางของฮามิลตัน () และ ปัญหาจุดยอดปกคลุม () ปัญหาทุกปัญหาในกลุ่มนี้สามารถตรวจคำตอบได้อย่างมีประสิทธิภาพ ทฤษฎีความซับซ้อนในการคำนวณซึ่งเป็นการศึกษาเกี่ยวกับทรัพยากรทางการคำนวณที่ต้องใช้ในการแก้ปัญหาหนึ่งๆ ได้สร้างแบบจำลองของขั้นตอนวิธีแบบสุ่มให้เป็น"เครื่องจักรทัวริงเชิงความน่าจะเป็น" ทั้งขั้นตอนวิธีลาสเวกัสและมอนติคาร์โลได้ถูกนำมาพิจารณา รวมถึง "คลาสของความซับซ้อน" หลายๆคลาสก็ได้ถูกนำมาศึกษา คลาสของความซับซ้อนแบบสุ่มแบบที่เป็นพื้นฐานที่สุดคือแบบอาร์พี ซึ่งเป็นคลาสของปัญหาการตัดสินใจที่มีขั้นตอนวิธีแบบสุ่ม (หรือเครื่องจักรทัวริงเชิงความน่าจะเป็น) ที่มีประสิทธิภาพ (ทำงานได้ได้ในเวลาโพลิโนเมียล) ที่สามารถตอบว่า "ไม่" ได้ถูกต้องเสมอ และสามารถตอบว่า "ใช่" ได้ โดยมีโอกาสถูกต้องอย่างน้อย 1/2 คลาสส่วนกลับ (complement) ได้แก่โค-อาร์พี และคลาสของปัญหาซึ่งทั้งคำตอบ "ใช่" และ "ไม่" สามารถมีค่าความน่าจะเป็นได้ทั้งคู่ (นั่นคือ ไม่ได้บังคับให้ต้องตอบถูกต้องเสมอ) เรียกว่าซีพีพี (ZPP) สำหรับปัญหาซึ่ง (เชื่อกันว่า) อยู่นอกคลาสนี้ เช่นปัญหาเอ็นพีแบบยาก (ซึ่งแม้แต่ขั้นตอนวิธีแบบสุ่มก็ไม่สามารถแก้ได้) จำเป็นต้องแก้ด้วยขั้นตอนวิธีการประมาณ เราจะนิยาม ความซับซ้อนด้านเวลา (time complexity) สำหรับปัญหาหนึ่ง ๆ ว่าเป็นจำนวนขั้นตอนที่ใช้ในการแก้ตัวอย่างปัญหาสำหรับปัญหานั้น ในรูปฟังก์ชันของขนาดของข้อมูลป้อนเข้า (ซึ่งโดยปกติแล้วเราจะคิดขนาดเป็นบิต) โดยใช้ขั้นตอนวิธีที่มีประสิทธิภาพที่สุด ยกตัวอย่างเช่น ในปัญหา ๆ หนึ่ง สำหรับทุกตัวอย่างปัญหาที่มีขนาด formula_1 บิต ถ้าเราสามารถแก้ตัวอย่างปัญหานี้ได้ภายใน formula_2 ขั้นตอน เราสามารถพูดได้ว่าปัญหานี้มีความซับซ้อนด้านเวลาเป็น formula_2 ซึ่งในการกล่าวถึงเวลาที่ใช้นั้น แน่นอนว่าเครื่องจักร หรือ คอมพิวเตอร์แต่ละเครื่องก็ใช้เวลาในการคำนวณแตกต่างกันไป เพื่อที่จะหลีกเลี่ยงความแตกต่างในจุดนี้ เราจะใช้สัญกรณ์โอใหญ่ (Big O notation) ปัญหาที่มีความซับซ้อนด้านเวลาเป็น formula_4 ในเครื่องคอมพิวเตอร์เครื่องหนึ่ง จะมีความซับซ้อนด้านเวลาเป็น formula_4 บนเครื่องอื่นๆด้วยเช่นกัน จะเห็นได้ว่าสัญกรณ์โอใหญ่ช่วยเราหลีกเลี่ยงการกล่าวถึงรายละเอียด ที่เป็นความแตกต่างระหว่างเครื่องคอมพิวเตอร์