กลับไปหน้าบทความ

อ่าน 2 นาที

ฟังก์ชันบูลีนสมดุล

ในคณิตศาสตร์และวิทยาศาสตร์คอมพิวเตอร์ฟังก์ชันบูลีนที่สมดุลคือฟังก์ชันบูลีนที่มีเอาต์พุตเป็น0เท่ากับ1ในชุดอินพุตซึ่งหมายความว่าสำหรับสตริงบิตอินพุตแบบสุ่มสม่ำเสมอ...

ฟังก์ชันบูลีนสมดุล

ในคณิตศาสตร์และวิทยาศาสตร์คอมพิวเตอร์ฟังก์ชันบูลีนที่สมดุลคือฟังก์ชันบูลีนที่มีเอาต์พุตเป็น0เท่ากับ1ในชุดอินพุตซึ่งหมายความว่าสำหรับสตริงบิตอินพุตแบบสุ่มสม่ำเสมอ ความน่าจะเป็นที่จะได้1คือ 1/2 [ 1 ]

ตัวอย่าง

ตัวอย่างของฟังก์ชันบูลีนที่สมดุล ได้แก่ฟังก์ชันเสียงข้างมาก[ 1 ]ฟังก์ชัน "เผด็จการ" ที่คัดลอกบิตแรกของอินพุตไปยังเอาต์พุต[ 1 ]และ ฟังก์ชัน ตรวจสอบความเท่าเทียมกันที่สร้างการดำเนินการเอกซ์คลูซีฟหรือของบิตอินพุต[ 2 ]

ถ้าเป็นฟังก์ชันเบนท์บนบิต และเป็นเวกเตอร์บิตที่ไม่เป็นศูนย์ใดๆ ฟังก์ชันที่แมปไป ยัง จะสมดุล ฟังก์ชันเบนท์คือฟังก์ชันที่เป็นจริงสำหรับตัวเลือกที่ไม่เป็นศูนย์ทั้งหมดของ[ 3 ]

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

แอปพลิเคชัน

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

ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=Balanced_Boolean_function&oldid=1329371774 "

สรุปเนื้อหา

ข้อมูลสำคัญจากบทความ

ข้อมูลสำคัญเกี่ยวกับ ฟังก์ชันบูลีนสมดุล

ในคณิตศาสตร์และวิทยาศาสตร์คอมพิวเตอร์ฟังก์ชันบูลีนที่สมดุลคือฟังก์ชันบูลีนที่มีเอาต์พุตเป็น0เท่ากับ1ในชุดอินพุตซึ่งหมายความว่าสำหรับสตริงบิตอินพุตแบบสุ่มสม่ำเสมอ...

ตัวอย่าง

ตัวอย่างของฟังก์ชันบูลีนที่สมดุล ได้แก่ฟังก์ชัน เสียงข้างมาก [ 1 ] ฟังก์ชัน "เผด็จการ" ที่คัดลอกบิตแรกของอินพุตไปยังเอาต์พุต [ 1 ] และ ฟังก์ชัน ตรวจสอบความเท่าเทียมกัน ที่สร้างการดำเนิน การเอกซ์คลูซีฟหรือ ของบิตอินพุต [ 2 ]

แอปพลิเคชัน

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