เหตุใดปัญหาลอการิทึมแยกจึงยาก

เหตุใดปัญหาลอการิทึมแบบไม่ต่อเนื่องจึงถือว่ายาก

คนอื่นถามคำถามเดียวกัน แต่คำตอบจะอธิบายว่ามีการยกกำลังอยู่เท่านั้น $O(\log(n))$ ในขณะที่อัลกอริทึมที่รู้จักเร็วที่สุดในการคำนวณลอการิทึมแบบไม่ต่อเนื่องนั้นอยู่ในนั้น $O(n)$. (ฉันกำลังปัดเศษรายละเอียดเช่นรันไทม์ของแคลคูลัสดัชนีที่นี่)

ที่อื่นที่ฉันอ่าน: "เราคิดว่าลอการิทึมแบบไม่ต่อเนื่องนั้นยากเพราะเป็นเวลากว่า 40 ปีที่ผู้คนฉลาดมากไม่สามารถหาอัลกอริทึมที่รวดเร็วได้"

ตอนนี้ฉันสงสัยว่ามีข้อโต้แย้งที่ดีกว่านี้หรือไม่ คุณอธิบายได้ไหมว่าทำไมลอการิทึมแบบไม่ต่อเนื่องถึงยาก