ในทางคณิตศาสตร์ การทดสอบการสลับที่ของไลท์ ( Light's associativity test)เป็นวิธีการที่คิดค้นโดย เอฟ.ดับบลิว. ไลท์ (FW Light) สำหรับทดสอบว่าการดำเนินการทวิภาคที่กำหนดในเซตจำกัดโดย ตาราง การคูณของเคย์ลีย์ (Cayley multiplication table) นั้น มีการสลับที่ หรือ ไม่ วิธีการตรวจสอบการสลับที่ของการดำเนินการทวิภาคที่ระบุโดยตารางเคย์ลีย์แบบดั้งเดิม ซึ่งเปรียบเทียบผลคูณสองผลที่สามารถสร้างได้จากแต่ละสามองค์ประกอบนั้นยุ่งยาก การทดสอบการสลับที่ของไลท์ช่วยลดความซับซ้อนของงานในบางกรณี (แม้ว่าจะไม่ได้ปรับปรุงเวลาการทำงานในกรณีที่เลวร้ายที่สุดของอัลกอริทึมแบบดั้งเดิม โดยเฉพาะอย่างยิ่งสำหรับเซตที่มีขนาด n ก็ตาม ) ${\displaystyle {\mathcal {O}}\left(n^{3}\right)}$${\displaystyle n}$

ให้การดำเนินการทวิภาค ' · ' ถูกกำหนดในเซตจำกัดAโดยใช้ตารางเคย์ลีย์ เมื่อเลือกสมาชิกa บางตัว ในAจะมีการกำหนดการดำเนินการทวิภาคใหม่สองตัวในAดังต่อไปนี้:

${\displaystyle x\star y=x\cdot (a\cdot y)}$

${\displaystyle x\circ y=(x\cdot a)\cdot y}$

ตารางเคย์ลีย์ของการดำเนินการเหล่านี้ถูกสร้างขึ้นและเปรียบเทียบกัน ถ้าตารางตรงกัน แสดงว่าสำหรับทุกxและyกระบวนการ นี้จะถูกทำซ้ำสำหรับทุกองค์ประกอบของเซตA${\displaystyle x\cdot (a\cdot y)=(x\cdot a)\cdot y}$

ตัวอย่างด้านล่างนี้แสดงให้เห็นถึงการลดความซับซ้อนเพิ่มเติมในขั้นตอนการสร้างและการเปรียบเทียบตาราง Cayley ของการดำเนินการ ' ' และ ' ' ${\displaystyle \star }$${\displaystyle \circ }$

ไม่จำเป็นต้องสร้างตารางเคย์ลีย์ของ ' ' และ ' ' สำหรับทุกองค์ประกอบของAด้วยซ้ำ เพียงแค่เปรียบเทียบตารางเคย์ลีย์ของ ' ' และ ' ' ที่สอดคล้องกับองค์ประกอบในเซตย่อยก่อกำเนิดที่เหมาะสมของA ก็เพียงพอ แล้ว ${\displaystyle \star }$${\displaystyle \circ }$${\displaystyle \star }$${\displaystyle \circ }$

เมื่อการดำเนินการ ' · ' เป็นแบบสลับที่ได้ x y = y x ดังนั้นจึงต้องคำนวณตารางเคย์ลีย์เพียงบางส่วนเท่านั้น เพราะ x x = x x เป็นจริงเสมอ และ x y = x y หมายความว่า y x = y x ${\displaystyle \star }$${\displaystyle \circ }$${\displaystyle \star }$${\displaystyle \circ }$${\displaystyle \star }$${\displaystyle \circ }$${\displaystyle \star }$${\displaystyle \circ }$

เมื่อมีองค์ประกอบเอกลักษณ์ e อยู่แล้ว ไม่จำเป็นต้องรวม e ไว้ในตาราง Cayley เพราะ x y = x y จะเป็นจริงเสมอหากอย่างน้อยหนึ่งใน x และ y เท่ากับ e ${\displaystyle \star }$${\displaystyle \circ }$

พิจารณาการดำเนินการทวิภาค ' · ' ในเซตA = { a , b , c , d , e } ซึ่งกำหนดโดยตารางเคย์ลีย์ต่อไปนี้ (ตารางที่ 1):

เซต { c , e } เป็นเซตก่อกำเนิดสำหรับเซตAภายใต้การดำเนินการทวิภาคที่กำหนดโดยตารางข้างต้น สำหรับ a = e · e , b = c · c , d = c · eดังนั้นจึงเพียงพอที่จะตรวจสอบว่าการดำเนินการทวิภาค ' ' และ ' ' ที่สอดคล้องกับcตรงกัน และการดำเนินการทวิภาค ' ' และ ' ' ที่สอดคล้องกับeตรงกัน ด้วย${\displaystyle \star }$${\displaystyle \circ }$${\displaystyle \star }$${\displaystyle \circ }$

เพื่อตรวจสอบว่าการดำเนินการไบนารี ' ' และ ' ' ที่สอดคล้องกับcตรงกัน ให้เลือกแถวในตารางที่ 1 ที่สอดคล้องกับองค์ประกอบc : ${\displaystyle \star }$${\displaystyle \circ }$

แถวนี้จะถูกคัดลอกไปเป็นแถวหัวตารางของตารางใหม่ (ตารางที่ 3):

ภายใต้หัวข้อaให้คัดลอกคอลัมน์ที่ตรงกันในตารางที่ 1 ภายใต้หัวข้อbให้คัดลอกคอลัมน์ที่ตรงกันในตารางที่ 1 เป็นต้น และสร้างตารางที่ 4 ขึ้นมา

ส่วนหัวของคอลัมน์ในตารางที่ 4 ถูกลบออกแล้ว เพื่อให้ได้ตารางที่ 5:

ตารางเคย์ลีย์ของการดำเนินการไบนารี ' ' ที่สอดคล้องกับองค์ประกอบcแสดงอยู่ในตารางที่ 6 ${\displaystyle \star }$

ตารางที่ 6

${\displaystyle \star }$(ค)	เอ	ข	ค	ง	อี
เอ	เอ	เอ	เอ	ง	ง
ข	เอ	ค	ข	ง	ง
ค	เอ	ข	ค	ง	ง
ง	ง	ง	ง	เอ	เอ
อี	ง	อี	อี	เอ	เอ

ถัดไป ให้เลือก คอลัมน์ cของตารางที่ 1:

คัดลอกคอลัมน์นี้ไปยังคอลัมน์ดัชนีเพื่อสร้างตารางที่ 8:

คัดลอกแถวที่ตรงกันในตารางที่ 1 เทียบกับรายการดัชนีa ในตารางที่ 8 คัดลอกแถวที่ตรงกันในตารางที่ 1 เทียบกับรายการดัชนี b เป็นต้น และสร้างตารางที่ 9 ขึ้นมา

ข้อมูลในคอลัมน์แรกของตารางที่ 9 ถูกลบออกแล้ว เพื่อให้ได้ตารางที่ 10:

ตารางเคย์ลีย์ของการดำเนินการไบนารี ' ' ที่สอดคล้องกับองค์ประกอบcแสดงอยู่ในตารางที่ 11 ${\displaystyle \circ }$

ตารางที่ 11

${\displaystyle \circ }$(ค)	เอ	ข	ค	ง	อี
เอ	เอ	เอ	เอ	ง	ง
ข	เอ	ค	ข	ง	ง
ค	เอ	ข	ค	ง	ง
ง	ง	ง	ง	เอ	เอ
อี	ง	อี	อี	เอ	เอ

สามารถตรวจสอบได้ว่าค่าในเซลล์ต่างๆ ในตารางที่ 6 ตรงกับค่าในเซลล์ที่สอดคล้องกันของตารางที่ 11 ซึ่งแสดงให้เห็นว่าx · ( c · y ) = ( x · c ) · yสำหรับทุกxและyในAหากมีความคลาดเคลื่อนใดๆ ก็จะไม่เป็นความจริงที่ว่าx · ( c · y ) = ( x · c ) · yสำหรับทุกxและyในA

สามารถตรวจสอบได้ ว่าx · ( e · y ) = ( x · e ) · yสำหรับทุกxและyในAในลักษณะเดียวกัน โดยการสร้างตารางต่อไปนี้ (ตารางที่ 12 และตารางที่ 13):

ตารางที่ 12

${\displaystyle \star }$( e )	เอ	ข	ค	ง	อี
เอ	ง	ง	ง	เอ	เอ
ข	ง	ง	ง	เอ	เอ
ค	ง	ง	ง	เอ	เอ
ง	เอ	เอ	เอ	ง	ง
อี	เอ	เอ	เอ	ง	ง

ตารางที่ 13

${\displaystyle \circ }$( e )	เอ	ข	ค	ง	อี
เอ	ง	ง	ง	เอ	เอ
ข	ง	ง	ง	เอ	เอ
ค	ง	ง	ง	เอ	เอ
ง	เอ	เอ	เอ	ง	ง
อี	เอ	เอ	เอ	ง	ง

ไม่จำเป็นต้องสร้างตารางเคย์ลีย์ (ตารางที่ 6 และตารางที่ 11) ของการดำเนินการไบนารี ' ' และ ' ' เพียงแค่คัดลอกคอลัมน์ที่ตรงกับส่วนหัวc ในตารางที่ 1 ไปยังคอลัมน์ดัชนีในตารางที่ 5 และสร้างตารางต่อไปนี้ (ตารางที่ 14) แล้วตรวจสอบว่า แถว aของตารางที่ 14 เหมือนกับ แถว aของตารางที่ 1 แถว bของตารางที่ 14 เหมือนกับ แถว bของตารางที่ 1 เป็นต้น ทำซ้ำเช่นนี้โดยมีการ เปลี่ยนแปลงตามความเหมาะสมสำหรับองค์ประกอบทั้งหมดของเซตก่อกำเนิดA${\displaystyle \star }$${\displaystyle \circ }$

สามารถเขียนซอฟต์แวร์คอมพิวเตอร์ เพื่อดำเนินการทดสอบความสัมพันธ์ของ Light ได้ Kehayopulu และ Argyris ได้พัฒนาโปรแกรมดังกล่าว สำหรับMathematica ^{[ 1 ]}

การทดสอบความสัมพันธ์ของ Light สามารถขยายเพื่อทดสอบความสัมพันธ์ในบริบททั่วไปได้^{[ 2 ] [ 3 ]}

ให้T = { t , t , , t ​​} เป็นแมกมาซึ่งการดำเนินการถูกแทนด้วยการวางติดกันให้X = { x , x , , x } เป็นเซต ให้มีฟังก์ชันจากผลคูณคาร์ทีเซียนT × XไปยังXซึ่งแทนด้วย ( t , x ) ↦ txและกำหนดให้ต้องทดสอบว่าฟังก์ชันนี้มีคุณสมบัติหรือไม่ ${\displaystyle \ldots }$${\displaystyle \ldots }$

( st ) x = s ( tx ) สำหรับทุกs , tในT และทุกxในX

สามารถใช้การขยายความทั่วไปของการทดสอบการสลับที่ของ Light เพื่อตรวจสอบว่าคุณสมบัติข้างต้นเป็นจริงหรือไม่ ในสัญลักษณ์ทางคณิตศาสตร์ การขยายความทั่วไปมีดังนี้: สำหรับแต่ละtในTให้L ( t ) เป็น เมทริกซ์ m × nขององค์ประกอบXซึ่งแถวที่ i คือ

( ( t t ) x , ( t t ) x , , ( t t ) x ) สำหรับi = 1, , m${\displaystyle \ldots }$${\displaystyle \ldots }$

และให้R ( t ) เป็น เมทริกซ์ขนาด m × nขององค์ประกอบXโดยที่องค์ประกอบในคอลัมน์ที่jคือ

( t ( tx ), t ( tx ), , t ​​( tx ) ) สำหรับj = 1, , n .${\displaystyle \ldots }$${\displaystyle \ldots }$

ตามการทดสอบแบบทั่วไป (ของเบดนาเร็ก) คุณสมบัติที่จะตรวจสอบจะเป็นจริงก็ต่อเมื่อL ( t ) = R ( t ) สำหรับทุกtในT เท่านั้น เมื่อX = Tการทดสอบของเบดนาเร็กจะลดลงเหลือการทดสอบของไลท์

มีอัลกอริทึมแบบสุ่มโดย Rajagopalan และSchulmanเพื่อทดสอบความสัมพันธ์ในเวลาที่แปรผันตามขนาดของอินพุต (วิธีนี้ยังใช้ได้กับการทดสอบเอกลักษณ์อื่นๆ บางอย่างด้วย) โดยเฉพาะอย่างยิ่ง เวลาในการทำงานคือสำหรับตารางและความน่าจะเป็นของข้อผิดพลาดอัลกอริทึมสามารถปรับเปลี่ยนเพื่อสร้างสามสิ่งสำหรับซึ่งมีอยู่หนึ่งอย่าง ในเวลา^{[ 4 ]}${\displaystyle O(n^{2}\log {\frac {1}{\delta }})}$${\displaystyle n\times n}$${\displaystyle \delta }$${\displaystyle \langle a,b,c\rangle }$${\displaystyle (ab)c\neq a(bc)}$${\displaystyle O(n^{2}\log n\cdot \log {\frac {1}{\delta }})}$