สิ่งนี้มาจากต้นฉบับของหนังสือเรื่อง Zero Knowledge Proofs - https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf
3.5 ส่วนขยายระดับต่ำและหลายเส้น $\mathbb F$ เป็นเขตข้อมูลจำกัดใด ๆ และให้ $f : \{0, 1\}^v \rightarrow \mathbb F$ เป็นอะไรก็ได้ ฟังก์ชันจับคู่ไฮเปอร์คิวบ์บูลีน v มิติกับ $\mathbb F$. ก $v$- ตัวแปรพหุนาม $g$ เกิน $\mathbb F$ กล่าวได้ว่าเป็นส่วนเสริม ของ $f$ ถ้า $g$ เห็นด้วยกับอินพุตที่มีค่าบูลีนทั้งหมด นั่นคือ $ก(x) = ฉ(x)$ สำหรับทุกอย่าง $x \in \{0, 1\}^v$
ฉันไม่สามารถเข้าใจความหมายนี้
ฉันไม่คิดว่าพวกเขากำลังพูดถึงฟิลด์ส่วนขยายที่นี่ - นั่นคือพวกเขาจะมี $\mathbb F_p$ & $\mathbb F_{p^n}$
ฉันคิดว่า $\{0,1\}^v$ เป็นสตริงบิตของ $v$ บิต หรือผมตีความหมายผิด?
$f$ เป็นแผนที่ - อย่างไรก็ตาม ฉันคิดว่ามันเป็นพหุนามด้วย มันอาจจะอยู่ในรูปพหุนามของดีกรีสูงสุด $v$ & มันใช้ค่าสัมประสิทธิ์จาก $\mathbb F_2$.
และ $g$ เป็นพหุนามอื่น อย่างไรก็ตามฉันยังไม่ชัดเจนว่าฟิลด์ใด $g$ ใช้ค่าสัมประสิทธิ์จาก
$g$ คือ $v$ แปรผันพหุนาม ดังนั้นสิ่งที่ไม่ $f(x) = g(x)$ สำหรับทุกอย่าง $x \in \{0, 1\}^v$ หมายถึง. ถ้า $g$ เป็นพหุนามหลายตัวแปร ดังนั้น g จึงหาค่าไม่ได้ด้วย $x$ เป็นอินพุต - มันต้องการ $v$ ตัวแปรต่าง ๆ ในการประเมินเช่น $g(x_1, x_2 .... x_v)$. แล้วเรามีวิธีอย่างไร $f(x) = g(x)$?
สรุปฉันไม่เข้าใจว่า "ส่วนขยายของพหุนาม" คืออะไร ใครช่วยแนะนำฉันให้เข้าใจว่าคำจำกัดความที่ยกมาหมายถึงอะไร
ความแตกต่างที่นี่คือ $g$ แผนที่จาก $\mathbb F^v\to \mathbb F$. ค่าบูลีน 0 และ 1 สามารถระบุได้โดยธรรมชาติด้วยตัวระบุการบวกและการคูณในฟิลด์ใดก็ได้เพื่อทำให้การบีบบังคับ $\{0,1\}^v\to \mathbb F^v$ ของ $v$สตริงบิตยาวถึง $v$-tuples ขององค์ประกอบของ $\mathbb F$ มีความหมายและไม่คลุมเครือ
ตัวอย่างอาจช่วยได้ที่นี่ อนุญาต $v=1$ และปล่อยให้ $\mathbb F=\mathbb F_5$. สมมติว่าเรามีฟังก์ชัน $f:\{0,1\}\to\mathbb F_5$ ที่กำหนดโดย $f(0)=2$ และ $f(1)=4$. ฟังก์ชันนี้มีส่วนขยายโดยพหุนามมากกว่า $\mathbb F_5$ (เช่น พหุนามที่มีค่าสัมประสิทธิ์อยู่ใน $\mathbb F_5$) $g:=2x+2$. เราเห็นอย่างนั้น $g(0)=2$ และนั่น $g(1)=4$ ซึ่งเห็นด้วยกับ $f$ ตามมูลค่าที่กำหนด (โปรดทราบว่าการประเมินของ $f$ สามารถนึกถึงการค้นหาตารางในขณะที่ $g$ คำนวณโดยใช้ $\mathbb F_5$ เลขคณิต). คุณสมบัติส่วนขยายไม่ได้พูดอะไรเกี่ยวกับพฤติกรรมของ $g$ ที่จุดอื่น ๆ และในความเป็นจริงมีพหุนามหลายตัวที่เป็นส่วนขยายของ $f$. อีกตัวอย่างหนึ่งคือ $g_2(x):=x^2+x+2$. โดยทั่วไปแล้วพหุนามของรูปแบบใดๆ $2x+2+h(x)(x^2-x)$ จะเป็นส่วนขยายของ $f$.
มันไม่สมเหตุสมผลเลยที่จะนึกถึง $f$ เป็นพหุนามมากกว่า $\mathbb F_2$ เป็นเลขคณิตมากกว่า $\mathbb F_2$ ไม่สามารถสร้างองค์ประกอบของ $\mathbb F_5$.
ETA 20220211: สำหรับค่าที่สูงขึ้นของ $v$, เราแยกส่วน $v$สตริงบิตยาว $x$ เข้าไปข้างใน $v$ ตัวแปรที่จะกำหนด $g$. ตัวอย่างเช่นกับ $v=2$ และ $\mathbb F_5$ เมื่อก่อนเราอาจจะเคย $f(00)=2$, $f(01)=2$ $f(10)=3$ และ $f(11)=4$. เราก็เลยอยากหา $g(x_1,x_2)\in \mathbb F_5[x_1,x_2]$ กับ $g(0,0)=2$, $g(0,1)=2$, $g(1,0)=3$ และ $g(1,1)=4$. ตัวอย่างหนึ่งคือ $g(x_1,x_2)=x_1x_2+x_1+2$แต่ก่อนมีความเป็นไปได้อื่น ๆ อีกมากมาย
บางทีชื่อที่รู้จักกันดีสำหรับเทคนิคนี้คือ เลขคณิต. แนวคิดกว้างๆ ที่อยู่เบื้องหลังคือการเข้ารหัสลอจิกบูลีนเป็นพหุนามดีกรีต่ำ ซึ่ง (ด้วยเหตุผลทางเทคนิคบางประการ) มีเทคนิคการวิเคราะห์ที่เป็นประโยชน์มากมาย สิ่งนี้มีประโยชน์อย่างยิ่งสำหรับการพิสูจน์ความถูกต้องของการพิสูจน์แบบโต้ตอบ และเป็นกุญแจสำคัญในการพิสูจน์ของ Shamir $\mathsf{IP} = \mathsf{PSPACE}$.
$f$ เป็นแผนที่ - อย่างไรก็ตาม ฉันคิดว่ามันเป็นพหุนามด้วย มันอาจจะอยู่ในรูปพหุนามของดีกรีสูงสุด $v$ & มันใช้ค่าสัมประสิทธิ์จาก $\mathbb{F}_2$.
แม้จะคิดได้ $f$ ในฐานะที่เป็นพหุนามจะเป็นการดีกว่าที่จะไม่ เรามีออบเจกต์การคำนวณ "มาตรฐาน" เริ่มต้นที่เราต้องการวิเคราะห์ ซึ่งโดยทั่วไปหมายถึง
คุณสามารถดูทั้งหมดเหล่านี้เป็นพหุนามได้ $\mathbb{F}_2$ (และแน่นอนว่านั่นคือวงจรบูลีนนั่นเอง) แต่บางครั้งคุณก็จะมีสูตรแทนหรืออะไรก็ตาม
แนวคิดเบื้องหลังการค้นหาพหุนามส่วนขยาย (หรืออย่างที่ฉันพูดไปก่อนหน้านี้ การดึงดูด "เลขคณิต") คือการเข้ารหัสวัตถุ (มาตรฐาน) นี้เป็นพหุนาม $g(x) \in \mathbb{F}[x_1,\dots,x_v]$ ที่ "เห็นด้วย" $ฉ(x)$ ในแง่ที่ว่า
$$\forall (x_1,\dots,x_v)\in\{0,1\}^v : f(x_1,\dots,x_v) = g(x_1,\dots,x_v).$$
ซึ่งสามารถทำได้ง่ายสำหรับการดำเนินการบางอย่าง เช่น $g_{AND}(x,y) = xy$ เป็นส่วนขยายของ AND $g_{NOT}(x) = 1-x$ เป็นนามสกุลของNO. สำหรับการดำเนินการอื่น ๆ จะตรงไปตรงมาน้อยกว่าเล็กน้อย $$g_{XOR}(x,y) = x+y-2xy = 1 - (xy - (1-x)(1-y)).$$ เป็นเลขคณิตของ XOR (ฉันคิดว่า) และอาจไม่ชัดเจนล่วงหน้า
ในความคิดเห็นที่คุณถามว่าทำไมเราถึงสนใจ บางทีแรงจูงใจที่ดีที่สุดคือ Schwartz-Zippel Lemma แต่คำศัพท์ทางเทคนิคของคำว่า who's utility อาจไม่มีประโยชน์ในทันที "ระยะห่างระหว่างลิฟต์" สำหรับการคำนวณเลขคณิตคือ
อย่างไรก็ตาม สำหรับการอ้างอิงหนังสือที่ชัดเจน ฉันรู้ว่าอย่างน้อยมันก็มีอยู่ใน Arora & Barak's ความซับซ้อนทางการคำนวณ : แนวทางสมัยใหม่. การใช้ ctrl+f เพื่อค้นหา "การคำนวณเลขคณิต" จะนำคุณไปยังบทที่ 8.5.2 ทันที ซึ่งจะกล่าวถึงวิธีการ โดยทั่วไปแล้ว การค้นหาด้วยคำนี้น่าจะได้ผลมากกว่า "นามสกุลพหุนาม" ซึ่งอาจมีการชนกันของชื่อโดยไม่ได้ตั้งใจมากกว่า
คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา
