Score:0

PRG หมายถึงหลักฐาน OWF

ธง lk

ป้อนคำอธิบายรูปภาพที่นี่ ฉันได้แนวคิดของการพิสูจน์นี้ว่า เนื่องจาก PRG ขยายจาก n เป็น 2n จึงไม่สามารถฉายไปยัง {0,1}^{2n} ทั้งหมดได้ เฉพาะส่วนที่เล็กน้อยซึ่งเราสามารถใช้ในทางที่ผิดเพื่อสร้างความแตกต่างที่ดีได้เพียงแค่บอกว่า A ประสบความสำเร็จในการค้นหาพรีอิมเมจใน X สตริงสุ่มจาก U2n มีโอกาสสูงที่จะไม่มีพรีอิมเมจใน X ดังนั้นเราจึงสามารถแยกแยะ U2n จาก G(Un) แต่ฉันคิดว่าฉันไม่เข้าใจการก่อสร้างดี จุดประสงค์ของ y ของเราคืออะไร? เราไม่สามารถพิสูจน์สิ่งนี้โดยใช้ f(x) := G(x) ได้หรือไม่ ทำไม f ถึงเป็นตัวแปร? ถ้าเรากำหนด f แบบนั้น มันควรจะเป็นเส้นโครงจาก 2n ถึง 2n ไม่ใช่หรือ? ฉันคิดถึงบางสิ่ง

cn flag
คำจำกัดความของ OWF ที่ใช้ที่นั่นอาจต้องการให้ฟังก์ชันคงความยาวไว้ เนื่องจาก G กำลังขยาย คุณต้องเพิ่มอินพุต
killertoge avatar
lk flag
ตกลงที่เข้าท่า ฉันข้ามกลับไปที่หน้า 40: "ในภาคต่อ เราจะจัดการกับฟังก์ชันแบบทางเดียวที่เป็นความยาวปกติ [...] โดยส่วนใหญ่จะเป็นฟังก์ชันรักษาความยาว" ฉันใช้หนังสือของ Goldreichs เพื่ออ่านข้อพิสูจน์ว่าการบรรยายของเราไม่ได้พูดถึง ดังนั้นฉันควรระมัดระวังให้มากขึ้น ขอบคุณ.
kodlu avatar
sa flag
คำถามของคุณคือความเจ็บปวดในการอ่าน โปรดใช้คณิตศาสตร์
killertoge avatar
lk flag
@kodlu ตอนนี้ฉันได้เรียนรู้เกี่ยวกับลาเท็กซ์ ฉันจะลองใช้มันในคำถามต่อไปอย่างแน่นอน

โพสต์คำตอบ

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