สำหรับ string $s$ และ $t$ ใดๆที่ไม่จำเป็นต้องต่างกันก็ได้ ให้ $v$ เป็น string ที่ยาวที่สุดที่ทำให้ $s=uv$ และ $t=vw$ โดย string $u$ และ $w$ ไม่เป็น empty string เราจะเรียก $|v|$ ว่า overlap ระหว่าง $s$ และ $t$ แทนได้ด้วย $ov(s,t)$ เราจะเรียก $u$ ว่าเป็น prefix ของ $s$ เทียบกับ $t$ แทนได้ด้วย $pref(s,t)$ และจะเรียก $|pref(s,t)|=|u|$ ว่าเป็น distance จาก $s$ ไปยัง $t$ แทนด้วย $d(s,t)$

หากเรามี string $s_(1),s_(2),...,s_(r)$ เราจะให้นิยาม string $s=<s_(1),...,s_(r)>$ ว่าเป็น string $pref(s_(1),s_(2))pref(s_(2),s_(3))* * *pref(s_(r-1),s_(r))s_(r)$ ซึ่งก็คือ string ที่สั้นที่สุดที่มี $s_(1),s_(2),...,s_(r)$ ปรากฏในนั้นตามลำดับ เราจะให้ $first(s)=s_(1)$ และ $last(s)=s_(r)$ จะเห็นว่าเราสามารถมองปัญหาในรูปของการสับเปลี่ยนลำดับของ string โดยจะมีอย่างน้อยหนึ่งลำดับที่ทำให้ได้ superstring ที่มีความยาวน้อยที่สุด

หากเปรียบเทียบปัญหาของเรากับปัญหาอื่นที่รู้จักกันดี คือ TSP ( Traveling Salesman Problem ) เราสามารถเชื่อมโยง SSP กับ TSP ในกรณีที่กราฟมีทิศทางได้ เราสามารถสร้างกราฟมีทิศทางและน้ำหนัก $G_(S)$ จาก $S$ โดยให้ $G_(S)=(V,E,d)$ มีจุดยอด $m$ จุด $V={1,...,m}$ และมีเส้นเชื่อม $m^(2)$ เส้น $E={(i,j):1<=i,j<=m}$ และให้เส้นเชื่อม $(i,j)$ มีน้ำหนักเท่ากับ $d(i,j)=d(s_(i),s_(j))$

หากให้ $TSP(G_(S))$ เป็นน้ำหนักรวมของ Hamiltonian cycle ที่มีน้ำหนักน้อยที่สุดของ $G_(S)$ จะได้ว่า $TSP(G_(S))<=OPT(S)$ เนื่องจากการวน superstring ใดๆให้ได้ Hamiltonian cycle อาจจะมีการซ้อนทับระหว่าง string ตัวแรกและตัวสุดท้ายซึ่งจะทำให้น้ำหนักของ Hamiltonian cycle น้อยลงกว่าความยาวเต็มๆของ superstring นั้น

แต่เนื่องจาก TSP ก็เป็นปัญหาที่ยากอยู่เช่นเดียวกัน เราจึงคิดเชื่อมโยงกับปัญหาอื่นที่ง่ายกว่า สามารถแก้ได้ใน Polynomial time ซึ่งก็คือ CCP ( Cycle Cover Problem ) ซึ่งต้องการจะแบ่งกราฟเป็น cycle ย่อยๆ โดยที่ทุกๆจุดยอดจะอยู่ในหนึ่ง cycle เสมอ และให้ผมรวมของน้ำหนักของทุกๆ cycle น้อยที่สุด หากให้ $CYC(G_(S))$ เป็นน้ำหนักของ minimum cycle cover ของกราฟ $G_(S)$ เราจะได้ว่า $CYC(G_(S))<=TSP(G_(S))<=OPT(S)

คราวหน้าเราจะใช้ความรู้ตรงนี้ เพื่อที่จะแสดงและพิสูจน์ $4*OPT(S)$ Approximation Algorithm ให้เห็นกัน

วันนี้จะขอเปิดหัวข้อใหม่ ซึ่งเป็นหัวข้อที่ผมกำลังศึกษาอยู่ เลยอยากมาเขียนไว้ให้ดูกันและเพื่อความเข้าใจของตัวผมเองด้วย เป็นเรื่องเกี่ยวกับ SSP: Shortest Superstring Problem.

Problem: String ในที่นี้จะหมายถึงสายอักขระ หรือก็คือลำดับของอักขระ (Character) สำหรับตัวปัญหาก็คือ หากเรามีเซตของ string หลายๆตัว เราต้องการจะหา string หนึ่งตัวที่ครอบคลุม string ทุกตัวในเซตนั้น โดยมีความยาวสั้นที่สุดที่เป็นไปได้ จะทำอย่างไร?

ปัญหานี้รู้กันอยู่ว่าเป็นปัญหาประเภท NP-hard การค้นคว้าวิจัยจึงมุ่งไปที่การแก้ปัญหาแบบ Approximationซึ่งเราจะค่อยๆติดตามไป

Preliminaries: ให้ $S={s_(1),...,s_(m)}$ เป็นเซตของ string โดยเราสมมติให้ $S$ เป็น substring-free คือไม่มี $s_(i)inS$ เป็น substring ของ string $s_(j)inS$ เมื่อ $i!=j$
เราจะเรียก string $s$ ว่าเป็นcommon superstring ของ $S$ ถ้าสำหรับแต่ละ $s_(i)inS$, $s$ สามารถเขียนเป็น $u_(i)s_(i)v_(i)$ สำหรับบาง $u_(i)$,$s_(i)$ เราจะให้ $n=OPT(S)$ เป็นความยาวของ common superstring ที่สั้นที่สุดของ $S$ จุดมุ่งหมายของเราคือจะหา common superstring ของ $S$ ที่มีความยาวใกล้ $n$ ให้มากที่สุดเท่าที่ทำได้

เอาไว้แค่นี้ก่อนดีกว่า ใครคิดวิธีดีๆออก ผมก็น้อมรับข้อเสนอครับ

วันนี้จะเสนอวิธีพิสูจน์พื้นฐานอีกวิธี คือ การพิสูจน์โดยหาข้อขัดแย้ง ( Proof by contradiction ) แนวคิดก็คือ หากเราต้องการพิสูจน์ทฤษฎีหนึ่งโดยหาข้อขัดแย้ง เราจะเริ่มต้นด้วยการสมมติให้ทฤษฎีนั้นไม่เป็นจริงก่อน และแสดงว่าการสมมติแบบนี้จะนำไปสู่ข้อขัดแย้งที่ไม่เป็นจริง ดังนั้นทฤษฎีนี้จะไม่เป็นจริงไม่ได้ จึงได้ว่าทฤษฎีนี้เป็นจริง

ลองดูจากทฤษฎีต่อไปนี้ ( หวังว่าคราวนี้จะไม่ยากไปนะ )

Theorem : ไม่มีจำนวนตรรกยะใดเป็นคำตอบของสมการ $x^3+x+1=0$

Proof : สมมติให้มีจำนวนตรรกยะ $s$ เป็นคำตอบของสมการ $x^3+x+1=0$ เนื่องจาก $s$ เป็นจำนวนตรรกยะ จึงสามารถเขียนเป็นเศษส่วนได้ ให้ $s=p/q$ โดยเป็นเศษส่วนอย่างต่ำแล้ว และ $q!=0$ เราจะได้ว่า
$p^3/q^3+p/q+1=0$
เมื่อคูณทั้งสมการด้วย $q^3$ จะได้
$p^3+p*q^2+q^3=0$
เราจะแบ่งเป็นสี่กรณีที่เป็นไปได้
1. ทั้ง $p$ และ $q$ เป็นจำนวนคี่ จะได้ว่าทั้ง $p^3$, $p*q^2$, และ $q^3$ เป็นจำนวนคี่ทั้งสิ้น ดังนั้น $p^3+p*q^2+q^3$ เป็นจำนวนคี่ ซึ่งไม่เท่ากับ $0$ แน่นอน เกิดข้อขัดแย้ง
2. $p$ เป็นจำนวนคี่ และ $q$ เป็นจำนวนคู่ จะได้ $p^3$ เป็นจำนวนคี่, $p*q^2$ และ $q^3$ เป็นจำนวนคู่ เมื่อบวกกันก็เป็นจำนวนคี่ซึ่งไม่มีทางเท่ากับ $0$ ได้ เกิดข้อขัดแย้งเช่นกัน
3. $p$ เป็นจำนวนคู่ และ $q$ เป็นจำนวนคี่ จะได้ $p^3$ และ $p*q^2$ เป็นจำนวนคู่ และ $q^3$ เป็นจำนวนคี่ เมื่อบวกกันก็ได้จำนวนคี่ เกิดข้อขัดแย้งเหมือนเดิม
4. ทั้ง $p$ และ $q$ เป็นจำนวนคู่ เราจะได้ว่า $p/q$ มีตัวประกอบร่วม สามารถตัดทอนได้ ซึ่งแสดงว่าไม่เป็นเศษส่วนอย่างต่ำ ขัดแย้งอยู่ดี

ทั้งสี่กรณีสรุปได้ว่า ข้อสมมติที่เราตั้งไว้ตอนต้นนั้นไม่เป็นจริง ดังนั้น จึงไม่มีจำนวนตรรกยะใดเป็นคำตอบของสมการ $x^3+x+1=0$