PCP 2 — ĐL PCP và NP-hardness của Gap-Max-E3SAT

NQH | 16/05/2009 |

5. Các thuật toán xấp xỉ cho các bài toán NP-Hard

Một trong các cách để giải quyết một bài toán tối ưu nhưng lại bị NP-hard là thiết kế một thuật toán xấp xỉ cho nó. Đối với các bài toán này, có một trade-off về mặt bản chất giữa chất lượng lời giải và thời gian tìm ra lời giải. Nếu muốn tìm lời giải tối ưu thì ta phải dùng hơn poly-time. Nếu muốn chạy trong poly-time thì buộc phải thỏa mãn với lời giải không nhất thiết là tối ưu.

Định nghĩa: Một thuật toán chạy trong poly-time và cho ra lời giải với giá nằm trong khoảng $\alpha$ lần giá tối ưu thì được gọi là một $\alpha$ -approximation algorithm của bài toán đang xét. Con số $\alpha$ gọi là approximation ratio của thuật toán.

Ví dụ 1: trong bài toán Vertex Cover, cho một đồ thị $G$ , ta cần tìm một số ít đỉnh nhất để “cover” tất cả các cạnh. (Một đỉnh “covers” một cạnh nếu nó kề cạnh đó.) Bài toán này là NP-Hard. Một $2$ -approximation algorithm cho bài này có thể thiết kế như sau:

Tìm một maximal matching $M$ của $G$ . (Chú ý rằng maximal khác với maximum. Mặc dù dùng maximum cũng được. Ngoài ra $M$ là ký hiệu tập các cạnh của matching.)
Output tất cả các đỉnh (có $2|M|$ đỉnh) của matching này.

Dĩ nhiên bất kỳ cạnh $e$ nào của $G$ cũng kề với một đỉnh nào đó trong matching, vì nếu không thì có thể thêm $e$ vào matching và do đó nó không còn là maximal nữa. Một Vertex Cover bất kỳ nào cũng phải chứa ít nhất một đỉnh cho mỗi cạnh của $M$ . Do đó, kích thước $\mathsf{opt}$ của Vertex Cover tối ưu cũng phải ít nhất là $|M|$ . Vì thế,

tổng số đỉnh thuật toán outputs $= 2|M| \leq 2 \cdot \mathsf{opt}$

Chúng ta vừa chứng minh rằng thuật toán đơn giản trên là $2$ -approximation algorithm cho bài Vertex Cover. Một bài toán mở rất quan trọng trong lý thuyết thuật toán xấp xỉ là có tồn tại một $(2-\epsilon)$ -approximation algorithm cho bài toán Vertex Cover hay không? ( $\epsilon$ là một hằng số dương tùy ý!)

Ví dụ 2: trong bài toán Max-E3SAT, cho một công thức E3-CNF $\varphi$ , nghĩa là một công thức CNF mà mỗi clause có đúng 3 literals, cần tìm một truth assignment thỏa mãn nhiều clauses nhất. Bài toán này dĩ nhiên là NP-hard. Xét thuật toán ngẫy nhiên hóa sau đây: gán mỗi biến giá trị TRUE/FALSE với xác suất $1/2$ . Xác suất một clause tùy ý được thỏa mãn là $7/8$ . Do đó, do linearity of expectation, giá trị kỳ vọng của số các clauses được thỏa mãn là $7/8$ tổng số clauses. Mà $7/8$ tổng số clauses thì ít nhất là $7/8$ tổng số tối đa các clauses có thể được thỏa mãn cùng một lúc.

Chúng ta vừa thiết kế một $7/8$ -randomized approximation algorithm cho bài Max-E3SAT. Thuật toán này có thể được de-randomized dùng phương pháp conditional expectation, dẫn đến một thuật toán xấp xỉ với approximation ratio $7/8$ cho bài toán Max-E3SAT.

Hai ví dụ trên chỉ để minh họa khái niệm approximation algorithm. Chúng được chọn vì có lời giải cực ngắn, một đại diện cho các bài toán tối thiểu hóa, một tối đa hóa. Đa số các approximation algorithms không ngắn gọn như thế. Thiết kế approximation algorithms là một nhánh nghiên cứu khá trưởng thành của thuật toán, có nhiều kỹ thuật tuyệt vời (dùng LP, SDP, hoặc randomization cộng derandomization chẳng hạn), và có liên hệ mật thiết đến complexity theory và PCP. Trong chuỗi bài này, chúng ta sẽ không nói về các kỹ thuật thiết kế thuật toán xấp xỉ. Các bạn đọc nên tham khảo 4 quyển sách (kinh điển) sau để biết sơ khởi về approximation algorithms:

