Hàm ẩn và hàm ngược

Đây là một bài thừa giấy vẽ voi” về toán-tin thôi. Thỉnh thoảng tôi phải viết các suy nghĩ “lảm nhảm” của mình ra để cho khỏi quên, có quên thì về sau đọc lại để nhớ ra mình đã từng có lúc nghĩ như vậy. Mà tôi lại có trí nhớ kém, hay quên, kể cả các định lý mình nghĩ ra viết ra hẳn hoi rồi mà một thời gian sau quên mất là mình đã từng làm :D

Thời gian vừa qua tôi có thỉnh thoảng “bổ túc văn hóa” cho mình bằng việc tìm hiểu về vấn đề độ phức tạp. Càng tìm hiểu thì thấy nó càng rắm rối khó hiểu, hy vọng là sẽ không tẩu hỏa nhập ma :D Và cũng hiểu thêm tại sao bài toán PvsNP khó như vậy.

Theo một anecdote, thì Hilbert có nói là “nếu tôi ngủ 1000 năm rồi tỉnh dậy, câu hỏi đầu tiên của tôi sẽ là người ta đã giải được giả thuyết Riemann chưa?”. Thời Hilbert vấn đề PvsNP chưa đặt ra, chứ nếu nó đặt ra rồi, thì có khi thay vì hỏi vè Riemann, ông ta sẽ hỏi về PvsNP. Bởi vì, tại thời điểm hiện tại của thế giới của chúng ta, vấn đề P vs NP có lẽ là vấn đề toán học cơ bản nhất. Tôi không nói nó là vấn đề khó nhất — có thể có những vấn đề khác khó hơn — nhưng cơ bản nhất, theo nghĩa việc giải quyết nó sẽ ảnh hưởng đến thế giới nhiều nhất.

Tôi sẽ không phát biểu lại một cách chính xác vấn đề P vs NP ở đây: ai biết nó thì đã biết rồi, ai chưa biết thì có thể xem các tài liệu khác (bản thân trang web này cũng lần viết phát biểu chính xác vấn đề đó trong bài “Vì sao vấn đề P vs NP khó vậy?”). Chỉ nói qua về ý nghĩa của P vs NP ở đây: nếu P = NP, thì công việc sáng tạo trở nên rất dễ dàng, ai biết nghe nhạc cũng có thể thành Mozart, ai biết kiểm tra định lý cũng thành Gauss, v.v. Nếu P=NP, thì các hệ thống bảo mật hiện tại  dùng cho việc giao dịch trên internet nói chung là sẽ toi hết, vì mọi mã mở sẽ bị bẻ dễ dàng. Thế giới sẽ “khác hẳn”, nếu P=NP. Bởi vậy mà phần lớn các chuyên gia tin là P khác NP.

Về mặt chính thức, thì bài toán P vs NP chỉ mới xuất hiện vào quãng đầu những năm 1970, cùng với mấy tên tuổi như Cook, Levin, Karp. Tuy nhiên, nó đã được nhoi nhóm từ giai đoạn những năm 1950-1960, khi các nhà tin học đi tìm các thuật toán hữu hiệu hơn thay thế cho các thuật toán “brute search” mà “công cốc”, không tìm ra được và cũng không chứng minh được sự không tồn tại của các thuật toán dùng thời gian đa thức cho một số vấn đề thường gặp. Đã bao nhiêu năm qua rồi, chưa ai giải quyết được vấn đề P vs NP, tuy hầu như tuần nào cũng có người tuyên bố giải được.  Phần lớn các tuyên bố giải được bài toán P vs NP là nhảm nhí, của những người thậm chí chưa hiểu rõ phát biểu của bài toán. Tuy nhiên, vào năm 2010 có một nhà toán học gốc Ấn Độ tên là Vinay Deolalikar làm cho Hewlett Parckard  đã được “vinh quang 10 hôm” khi đưa ra lời giải dài 100 trang và đươc một số chuyên gia đầu ngành quan tâm cho đến khi phát hiện lô hổng (Bản thân ông Deolalikar là một nhà toán học ứng dụng “cứng cựa” có hiểu biết nhiều về những thứ toán lý thuyết như hình học đại số, chứ không phải loại nhảm nhí). Trong chứng minh của ông Deolalikar dùng đến 1 định lý thú vị, gọi là định lý Immerman-Verdi, mô tả lớp P bằng “logic bậc 1 có thứ tự công với một thứ toán tử qui nạp”. Đây là một định lý nổi tiếng, xuất hiện từ đầu những năm 1980, trong một chuyên ngành toán-tin gọi là “descriptive complexity” (ý của nó là: độ phức tạp về tính toán có thể biểu diễn thông qua độ phức tạp của công cụ logic cần thiết để mô tả vấn đề).  Người ta phát hiện là ông Deolalikar cũng hiểu sai ý nghĩa của định lý Immerman-Verdi khi dùng nó trong chứng minh!

