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

ปกติแล้ว ปัญหาการตัดสินใจมักจะเป็นที่สนใจเพราะว่า ปัญหาหลายปัญหามักจะสามารถลดรูปไปเป็นปัญหาในกลุ่มนี้ได้. ยกตัวอย่างเช่น ปัญหา HAS-FACTOR ที่ถามว่า สำหรับจำนวนเต็ม n {\displaystyle n} และ k {\displaystyle k} , จำนวน n {\displaystyle n} มีตัวประกอบเฉพาะที่มีค่าไม่เกิน k {\displaystyle k} หรือไม่? ในที่นี้เราจะแสดงให้เห็นว่า การแก้ปัญหา HAS-FACTOR จะนำไปสู่การแก้ปัญหา FACTORIZE ที่เราได้กล่าวถึงไปแล้ว โดยใช้ทรัพยากรไม่มากกว่ากันนัก สังเกตว่าหากเราสามารถแก้ปัญหา HAS-FACTOR ได้ เราสามารถใช้การค้นหาแบบทวิภาค (binary search) เพื่อหาค่าของ k {\displaystyle k} ที่น้อยที่สุดที่เป็นตัวประกอบของ n {\displaystyle n} และเมื่อเจอจำนวนนั้นแล้ว เราก็จะหารมันทิ้งไป ทำซ้ำไปเรื่อย ๆ จนกระทั่งไม่สามารถทำต่อได้ เราก็จะสามารถหาตัวประกอบเฉพาะทั้งหมดของ n {\displaystyle n} ออกมาได้

ค่อนข้างจะชัดเจนว่าเนื้อที่ที่ใช้ในการแก้ปัญหา FACTORIZE จะไม่มากไปกว่าเนื้อที่ที่ใช้ในการแก้ปัญหา HAS-FACTOR นัก (สำหรับค่า k {\displaystyle k} แต่ละค่าเราสามารถคืนหน่วยความจำที่ใช้ในการทำงานของค่า k {\displaystyle k} ก่อนหน้าได้) สำหรับเวลาที่ใช้ก็เช่นกัน ในการหาตัวประกอบแต่ละตัวเราจะเรียกใช้ HAS-FACTOR ไม่เกิน log ⁡ ( n ) {\displaystyle \log(n)} ครั้ง และจำนวนของตัวประกอบเฉพาะของ n {\displaystyle n} ที่เป็นไปได้ก็ไม่เกิน log ⁡ ( n ) {\displaystyle \log(n)} จำนวน

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

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