ฉันสับสนกับคำจำกัดความของ GAP SVP ปัญหาระบุว่าสำหรับการแก้ไข $\gamma \geq 1$ให้เป็นพื้นฐาน $B$ ของแลตทิซและก $d>0$GAPSVP ขอให้ตรวจสอบว่า $\แลมบ์ดา\leq d$ หรือ $\lambda > \gamma d$. ความสับสนของฉันคือจะเกิดอะไรขึ้นถ้า $d<\lambda\leq \gamma d$? แล้วคำตอบของ GAP SVP จะเป็นอย่างไร? ฉันอ่านจาก Micciancio's Fall 2021 CSE206A หมายเหตุ คำตอบใด ๆ ที่ยอมรับได้ในกรณีนั้น แต่นั่นหมายความว่าอย่างไร
บันทึกของ Micciancio นั้นถูกต้องและเป็นวิธีมาตรฐานในการอธิบายสิ่งต่าง ๆ ดังนั้นเรามาอธิบายเพิ่มเติม
ประการแรก สิ่งที่ควรกล่าวถึงนี้ไม่เกี่ยวกับ (Gap)SVP โดยเฉพาะ และทุกอย่างเกี่ยวข้องกับสิ่งที่เรียกว่า ปัญหาสัญญา ให้เป็นปกติมากกว่านี้.
ปัญหาสัญญาคือการผ่อนคลายปัญหาการตัดสินใจมาตรฐาน มีไว้เพื่อผ่อนคลายความคิดของ ความถูกต้อง สำหรับปัญหา แนวคิดมาตรฐานเกี่ยวกับความถูกต้องสามารถสรุปได้ว่า "อัลกอริทึมถูกต้องในทุกอินพุต" การผ่อนคลายตามธรรมชาติมีสองอย่างนี้
คลาสแบบสุ่ม (เช่น BPP, ZPP, (co)RP)ในกรณีใดกรณีหนึ่ง อัลกอริทึมจะต้องถูกต้อง "โดยเฉลี่ย" โดยที่คุณเฉลี่ยมากกว่าตัวเลือกเหรียญสุ่มภายใน
ปัญหาตามสัญญา ซึ่งคุณไม่มีปัญหากับอัลกอริทึมที่ทำผิดพลาดใน "อินสแตนซ์แบบยาก" แต่จะต้องถูกต้องใน "อินสแตนซ์แบบง่าย" เสมอ
โดยเฉพาะอย่างยิ่ง ในกรณียาก อัลกอริทึมสามารถเป็นได้ ไม่ถูกต้องอย่างสมบูรณ์และเราไม่สนใจ ตราบใดที่มันถูกต้องในกรณีง่ายๆ เราจะบอกว่ามันถูกต้องโดยรวม
เพื่อนำสิ่งต่าง ๆ กลับมาที่ GapSVP กรณีที่ยากคือเมื่อใด $d\leq \lambda\leq \gamma d$. ดังนั้นเราจึงบอกว่าอัลกอริทึมแก้ GapSVP ถ้า
ให้ตัวอย่าง $(ล, ง)$ (ตาข่ายและระยะทางผูกพัน) นั่นคือ ง่าย, ความหมาย $\lambda_1(L)\leq d$ หรือ $\lambda_1(L)\geq \gamma d$อัลกอริทึมจะส่งคืนคำตอบที่ถูกต้อง
อัลกอริทึมจะส่งคืนสิ่งที่ต้องการ เราไม่สนใจ
โดยเฉพาะอย่างยิ่งให้ เหมือนกัน ฮาร์ดอินสแตนซ์สองครั้ง อัลกอริทึมสามารถส่งคืนทั้งสองคำตอบ (ไม่จำเป็นต้องสอดคล้องกันภายใน) เราไม่สนใจ --- เราสนใจแค่ว่าอัลกอริทึมทำงานอย่างไรกับอินสแตนซ์ที่ "ง่าย" ซึ่งวัดโดย $\gamma$.
คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา
