Chính xác thì "Mở rộng của đa thức" nghĩa là gì?

Điều này từ bản thảo của một cuốn sách về Zero Knowledge Proofs - https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf

3.5 Mở rộng bậc thấp và đa tuyến $\mathbb F$ là bất kỳ trường hữu hạn nào, và đặt $f : \{0, 1\}^v \rightarrow \mathbb F$ là bất kỳ chức năng ánh xạ siêu khối Boolean v-chiều thành $\mathbb F$. Một $v$-biến đa thức $g$ trên $\mathbb F$ được cho là một phần mở rộng của $f$ nếu $g$ đồng ý với tất cả các đầu vào có giá trị Boolean, nghĩa là, $g(x) = f (x)$ cho tất cả $x \in \{0, 1\}^v$

Tôi không thể hiểu điều này có nghĩa là gì.

• Tôi không nghĩ rằng họ đang nói về các trường Mở rộng ở đây - tức là sau đó họ sẽ có $\mathbb F_p$ & $\mathbb F_{p^n}$

• tôi nghĩ $\{0,1\}^v$ là một chuỗi bit của $v$ chút ít. Hay tôi đang hiểu sai nó?

• $f$ là một bản đồ - tuy nhiên tôi nghĩ nó cũng là một đa thức. Chắc nó ở dạng đa thức bậc nhất $v$ & nó lấy các hệ số từ $\mathbb F_2$.

• Và $g$ là một đa thức khác. Tuy nhiên, tôi không rõ lĩnh vực nào $g$ lấy hệ số của nó từ.

• $g$ là một $v$ biến đa thức. Vì vậy, những gì chính xác làm $f(x) = g(x)$ cho tất cả $x \in \{0, 1\}^v$ bần tiện. Nếu $g$ là một đa thức nhiều biến, thì g không thể được đánh giá chỉ với $x$ làm đầu vào - nó cần $v$ các biến khác nhau để đánh giá tức là $g(x_1, x_2 .... x_v)$. Vậy làm thế nào để chúng ta có $f(x) = g(x)$?

Nói chung, tôi không hiểu "Mở rộng của đa thức" này là gì? Ai đó có thể hướng dẫn tôi hiểu định nghĩa được trích dẫn có nghĩa là gì không.

Có lẽ một cái tên được biết đến nhiều hơn cho kỹ thuật này là số học hóa. Ý tưởng rộng rãi đằng sau nó là mã hóa logic boolean thành các đa thức bậc thấp, mà (vì những lý do kỹ thuật nhất định) có sẵn nhiều kỹ thuật phân tích hữu ích khác nhau (có lẽ rõ ràng nhất là bổ đề Schwartz-Zippel). Điều này đặc biệt hữu ích để chứng minh tính hợp lý của các bằng chứng tương tác và là chìa khóa cho bằng chứng của Shamir về $\mathsf{IP} = \mathsf{PSPACE}$.

$f$ là một bản đồ - tuy nhiên tôi nghĩ nó cũng là một đa thức. Chắc nó ở dạng đa thức bậc nhất $v$ & nó lấy các hệ số từ $\mathbb{F}_2$.

Ngay cả khi bạn có thể nghĩ về $f$ như một đa thức, tốt hơn là không nên. Chúng tôi có một số đối tượng tính toán "tiêu chuẩn" ban đầu mà chúng tôi muốn phân tích, điều này thường có nghĩa là

• một công thức boolean, hoặc
• một mạch boolean, hoặc
• một bảng sự thật.

Bạn có thể xem tất cả những thứ này dưới dạng đa thức trên $\mathbb{F}_2$ (và có thể cho rằng đó chính xác là mạch boolean), nhưng đôi khi bạn sẽ có một công thức thay thế hoặc bất cứ thứ gì.

Ý tưởng đằng sau việc tìm kiếm một đa thức mở rộng (hoặc, như tôi đã nói trước đây, gọi là "số học") là mã hóa đối tượng (tiêu chuẩn) này thành một đa thức $g(x) \in \mathbb{F}[x_1,\dots,x_v]$ mà "đồng ý với" $f(x)$ theo nghĩa là

$$\forall (x_1,\dots,x_v)\in\{0,1\}^v : f(x_1,\dots,x_v) = g(x_1,\dots,x_v).$$

Điều này có thể dễ dàng được thực hiện đối với một số hoạt động nhất định, ví dụ: $g_{AND}(x,y) = xy$ là phần mở rộng của AND, $g_{KHÔNG}(x) = 1-x$ là phần mở rộng của NOT. Đối với các hoạt động khác, nó đơn giản hơn một chút, ví dụ $$g_{XOR}(x,y) = x+y-2xy = 1 - (xy - (1-x)(1-y)).$$ là số học của XOR (tôi nghĩ) và có lẽ không rõ ràng trước đó.

Trong các nhận xét, bạn đã hỏi tại sao chúng tôi quan tâm. Có lẽ động lực tốt nhất là Bổ đề Schwartz-Zippel, nhưng bổ đề kỹ thuật của nó là tiện ích của ai có thể không hữu ích ngay lập tức. "Elevator pitch" cho số học là

1. đó là chìa khóa để chứng minh $\mathsf{IP} = \mathsf{PSPACE}$ (thông qua giao thức "tổng kiểm tra" của Shamir), một trong những kết quả lớn đầu tiên trong các hệ thống bằng chứng tương tác và
2. bằng chứng của kết quả này là rất đặc biệt (không tương đối hóa, và không phải là bằng chứng tự nhiên). Có thể cho rằng "số học" là một trong ~ 3 hoặc 4 kỹ thuật chứng minh cơ bản mà chúng ta biết trong lý thuyết phức tạp. Cho đến năm 2009, nó thực sự là những kỹ thuật "lớn" chính vẫn có cơ hội thể hiện rằng $\mathsf{P} \neq \mathsf{NP}$ --- nó không còn có một shot mặc dù.

Dù sao, đối với một tài liệu tham khảo sách rõ ràng, tôi biết nó ít nhất có trong Arora & Barak's Độ phức tạp tính toán: Một cách tiếp cận hiện đại. Sử dụng ctrl+f để tìm kiếm "số học" sẽ ngay lập tức đưa bạn đến chương 8.5.2, thảo luận về cách tiếp cận. Nói chung, tìm kiếm theo thuật ngữ này có thể sẽ hiệu quả hơn nhiều so với "đa thức mở rộng", có thể có nhiều va chạm tên vô tình hơn.