ใน Introduction to Modern Cryptography ของ Katz มีปัญหาหนักๆ หลายอย่าง และสำหรับแต่ละปัญหา จะมีการทดลอง ซึ่งอัลกอริทึมสร้างตัวอย่างปัญหา และอัลกอริทึมอีกชุดหนึ่งแก้ปัญหาอินสแตนซ์ของปัญหา ตัวอย่างเช่น พิจารณาปัญหาลอการิทึมแยกใน 9.3.2:
ให้ GG เป็นอัลกอริทึมการสร้างกลุ่มซึ่งสำหรับแต่ละ n สร้าง (G,q,p)
ให้ A เป็นอัลกอริทึมสำหรับแก้ปัญหา
การทดสอบลอการิทึมแบบไม่ต่อเนื่อง DLog_{A,GG} (n):
- รัน GG(1^n ) เพื่อรับ (G , q, g) โดยที่ G เป็นกลุ่มวงจรของคำสั่ง q (โดย kqk = n) และ g เป็นตัวกำเนิดของ G
- เลือกเครื่องแบบ h ใน G
- A ได้รับ G , q, g, h และเอาต์พุต x ใน Z_q
- ผลลัพธ์ของการทดสอบกำหนดให้เป็น 1 ถ้า g^x = h และ 0 มิฉะนั้น
คำจำกัดความ 9.63 เรากล่าวว่าปัญหาลอการิทึมแบบไม่ต่อเนื่องนั้นยากเมื่อเทียบกับ GG ถ้าสำหรับอัลกอริธึมเวลาพหุนามที่น่าจะเป็นทั้งหมด A มีฟังก์ชันเล็กน้อยที่ละเลยได้ เช่น Pr[DLog A,GG(n) = 1] = negl(n)
คำจำกัดความและการวิเคราะห์ความแข็งของปัญหานั้นเกี่ยวข้องกับแนวคิดของ "การทดลอง" มาตรฐานไปจนถึงการวิเคราะห์ความซับซ้อนของปัญหาโดยทั่วไปหรือไม่ (ไม่ใช่เฉพาะในการเข้ารหัส)
หนังสือเกี่ยวกับการวิเคราะห์ความซับซ้อนของปัญหาใช้คำจำกัดความและการวิเคราะห์ความแข็งของปัญหาแบบนี้หรือไม่?
ขอบคุณ.
คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา
