ความซับซ้อนของอัลกอริทึมคืออะไร?

ความซับซ้อนของอัลกอริทึม (ความซับซ้อนในการคำนวณหรือความซับซ้อนของ Kolmogorov) เป็นแนวคิดพื้นฐานในทั้ง ทฤษฎีความซับซ้อน ใน การคำนวณ และ ทฤษฎีข้อมูลอัลกอริทึม และมีบทบาทสำคัญในการเหนี่ยวนำอย่างเป็นทางการ

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

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

ความซับซ้อนในการคำนวณเป็นแนวคิดที่ใช้บ่อยในวิทยาการคอมพิวเตอร์เชิงทฤษฎีเพื่อกำหนดความยากลำบากในการคำนวณวิธีการแก้ปัญหาทางคณิตศาสตร์และตรรกะ มีคลาสความซับซ้อนมากกว่า 400 คลาสและคลาสเพิ่มเติมจะถูกค้นพบอย่างต่อเนื่อง คำถาม P = NP ที่ มีชื่อเสียงเกี่ยวข้องกับธรรมชาติของสองคลาสที่ซับซ้อนเหล่านี้ ชั้นเรียนที่ซับซ้อนประกอบด้วยปัญหาที่ยากกว่าสิ่งใดที่อาจพบในคณิตศาสตร์จนถึงแคลคูลัส มีปัญหามากมายที่สามารถจินตนาการได้ในทฤษฎีความซับซ้อนในการคำนวณที่จะต้องใช้เวลาในการแก้ไขที่ไม่ จำกัด

ความซับซ้อนของอัลกอริทึมและแนวคิดที่เกี่ยวข้องได้รับการพัฒนาในปี 1960 โดยนักวิจัยหลายสิบคน Andrey Kolmogorov, Ray Solomonoff และ Gregory Chaitin ได้มีส่วนร่วมสำคัญในช่วงปลายยุค 60 ด้วยทฤษฎีข้อมูลอัลกอริทึม หลักการของความยาวข้อความต่ำสุดที่เกี่ยวข้องอย่างใกล้ชิดกับความซับซ้อนของอัลกอริทึมให้มากพื้นฐานของการอนุมานทางสถิติและอุปนัยและการเรียนรู้เครื่อง