อ่าน 2 นาที
ฟังก์ชันบูลีนสมดุล
ในคณิตศาสตร์และวิทยาศาสตร์คอมพิวเตอร์ฟังก์ชันบูลีนที่สมดุลคือฟังก์ชันบูลีนที่มีเอาต์พุตเป็น0เท่ากับ1ในชุดอินพุตซึ่งหมายความว่าสำหรับสตริงบิตอินพุตแบบสุ่มสม่ำเสมอ...
ฟังก์ชันบูลีนสมดุล
ในคณิตศาสตร์และวิทยาศาสตร์คอมพิวเตอร์ฟังก์ชันบูลีนที่สมดุลคือฟังก์ชันบูลีนที่มีเอาต์พุตเป็น0เท่ากับ1ในชุดอินพุตซึ่งหมายความว่าสำหรับสตริงบิตอินพุตแบบสุ่มสม่ำเสมอ ความน่าจะเป็นที่จะได้1คือ 1/2 [ 1 ]
ตัวอย่าง
ตัวอย่างของฟังก์ชันบูลีนที่สมดุล ได้แก่ฟังก์ชันเสียงข้างมาก[ 1 ]ฟังก์ชัน "เผด็จการ" ที่คัดลอกบิตแรกของอินพุตไปยังเอาต์พุต[ 1 ]และ ฟังก์ชัน ตรวจสอบความเท่าเทียมกันที่สร้างการดำเนินการเอกซ์คลูซีฟหรือของบิตอินพุต[ 2 ]
ถ้าเป็นฟังก์ชันเบนท์บนบิต และเป็นเวกเตอร์บิตที่ไม่เป็นศูนย์ใดๆ ฟังก์ชันที่แมปไป ยัง จะสมดุล ฟังก์ชันเบนท์คือฟังก์ชันที่เป็นจริงสำหรับตัวเลือกที่ไม่เป็นศูนย์ทั้งหมดของ[ 3 ]
ฟังก์ชันเผด็จการสามารถประเมินได้หลังจากตรวจสอบเพียงบิตเดียวของอินพุต แต่บิตนั้นจะต้องได้รับการตรวจสอบเสมอ Benjamini, Schramm และ Wilson อธิบายตัวอย่างที่ซับซ้อนกว่าโดยอิงจากทฤษฎีการแพร่กระจายที่มีคุณสมบัติว่าอัลกอริทึม Las Vegas แบบสุ่ม สามารถคำนวณฟังก์ชันได้อย่างแม่นยำในขณะที่รับประกันว่าความน่าจะเป็นของการอ่านบิตอินพุตใด ๆ นั้นมีขนาดเล็ก โดยประมาณเป็นสัดส่วนผกผันกับรากที่สองของจำนวนบิต[ 1 ]
แอปพลิเคชัน
ฟังก์ชันบูลีนที่สมดุลใช้ในการเข้ารหัสโดยความสมดุลถือเป็นหนึ่งใน "เกณฑ์ที่สำคัญที่สุดสำหรับฟังก์ชันบูลีนที่แข็งแกร่งในการเข้ารหัส" [ 3 ] หากฟังก์ชันไม่สมดุล ฟังก์ชันนั้นจะมีอคติทางสถิติทำให้สามารถวิเคราะห์การเข้ารหัสได้เช่นการ โจมตีแบบสหสัมพันธ์
สรุปเนื้อหา
ข้อมูลสำคัญจากบทความ
ข้อมูลสำคัญเกี่ยวกับ ฟังก์ชันบูลีนสมดุล
ในคณิตศาสตร์และวิทยาศาสตร์คอมพิวเตอร์ฟังก์ชันบูลีนที่สมดุลคือฟังก์ชันบูลีนที่มีเอาต์พุตเป็น0เท่ากับ1ในชุดอินพุตซึ่งหมายความว่าสำหรับสตริงบิตอินพุตแบบสุ่มสม่ำเสมอ...
ตัวอย่าง
ตัวอย่างของฟังก์ชันบูลีนที่สมดุล ได้แก่ฟังก์ชัน เสียงข้างมาก [ 1 ] ฟังก์ชัน "เผด็จการ" ที่คัดลอกบิตแรกของอินพุตไปยังเอาต์พุต [ 1 ] และ ฟังก์ชัน ตรวจสอบความเท่าเทียมกัน ที่สร้างการดำเนิน การเอกซ์คลูซีฟหรือ ของบิตอินพุต [ 2 ]
แอปพลิเคชัน
ฟังก์ชันบูลีนที่สมดุลใช้ใน การเข้ารหัส โดยความสมดุลถือเป็นหนึ่งใน "เกณฑ์ที่สำคัญที่สุดสำหรับฟังก์ชันบูลีนที่แข็งแกร่งในการเข้ารหัส" [ 3 ] หากฟังก์ชันไม่สมดุล ฟังก์ชันนั้นจะมี อคติทางสถิติ ทำให้สามารถ วิเคราะห์การเข้ารหัสได้ เช่นการ โจมตีแบบสหสัมพันธ์