Vijay Vazirani, Approximation Algorithms Springer-Verlag, 397 pages hardcover, ISBN: 3-540-65367-8, published 2001.
Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms, 492 pages, Cambridge University Press (August 25, 1995).
Dorit Hochbaum (Editor), Approximation Algorithms for NP-Hard Problems, 624 pages ; Brooks/Cole Pub Co; ISBN: 0534949681; 1st edition (July 26, 1996)
Mark Jerrum, Counting, Sampling and Integrating: Algorithms and Complexity (Lectures in Mathematics. ETH Zürich), Birkhäuser Basel; 1 edition (April 28, 2003)

6. Xấp xỉ một bài NP-hard cũng có thể bị … NP-hard

Có tồn tại một thuật toán xấp xỉ cho bài Vertex Cover với tỉ lệ xấp xỉ $1.99999$ không? Có tồn tại một thuật toán xấp xỉ cho bài Max-E3SAT với tỉ lệ $7/8+0.00001$ không? Làm thế nào để trả lời các câu hỏi loại này? (Dành cho các bạn nóng lòng: câu trả lời là không biết cho câu hỏi thứ nhất, và không, trừ phi P=NP cho câu hỏi thứ hai.)

Để trả lời các câu hỏi về hardness of approximation như trên, chúng ta cần một khái niệm mới: gap-version của một bài toán tối ưu. Để đơn giản, chúng ta sẽ dùng Max-E3SAT làm ví dụ.

Định nghĩa: cho trước hai số $0 < s < c \le 1$ .

Input của bài toán là một công thức E3-CNF $\varphi$ với $m$ clauses. (Hai số $c,s$ có thể phụ thuộc vào kích thước của $\varphi$ .) Gọi $\mathsf{opt}(\varphi)$ là tỉ lệ tối đa các clauses của $\varphi$ có thể được thỏa mãn bới một truth assignment. (Nghĩa là, nếu tổng số tối đa các clauses có thể thỏa mãn được bới một truth assignment là $m'$ thì $\mathsf{opt}(\varphi) = m'/m$ .) Chúng ta biết trước rằng hoặc $\mathsf{opt}(\varphi) \geq c$ hoặc $\mathsf{opt}(\varphi) \leq s$ . (Đây là một loại promise problem.)

Output của bài toán là YES hoặc NO. YES nếu $\mathsf{opt}(\varphi) \geq c$ còn NO nếu $\mathsf{opt}(\varphi) \leq s$ .

Bài tập. Chứng minh rằng Gap-Max-E3SAT $(1, 1-1/m)$ là NP-Hard, trong đó $m$ là tổng số clauses của input formula.

Lý do mà chúng ta cần khái niệm “gap problems” được giải thích trong bổ đề sau.

Bổ Đề: Nếu bài toán Gap-Max-E3SAT $(c,s)$ là NP-Hard với các số $00$ — không tồn tại thuật toán xấp xỉ cho bài toán Max-E3SAT đến tỉ lệ $\frac s c + \epsilon$ , trừ phi P=NP. Cụ thể hơn, việc xấp xỉ bài toán đến tỉ lệ đó là NP-Hard.

Chứng minh. Giả sử tồn tại thuật toán $\mathbf A$ xấp xỉ cho Max-E3SAT đến tỉ lệ $\frac s c + \epsilon$ . Chúng ta có thể dùng thuật toán này để giải bài toán NP-Hard Gap-Max-E3SAT $(c,s)$ trong poly-time như sau:

Cho một input $\varphi$ của bài toán Gap-Max-E3SAT $(c,s)$
Cung cấp input này cho thuật toán $\mathbf A$ ; nó sẽ output một truth assignment thỏa mãn $\mathbf A(\varphi)$ clauses.
Nếu $\frac{\mathbf A(\varphi)}{m} > s$ thì output YES.
Nếu $\frac{\mathbf A(\varphi)}{m} \leq s$ thì output NO.

Do $\mathbf A$ là $(\frac s c+\epsilon)$ -approximation algorithm, chúng ta biết rằng $\frac{\mathbf A(\varphi)}{m} \geq \left(\frac s c + \epsilon\right) \mathsf{opt}(\varphi)$ . Vì thế, nếu $\varphi$ là một YES-instance thì $\mathsf{opt}(\varphi) \geq c$ và vì thế $\frac{\mathbf A(\varphi)}{m} > s$ . Còn nếu $\varphi$ là một NO-instance thì $\mathsf{opt}(\varphi) \leq s$ . Khi đó $\frac{\mathbf A(\varphi)}{m} \leq \mathsf{opt}(\varphi) \leq s$ .

QED

Thế những thứ trên thì liên quan gì đến định lý PCP? Xem định lý sau đây.

Định lý. Định lý PCP tương đương với phát biểu sau đây: “tồn tại một hằng số $0<\rho<1$ sao cho bài toán Gap-Max-E3SAT $(1,\rho)$ là bài toán NP-Hard.”

Chứng minh.

Cho chiều thuận, giả sử định lý PCP là đúng. Để chứng minh rằng Gap-Max-E3SAT $(1,\rho)$ là bài toán NP-Hard với một hẳng số $\rho$ nào đó, chúng ta tìm một reduction từ một bài toán NPC về nó. Xét một bài toán NP-Complete bất kỳ nào đó. Gọi nó là bài toán $\Pi$ . Chúng ta sẽ reduce từ $\Pi$ về Gap-Max-E3SAT $(1,\rho)$ ; giá trị cụ thể của $\rho$ sẽ được chỉ ra sau.

Từ định lý PCP, ta biết rằng tồn tại một $(r, q)$ -restricted verifier $V$ cho $\Pi$ , trong đó $r=c_1\log n$ và $q=c_2$ , $c_1,c_2$ là các hằng số dương. Xét một input $x$ bất kỳ của bài toán $\Pi$ , chúng ta sẽ dùng $V$ để xây dựng trong poly-time một công thức $\varphi_x$ là input của Gap-Max-E3SAT $(1,\rho)$ thỏa mãn hai điều kiện của một NP-Hard reduction:

(1) Nếu $x$ là YES-instance của $\Pi$ thì $\mathsf{opt}(\varphi_x) =1$ (hay nói cách khác $\varphi_x$ là YES-instance của Gap-Max-E3SAT $(1,\rho)$ )

(2) Nếu $x$ là NO-instance của $\Pi$ thì $\mathsf{opt}(\varphi_x) \leq \rho$ (hay nói cách khác $\varphi_x$ là NO-instance của Gap-Max-E3SAT $(1,\rho)$ )

Trước hết, chú ý rằng cái chứng minh $\pi$ mà prover cung cấp cho $V$ chỉ cần có độ dài tối đa $p = q2^r$ , tại vì mới mỗi random bit string với $r$ random bits, $V$ chỉ truy cập $q$ vị trí trong chứng minh $\pi$ . Do đó, chiều dài tối đa của chứng minh $\pi$ chỉ là $p=$ poly $(|x|)$ . Tạo $p$ biến Boolean $x_1, \dots, x_p$ . Mỗi biến tương đương với một bit trong chứng minh $\pi$ . Một truth assignment cho các biến này tương đương với một chứng minh $\pi$ . Chúng ta sẽ tạo công thức $\varphi_x$ sao cho việc thỏa mãn tất cả các clauses của $\varphi_x$ thì cũng giống như việc verifier $V$ chấp nhận $x$ .

Đến đây, với mỗi random string $R$ với chiều dài $r$ , chúng ta có thể chạy $V(x;R)$ và “đút” cho $V$ tất cả $2^q$ tổ hợp của các câu trả lời ở $q$ vị trí mà $V$ truy cập $\pi$ . (Xem hình dưới đây lần nữa.) Phần còn lại điền $0$ vào là xong.

