แบบจำลองทั่วไปของกล่องดำห้ามการคำนวณลอการิทึมแบบไม่ต่อเนื่องในกลุ่มของคำสั่ง $q=2p+1$ ที่ไหน $p,q$ เป็นจำนวนเฉพาะสุ่มของ $\Omega(\sqrt{p})$ ขั้นตอน (อ้างอิง ลอการิทึมแบบไม่ต่อเนื่องในแบบจำลองกลุ่มทั่วไปนั้นยาก - ทฤษฎีบทโดย Shoup).
โมเดลทั่วไปของกล่องดำยังห้ามไม่ให้ MSB ของลอการิทึมไม่ต่อเนื่อง $\Omega(\sqrt{p})$ หรือเป็นไปได้หรือไม่ที่อัลกอริทึมทั่วไปของกล่องดำสามารถรับ MSB ของลอการิทึมที่ไม่ต่อเนื่องเข้ามาได้ $โพลีล็อก(p)$ ขั้นตอน?
หมายเหตุในการคำนวณลอการิทึมแบบไม่ต่อเนื่องเมื่อคุณรู้ว่า MSB นั้นไม่สำคัญ แต่มีการโต้ตอบ (การแตกแขนงขึ้นอยู่กับ MSB คือ $0$ หรือ $1$) ซึ่งผมไม่แน่ใจว่ารุ่น Black Box ห้าม
ซึ่งผมไม่แน่ใจว่ารุ่น Black Box ห้าม"
สิ่งที่โมเดลกล่องดำห้ามคือการดำเนินการใดๆ กับองค์ประกอบกลุ่มนอกเหนือจากชุดการดำเนินการเฉพาะ ในกรณีของคุณ การดำเนินการที่อนุญาตจะเป็น:
การดำเนินงานกลุ่ม (อพ $A$ และ $B$, กลับ $A \คูณ B$)
การดำเนินการผกผันกลุ่ม
การเปรียบเทียบองค์ประกอบสองกลุ่มเพื่อความเท่าเทียมกัน
msbit oracle ของคุณ (เนื่องจากคุณกำลังขยายโมเดลกล่องดำเพื่อให้มีการดำเนินการนี้)
การดำเนินการอื่นใดกับองค์ประกอบของกลุ่มเป็นสิ่งต้องห้าม
ในทางกลับกัน การดำเนินการใด ๆ ที่ไม่ใช่องค์ประกอบของกลุ่มถือเป็นเกมที่ยุติธรรม ตัวอย่างเช่น msbit oracle ของคุณคืนค่าบิต บิตนี้ไม่ใช่องค์ประกอบกลุ่ม และทำสิ่งต่างๆ เช่น:
ถ้า (oracle_returned_a_one) {
ทำเช่นนี้();
} อื่น {
ทำอย่างนั้น();
}
กำลังเล่นได้อย่างสมบูรณ์แบบ
ดังนั้น เว้นแต่ว่าจำนวนเฉพาะจะอยู่เหนือกำลัง 2 เพียงเล็กน้อย นั่นคือ $p = 2^k + \ell$ สำหรับ $2^k / \text{polylog}(p) < \ell < 2^k$ควรชัดเจนว่าคุณสามารถคำนวณบันทึกแบบไม่ต่อเนื่องด้วยจำนวนการสืบค้นแบบพหุนาม (โดยเฉพาะ $k + \text{polylog}(p)$ สอบถาม)
คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา
