พิสูจน์: หากมี OWF ที่แข็งแกร่ง แสดงว่ามี OWF ที่อ่อนแอที่ไม่แข็งแกร่งอยู่

สองสิ่ง:

1. ใช่, $x_1$ เป็นบิตแรก แนวคิดก็คือว่าถ้า $x_1 = 0$ (ซึ่งเกิดขึ้นด้วยความน่าจะเป็น 1/2) มันง่ายที่จะหาภาพพจน์ของ $g(x) = 0$ --- สตริงใด ๆ $x'$ กับ $x'_1 = 0$ จะเพียงพอ นี่แสดงให้เห็นว่า $g$ ไม่สามารถเป็น $\alpha$-OWF สำหรับใดๆ $\alpha <1/2$. แสดงว่าเป็น $\alpha$-OWF สำหรับ $\alpha \leq 2/3$คุณจะต้องลดการรักษาความปลอดภัย OWF ที่แข็งแกร่งของ $f$ซึ่งฉันจะปล่อยให้คุณทำ

2. ทางเลือกของ $2/3$ เป็นเพียงการประชุมทางสังคมสำหรับ "ค่าคงที่ที่เหมาะสม" มี มากมาย คลาสที่ซับซ้อน $\คณิตศาสตร์แคล{C}$ ขึ้นอยู่กับพารามิเตอร์บางอย่าง $\alpha$ (ซึ่งฉันจะหมายถึง $\mathcal{C}(\alpha)$) ซึ่งคุณสามารถแสดงผลลัพธ์ของฟอร์มได้

สำหรับใดๆ $\alpha$ ห่าง*จาก $1/2$ และ $1$คลาสความซับซ้อน $\mathcal{C}(\alpha)$ มีค่าเทียบเท่า

ในที่นี้ คำว่า "พ้นเขตแดน" หมายความเช่นนั้น $\frac{1}{2}+\frac{1}{n^c} \leq \alpha \leq 1 - \frac{1}{n^d}$ สำหรับค่าคงที่ $c, d$ --- โดยเฉพาะอย่างยิ่ง, $\alpha$ ต้องไม่ใกล้เคียง (เป็นฟังก์ชันของขนาดของอินพุต) กับ 1/2 หรือ 1 สำหรับคลาสดังกล่าว การประชุมทางสังคมที่จะเลือก $\mathcal{C}(2/3)$ เป็นตัวอย่าง "มาตรฐาน" ที่เกี่ยวข้องกับสิ่งต่าง ๆ เป็นเรื่องธรรมดา

มีตัวอย่างมากมายของฟีโนโนมาข้างต้น เช่น คลาสความซับซ้อนแบบสุ่มส่วนใหญ่ แต่บางที $บีพีพี$ โดยเฉพาะอย่างยิ่งเป็นตัวอย่างที่รู้จักกันดีที่สุด ความสำคัญของ $\alpha$ ขอบเขตห่างจาก 1/2 และ 1 สามารถมองเห็นได้ผ่านความแตกต่างระหว่างคลาส $บีพีพี$ (ซึ่งมีข้อจำกัดนี้) และคลาส $พีพี$ (ซึ่งไม่ได้และเป็น มาก มีพลังมากขึ้น)

อย่างไรก็ตาม ส่วนนี้ของบันทึกย่อที่เชื่อมโยงโดยพื้นฐานแล้วแสดงให้เห็นว่าฟังก์ชันทางเดียวเป็นคลาสที่คล้ายคลึงกับสิ่งต่างๆ เช่น $บีพีพี$ (ในแง่ของการพึ่งพาพารามิเตอร์ $\alpha$).