$q$ vị trí mà $V(x;R)$ truy cập tương đương với $q$ biến $x_{i_1}, \dots, x_{i_q}$ nào đó. Một số truth assignments vào các biến này làm $V(x;R)$ chấp nhận $x$ , các truth assignments khác thì không. Chúng ta có thể dễ dàng viết ra một công thức CNF $\psi_{s;R}$ trên các biến $x_{i_1,},\dots,x_{i_q}$ sao cho truth assignment thỏa mãn $\psi_{x;R}$ cũng chính là truth assignment làm $V(x;R)$ chấp nhận input $x$ và ngược lại. Chú ý rằng $\psi_{x;R}$ có nhiều nhất là $2^q$ clauses, và $q$ là một hằng số. Dùng cái mẹo chuẩn (của Karp), ta dễ dàng chuyển được $\psi_{x;R}$ thành một công thức tương đương $\varphi_{x;R}$ ở dạng E3-CNF. Chỉ hơi khác là $\varphi_{x;R}$ có thể có đến $q2^q$ clauses, thay vì chỉ có $2^q$ clauses như $\psi_{x;R}$ .

Cuối cùng, định nghĩa $\varphi_x = \bigwedge_{R} \varphi_{x;R}$ — conjunction của tất cả các công thức $\varphi_{x;R}$ . Rõ ràng là $\varphi_x$ là một công thức ở dạng E3-CNF.

Ta chứng minh (1) trước. Nếu $x$ là một YES-instance của $\Pi$ thì tồn tại một chứng minh $\pi$ sao cho Prob $[V^\pi(x)=$ YES $]= 1$ , nghĩa là $V^\pi(x)$ luôn luôn chấp nhận $x$ , bất kể random string $R$ là gì. Rõ ràng là $\pi$ cũng là một truth assignment thỏa mãn toàn bộ các clauses của $\varphi_x$ .

Bây giờ đến (2). Vì $x$ là NO-instance của $\Pi$ , xác suất mà verifier $V^\pi$ chấp nhận $x$ nhiều nhất là $1/2$ , bất kể chứng minh $\pi$ là gì. Có nghĩa là, có nhiều nhất là một nửa số random strings $R$ có thể làm cho verifier chấp nhận $x$ , bất kể chứng minh $\pi$ là gì. Nói cách khác, bất kể truth assignment là gì thì cũng có một nửa số công thức $\varphi_{x;R}$ không hoàn toàn được thỏa mãn. Do đó, tổng số các clauses không được thoả mãn ít nhất là $\frac{2^r}{2}$ . (Mỗi công thức $\varphi_{x;R}$ không được thỏa mãn phải có ít nhất một clause không được thỏa mãn.) Mà, tổng số clauses $m$ của $\varphi_x$ nhiều nhất là $2^r \cdot q \cdot 2^q$ . Do đó, tỉ lệ các clauses không được thỏa mãn bởi một truth assignment bất kỳ ít nhất là $\frac{2^{r-1}}{2^r \cdot q \cdot 2^q} = \frac{1}{q2^{q+1}}$ . Vì thế, $\mathsf{opt}(\varphi_x) \leq 1-\frac{1}{q2^{q+1}}$ . Chúng ta vì thế chọn $\rho = 1- \frac{1}{q2^{q+1}}$ .

Cho chiều nghịch, giả sử tồn tại một hằng số $0 < \rho < 1$ sao cho bài toán Gap-Max-E3SAT $(1,\rho)$ là bài toán NP-Hard. Chúng ta chỉ cần thiết kế một $(O(\log n), O(1))$ -restricted verifier cho chính bài toán này là xong! (Bài tập: tại sao?) Verifier này làm việc như sau: cho một input $\varphi$ của bài toán Gap-Max-E3SAT $(1,\rho)$ , verifier chọn một clause ngẫu nhiên của $\varphi$ , query chứng minh $\pi$ ở $3$ vị trí tương ứng với các literals trong clause vừa chọn, và chấp nhận input nếu cái clause này được thỏa mãn. Nếu $\mathsf{opt}(\varphi) = 1$ thì dĩ nhiên là tồn tại một chứng minh $\pi$ (tương ứng với truth assignment thỏa mãn toàn bộ $\varphi$ ) làm cho xác suất verifier chấp nhận bằng $1$ . Nếu chỉ có một tỉ lệ $\rho$ của tổng số các clauses có thể thỏa mãn được thì, bất kể chứng minh $\pi$ là gì, xác suất mà verifier chấp nhận input $x$ nhiều nhất là $\rho$ (nếu nó “chẳng may” chọn phải các clauses được thỏa mãn bởi $\pi$ ). Để giảm soundness từ $\rho$ xuống $1/2$ , ta có thể chạy verifier này $\log_2(1/\rho)$ lần độc lập, và chỉ output YES khi tất cả mọi lần chạy đều output YES. Tổng số random bits nhiều nhất là $\log_2(1/\rho)\log_2 m = O(\log |\varphi|)$ và tổng số query bits nhiều nhất là $3\log_2(1/\rho)$ . Verifier của chúng ta đúng là $(O(\log n), O(1))$ -restricted.

