ผลต่างระหว่างรุ่นของ "ทฤษฎีความซับซ้อนในการคำนวณ"

==ปัญหาการตัดสินใจ==

 

 

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