Mức độ hiểu biết của tôi về vấn đề P vs NP vẫn còn rất ú ớ, tuy nhiên tôi có cảm giác là định lý Immerman-Verdi chỉ cho ta một cách trình bầy lại vấn đề P vs NP bằng một ngôn ngữ khác thôi, chứ chưa phải là một bước tiến lớn trong việc giải bài toán P vs NP. Nó làm nhớ lại truyện cười: có 1 nhà toán học tham vọng  chứng minh được giả thuyết Riemann bằng mọi cách, đến mức thỏa thuận với quỉ sứ là bán linh hồn cho quỉ sứ để đổi lấy chứng minh, và giao hẹn là sau 2 tuần thì quỉ sứ sẽ đem chứng minh đến. Nhưng rồi đợi mãi, đợi mãi không thấy quỉ sứ đâu, cho đến 1 hôm quỉ sứ xuất hiện mặt mày bơ phờ, nói với nhà toán học là: tôi chưa có chứng minh, nhưng có cái bổ đề này hay lắm! :D

Quay lại P vs NP, vấn đề này có thể phát biểu nôm na ở dạng: có những ánh xạ mà tính theo chiều xuôi thì dễ, nhưng theo chiều ngược thì không thể tính nổi.  Các ánh xạ (hay hàm số) mà tính xuôi dễ, tính ngược khó đến mức không thể tính nổi, được gọi là các one-way function.
Nói một cách chặt chẽ, thì nếu tồn tại one-way function, thì P khác NP. Nhưng từ việc P khác NP chưa suy ra được là tồn tại one-way function. Tuy nhiên, Nếu P khác NP, thì có nghĩa là có các hàm ẩn định nghĩa thì dễ nhưng tính toán thì không thể tính nổi. Như vậy, về mặt toán học, ta có hai vấn đề rất sát nhau, mà trong toán gọi là hàm ngược và hàm ẩn.

Trong giải tích toán học, thì các định lý tồn tại hàm ngược và hàm ẩn nói chung là có cùng một chứng minh, có thể gộp chung thành một định lý. Bởi vậy, trong tin học, vấn đề tồn tại one-way function (không tính được hàm ngược) và vấn đề P khác NP (không tính được hàm ẩn) cũng có thể coi là (các trường hợp riêng của) cùng một vấn đề.

Tất nhiên, những điều tôi viết phía trên chưa giúp ích gì hết cho việc giải quyết bài toán P vs NP. Nó chỉ cho thấy là, thay vì xét bài toán này, có thể đi nghiên cứu các hàm và việc đảo nghịch chúng. Trong giải tích toán học, có các mở rộng định lý hàm ẩn/hàm ngược lên các không gian kiểu “scaled tamed Frechet”, sử dụng các loại “interpolation” và “smoothing operators”. Biết đâu có thể chuyển các ý tưởng giải tích sang để có một mô ta mới cho hàm ngược / hàm ẩn trong tin học :D

Thực ra thì các hàm ẩn và hàm ngược phía trên phải hiểu là ẩn/ngược một bên (bên phải) với miền xác định là ảnh của hàm ban đầu thôi, vì bản thân hàm ban đầu nói chung không có tính chất onto hay bijective. Có vẻ là chính các tính chất many-to-one và non-onto là các tính chất khiến cho việc tính hàm ngược.hàm ẩn trở nên rất khó. Nếu một hàm xuôi là bijective, thì khả năng tính được hàm ngược dễ hơn?! (Đặc biệt nếu có thể phân tích một ánh xạ bijective như vậy thành composition của những ánh xạ elementary, thì tính được ánh xạ ngược, vì ngược của elementary cũng là elementary ?!)

Print Friendly

3 comments to Hàm ẩn và hàm ngược

  • Giá mà có nhiều người làm việc”thừa giấy vẽ voi” như anh thì thật là hay. Vì những ý tưởng có thể được chia sẻ và biết đâu nó lại gặp kinh nghiệm ở đâu đó và tạo ra được một giá trị phi thường.

  • D_Lucy MonsterID Icon D_Lucy

    Giúp làm hộ bài này với ạ.thank tr
    Gọi g(x) là hàm số ngược của f(y)=y^5+y+1
    Tính y´(1)

  • admin MonsterID Icon admin

    D_Lucy: có thể dùng công thức sau

    tích của đạo hàm của hàm xuôi với đạo hàm của hàm ngược (tại các điểm tương ứng ngược-xuôi) thì bằng 1.

    Khi y = 0 thì x = 1 nên g'(1) = 1/ f'(0)

Leave a Reply

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

  

  

  

This blog is kept spam free by WP-SpamFree.