QED

Như vậy, chứng minh định lý PCP “chẳng qua” là chứng minh một bài toán nhất định là NP-Hard. Vậy mà tại sao định lý PCP lại là một crowned jewel của TCS trong vòng 20 năm qua? Lý do là các NP-Hard reduction thông thường không thể tạo một cái “gap” là hằng số $1/\rho$ như ta cần. Để “khuếch đại” cái gap, ta cần một vài kỹ thuật cực kỳ thú vị từ coding theory và algebraic graph theory. Sẽ nói về chứng minh định lý PCP sau. Trong bài tới, chúng ta nói thêm về các cách chứng minh hardness of approximations. Sẽ cần đến các kỹ thuật như phân tích Fourier của các hàm Bool, dùng expander graphs, vân vân. Chúng ta cũng sẽ nói đến một conjecture đang cực kỳ nổi cộm trong TCS là Unique Games Conjecture.

Chủ đề : Lý thuyết tính toán, Thuật Toán. Bookmark the permalink. Trackbacks are closed, but you can post a comment.

13 Comments

Thinh Nguyen

Posted 17/05/2009 at 2:33 am | Permalink

Ba`i 1: Gap-Max-E3SAT(1, 1-1/m) chinh la 3SAT binh thuong nen no la NP-Hard.
Ba`i 2: Vi neu thiet ke duoc mot V nhu vay thi PCP(O(log n), O(1)) se contain lop NP. Bao ham thuc nguoc lai hinh nhu la de dang.

Reply
chinhx14

Posted 18/05/2009 at 5:02 am | Permalink

ai co tai lieu lien quan den “thuat toan xap xi tuyet doi ” thi lam on post len day cho minh nha. thanks]

Reply
Thinh Nguyen

Posted 18/05/2009 at 7:13 pm | Permalink

Chi tiet hon ve bai tap so 2: Bao ham thuc nguoc lai (NP contains PCP) chung minh bang cach dua 2^r random bit strings kha di cho V chay, tu do ta se biet duoc xac suat chap nhan bang bao nhieu. Vi 2^r la da thuc n^c nen mot NP-verifier du nang luc de mo phong dieu nay. Nhu vay cai certificate cua NP-verifier o day chinh la q2^r bits trong proof \pi cua PCP-Verifier. Neu co gi sai rat mong anh Hung Ngo chi giao.

Reply
Ngô Quang Hưng

Posted 18/05/2009 at 7:57 pm | Permalink

@Thinh Nguyen: lời giải của bạn chính xác rồi! Cho cả 2 bài tập.

Reply
Thinh Nguyen

Posted 22/05/2009 at 7:08 am | Permalink

Anh Hung co the noi ro hon ve derandomization cho bai MAX-3SAT duoc khong a?
Phan expander kho qua, em sap “tau hoa nhap ma” roi.

Reply
RongChoi

Posted 22/05/2009 at 12:58 pm | Permalink

Hello Thịnh,
Hy vọng anh Hưng sẽ làm một bài về Derandomization với nhiều techniques đa dạng.
Đối với MAX-E3SAT thì khá đơn giản, hồi xưa học master mình được học như sau (tóm tắt):
- Với E3SAT thì điều quan trọng là trong từng Clause một thì 3 biến là độc lập nhau và ngẫu nhiên. Như vậy thay vì phải chọn một không gian với n biến ngẫu nhiên, ta chỉ cần làm việc trên một không gian với n biến không hoàn toàn ngẫu nhiên nhưng khi chọn 3 phần tử thì chúng độc lập nhau và ngẫu nhiên. Một không gian như vậy được gọi là 3-wise independent sample space.
- Xây dựng k-wise independent sample space khá đơn giản. Đối với một trường hữu hạn F (có q phần tử), thì tập P_k gồm tất cả các đa thức bậc nhỏ hơn k trong F sẽ sẽ cho ta cách tạo một k-wise independent sample space. (Khi k = 3 thì P_3 bao gồm $q^3$ phần tử $ax^2 + bx + c$ ): nếu ta cần n biến k-wise independent ( $n \leq m$ ) thì ta chỉ cần lấy ngẫu nhiên một đa thức f(x) trong P_k và output f(1),f(2),…,f(n).
- Không gian q^n chuỗi n phần tử ngẫu nhiên đã được thu hẹp về $q^k = poly(q)$ phần tử của P_k. Duyệt toàn bộ không gian này là hoàn thành quá trình Derandomization.

