Hidden Structure in Complexity Theory

: 08h30, ngày 05/12/2017 (Thứ Ba)

: P104 D3

: Seminar Toán rời rạc

: Nguyễn Văn Quyết

: Viện CNTT&TT - ĐH BKHN

Tóm tắt báo cáo

Complexity theory hay complexity computation là một trong những lĩnh vực quan trọng của computation theory trong đó mục tiêu cơ bản là trả lời câu hỏi P vs NP. Complexity theory gắn liền với sự ra đời của lĩnh vực Computer Science, xuất hiện không lâu sau khi Alan Turing công bố mô hình toán học đầu tiên của máy tính với sự đóng góp nền tảng bởi Stephen Cook và R. Karp. Trong chủ đề này chúng ta sẽ giới thiệu sơ lược về các kỹ thuật kinh điển gắn liền với Complexity theory như Diagonalization, Circuit lower bound, Self -reducibility, One-way-function,. . .. Mặt khác hướng nghiên cứu Hidden Structure là vấn đề được quan tâm hầu hết của các lĩnh vực toán học chẳng hạn trong giải tích tổ hợp và tổ hợp cộng tính như Terence Tao, Timothy Gowers,. . .. Việc nghiên cứu các Hidden Structure của các đối tượng mang lại đột phá trong phân tách độ phức tạp, giúp chúng ta hiểu được câu hỏi tại sao vấn đề này lại giải quyết dễ dàng hơn vấn đề khác. Đặc biệt trong lớp NP hay NP − complete, chúng ta sẽ giới thiệu ý tưởng của Hidden Structure trong một số bài toán thuộc lớp NP − complete như SAT qua một số ý tưởng từ Backdoor Set của Williams, phát triển mạnh bởi Serge Gaspers, Stefan Szeider. Những kết quả hiện tại tất nhiên còn nhiều hạn chế và khó khăn so với mục tiêu cuối cùng là phân tách độ phức tạp lớp P và NP.


Đánh giá bài viết


Xem thêm

20/11/2017. Mạng Neural
27/11/2017. Credit Scoring