Score:0

สมมติว่ามีฟังก์ชันทางเดียวอยู่ แสดงว่ามีฟังก์ชันทางเดียวอยู่โดยไม่มีบิตอินพุตที่เป็นฮาร์ดคอร์บิต

ธง us

ฉันเพิ่งเรียนรู้คำจำกัดความของฮาร์ดคอร์บิต และฉันไม่มีสัญชาตญาณเกี่ยวกับเรื่องนี้ ฉันต้องการทราบว่าอะไรคือแนวทางที่เป็นไปได้สำหรับปัญหานี้

cn flag
คำแนะนำ: สำหรับเอาต์พุตคงที่ บิตอินพุตบางบิตต้องคาดเดาได้ยาก แต่แต่ละบิตสามารถคาดเดาได้ง่ายสำหรับ *ค่าเฉลี่ย* บนอินพุตแบบสุ่ม
Score:1
ธง us

ฉันได้รับความคิดที่ดีจากเพื่อนร่วมชั้นของฉัน

สมมติว่า $f:\{0,1\}^n\to\{0,1\}^m$ เป็นฟังก์ชันทางเดียว

เราสร้างฟังก์ชันทางเดียวอีกฟังก์ชันหนึ่ง $F:\{0,1\}^{n+1+\log(n+1)}\to\{0,1\}^{m+\log(n+1)+1}$ : สำหรับการป้อนข้อมูล $x=x_0x_1\cdots x_{n-1}x_n||s$, ที่ไหน $s\in\{0,1,2,\cdots,n\}$ คือ $\log(n+1)$สตริง -bit เรามี $$ F(x)=f(x_0x_1\cdots x_{s-1}x_{s+1}\cdots x_n)||s||x_s $$ จากนั้นเราจะสามารถพิสูจน์ได้ว่า $F$ เป็นฟังก์ชันทางเดียวที่ไม่มีบิตอินพุตใดที่เป็นฮาร์ดคอร์บิต

โพสต์คำตอบ

คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา