เห็นได้ด้วยเหตุผล(เท่านั้น)

ความจริงของปรากฏการณ์บางอย่าง เรามองไม่ออกได้ด้วยตาเปล่า
แม้เราจะมีเครื่องมือคอมพิวเตอร์ที่เร็วที่สุดถึงขีดจำกัดของฟิสิกส์มาช่วยคำนวณ ก็ยังมองไม่ออก
แม้เราจะเป็นพระเจ้าที่สามารถเฝ้าดูปรากฏการณ์นี้นานจนโลกสลายไป จักรวาลแตกดับไป ก็ยังไม่มีทาง
หรือแม้จะสังเกตด้วยใจที่เป็นกลาง ไม่ยินดียินร้ายตามหลักวิปัสสนา ก็มองไม่ออก ก็เพราะมันไม่เกี่ยวกับจิตใจของเรา

ความจริงของปรากฏการณ์บางอย่าง จะมองเห็นได้ก็ด้วยการใช้เหตุผลที่รัดกุมเท่านั้น

ตัวอย่างหนึ่งของ ปรากฏการณ์ที่ว่า ก็คือการแยกแยะว่า
function f(n) ~ n หรือ f(n) ~ n*alpha(n)
“~” ผมหมายถึงแปรผันตาม (หรือ Theta สำหรับนักคอมพิวเตอร์)

alpha(n) หรือ inverse ackermann function เป็น function ที่ค่อนข้างพิเศษ
คือเมื่อเราใส่เลข n ที่โตขึ้นเข้าไปมากพอ ผลลัพธ์ alpha(n) ก็จะโตขึ้นตามเสมอ
มันคือโตได้ไม่สิ้นสุด ฉะนั้น n*alpha(n) ถึงมากกว่า n ตอนที่ n ใหญ่พอเสมอ
แต่… alpha(n) มันโตช้ามากเกินจินตนาการของมนุษย์

ต่อให้เราเอาจำนวนอะตอมทั้งจักรวาลมารวมกัน มาคูณกับ จำนวนมิลลิวินาทีของระยะเวลาตั้งแต่กำเนิดจักรวาล แล้วเรียกจำนวนนี้ว่า K
ให้ทายว่า alpha(K) เท่ากับเท่าไหร่… คำตอบคือ ไม่เกิน 5
ต่อให้เอาค่า K มาคูนตัวมันเอง alpha(K*K) ก็ไม่เกิน 5
หรือเอามันมายกกำลังตัวมันเอง alpha(K^K) ก็ไม่เกิน 5
แม้ว่าจะมีค่าที่ทำให้ alpha เท่ากับ 6 แต่ค่านั้นใหญ่เกินขอบเขตความคิดของเรา

มันเป็นไปไม่ได้เลยที่เราจะ “สังเกต” ว่า f(n) ~ 6*n หรือ f(n) ~ n*alpha(n) ในจักรวาลแบบที่เราอยู่นี้

มีสิ่งนึงในโปรเจคที่ผมงานทำอยู่ คือผมพยายามวิเคราะห์ function f อันนึงเกี่ยวกับ สิ่งที่เรียกว่า “binary search tree” (นักคอมพิวเตอร์ทุกคนคงรู้จัก)
ว่า f(n) ~ n หรือ f(n) ~ n*alpha(n)
ผมรู้ว่า f(n) โตเร็วไม่เกิน n*alpha(n) และก็ไม่ช้ากว่า n
แต่ผมไม่รู้ที่จริงแล้ว f โตเร็วแค่ไหน กันแน่

ที่มาเขียนเรื่องนี้วันนี้ก็เพราะว่า ค่อนข้างละเหี่ยใจ
ช่วงสามเดือนที่ผ่านมา ผมพยายามพิสูจน์ว่า f(n) ~ n
กี่ไอเดียจากหลายแง่มุมที่เข้ามา(โดยเฉพาะวันนี้) ก็พังไปเสมอ ไม่สามารถพิสูจน์ได้ซะที
ผมอยากจะทำให้ได้ เพราะถ้าทำได้มันจะเป็นเรื่องที่ดีมาก
มันแทบจะตอบคำถามอีกคำถามที่นักวิจัยคิดว่าถูก แต่พิสูจน์ไม่ได้มาแล้ว 30 ปี

และวันนี้ผมคงยอมแพ้ก่อน…
ที่จะพิสูจน์ว่า f(n) ~ n
ความจริง f มันอาจจะโตเร็วกว่า n จริงๆ ก็ได้
แม้ว่าผลการทดลองที่ผ่านมันมันจะดูเหมือนกว่า f(n)~n มาตลอด
แต่ที่จริง มันไม่ได้บอก f มันโตช้ากว่า n*alpha(n) ได้เลย

หลังจากนี้จะเริ่มใหม่ ลองพิสูจน์ว่า f(n) ~ n*alpha(n)
โอ๊สสสสสสสสสสสสสสสส

ปล. นักคอมพิวเตอร์บางคนอาจจะอยากรู้ว่า binary search tree ง่ายๆ มันจะยังมีอะไรให้วิจัยอีกวะ
ผมคิดว่า คำถามที่ผมถามอยูู่ มันก็คล้ายๆ กับการค้นหา the lord of the ring, “one ring to rule them all”.
ผมกำลังค้นหา the lord of binary search tree (BST) algorihm
คร่าวๆ แบบไร้ความรัดกุมก็คือถามว่า มันมี BST algorithm หนึ่งเดียวหรือไม่ ที่แทบจะไม่ช้าไปกว่า BST algorithm อื่นใดเลย ไม่ว่า access sequence จะเป็นอะไร
คำถามนั้นมีชื่อว่า dynamic optimality รายละเอียดเป็นยังไง ตามอ่านดูนะครับ 555