Reply
RongChoi

Posted 22/05/2009 at 1:04 pm | Permalink

coquille: thay ( $n \leq m$ ) bằng ( $n \leq q$ ).
@anh Hưng: blog có thể cài chế độ preview để trước khi post đọc lại 1 lần không?

Reply
Ngô Quang Hưng

Posted 22/05/2009 at 3:02 pm | Permalink

Hi RongChoi,

Ừ, để tôi tìm preview plugin xem sao.

Về derandomization thì đúng là cần một chuỗi bài khác. Phương pháp dùng 3-wise ind. dist. như RongChoi nói cũng được; trong bài tôi nhắc đến phương pháp conditional expectation để derandomize max-e3sat; p.p. này khác với p.p. dùng limited independence.

Đại khái, $E[X] = 7m/8 = \frac 1 2 E[X \ | \ x_1=1] + \frac 1 2 E[X \ | \ x_1=0]$ . Do đó chắc chắn một trong hai biểu thức $E[X \ | \ x_1=1]$ hoặc $E[X \ | \ x_1=0]$ là $\geq 7m/8$ . Cả hai biểu thức này đều tính được trong poly-time. Ta gán $x_1$ giá trị làm cho biểu thức tương ứng $\geq 7m/8$ . Rồi, recursively gán $x_2, \dots, x_n$ .

P.P. dùng conditional expectation vẫn tìm qua uniform distribution trên toàn bộ $\{0,1\}^n$ chứ không cần tạo 3-wise ind. dist. như p.p kia.

Reply
Thinh Nguyen

Posted 22/05/2009 at 5:59 pm | Permalink

Em thấy có bài báo cua Karloff và Zwick, họ chưa chứng minh (mới chỉ có strong evidence) rằng thuật toán của họ là $7/8$ -approximation algorithm cho MAX-3SAT.

Về phương pháp conditional expectation trong slide năm 2008 của anh Hưng, em thấy rằng các expected value được tính toán đều là các giá trị cố định theo input hết. Như vậy thuật toán của ta là hoàn toàn tất định (đương nhiên vì ta đang derandomize) nhưng như vậy em không thấy có liên quan gì giữa các giá trị $E[]$ được tính toán và số clauses rốt cuộc được satisfied. Nói cách khác, em không nghĩ là ta có thể chứng minh được thuật toán dựa trên conditional expectation là 7/8-approximation algorithm.

Về phương pháp 3-wise independent sample space em chưa hiểu nên chưa comment được.

Reply
Ngô Quang Hưng

Posted 22/05/2009 at 6:38 pm | Permalink

@Thịnh,

Zwick có bài năm 2002 hoàn tất cái evidence đó rồi.

Về conditional expectation method thì Thịnh cứ nghĩ tiếp. Khi nào xong chuỗi bài này tôi sẽ quay lại với derandomization. Dĩ nhiên là slides của tôi … đúng

Reply
Thinh Nguyen

Posted 22/05/2009 at 6:59 pm | Permalink

Vâng ạ

Reply
RongChoi

Posted 23/05/2009 at 6:11 am | Permalink

Hi Thịnh,
$E[ C= \neg x_1 \vee x_2 \vee x_3 \ | \ x_1=1] = \frac34$
PS: Ngoài lề tí, không biết đã rong chơi đâu đó gặp Thịnh chưa nhỉ?

Reply
Thinh Nguyen

Posted 23/05/2009 at 7:01 am | Permalink

Hi RC huynh,

Chắc là chưa ạ, em chưa tham dự VietCRYPT, RIVF hay các conf. tương tự như thế bao giờ?
Chắc chắn em sẽ còn phải học hỏi nhiều.

Lẽ ra cũng có thể tham dự RIVF một hai lần nhưng em không theo hướng nghiên cứu dynamical systems rời rạc của “our common relation” nữa nên đành thôi…

Reply