Ore revisited: An algorithmic investigation of the simple commutator promise problem (Oystein Ore)
Luận án · Tiến sĩ · năm 2005 · đề tài tham khảo
| Loại tài liệu | Luận án |
|---|---|
| Bậc học | Tiến sĩ |
| Ngành | Công nghệ thông tin |
| Tác giả | James L Ulrich |
| Cơ sở đào tạo | Đại học Quốc gia TP. Hồ Chí Minh |
| Năm | 2005 |
| Nguồn | Thư viện số Đại học Quốc gia TP. Hồ Chí Minh · trang gốc |
Tóm tắt
Motivated by a desire to test the security of the pubic key exchange protocol of I. Anshel, M. Anshel, and D. Goldfeld, (“An Algebraic Method for Public-Key Cryptography”, Mathematical Research Letters, vol. 6, pp. 1-5, 1999), we study algorithmic approaches to the simple commutator decision and promise problems (SCDP/SCPP) for the braid groups Bn. We take as our point of departure a seminal paper of O. Ore, (“Some Remarks on Commutators”, Proceedings of the American Mathematical Society, Vol. 2, No. 2, pp.307-314, 1951), which studies the SCPP for the symmetric groups. Our results build on the work of H. Cejtin and I. Rivin, (“A Property of Alternating Groups”, arXiv:math.GR/0303036). We extract, from their proof that any element of the alternating subgroup of Sn can be written as a product of two n-cycles, an explicit algorithm for solving the SCPP for Sn. We define a model of computation with respect to which the algorithm executes in time O(n2). We then extend the algorithm to a subset of permutation braids of the braid groups Bn, to show that any element of the commutator subgroup [Bn, Bn] may be efficiently written as the product of a pure braid and a simple commutator of permutation braids. We use this result to define a probabilistic approach to the SCDP/SCPP, posing for future research the question of whether such an algorithm may be made efficient with respect to a measure of complexity such as that defined in a work of I. Kapovich, A. Myasnikov, P. Schupp, V. Shpilrain (“Average-Case Complexity and Decision Problems in Group Theory”, Advances in Math. vol. 190, pp. 343-359, 2005).
Bản toàn văn lưu tại thư viện Đại học Quốc gia TP. Hồ Chí Minh
Thông tin và tóm tắt ở trên lấy từ kho số mở của thư viện trường. Bản toàn văn do thư viện trường quản lý — có nơi cho đọc trực tuyến, có nơi cần tài khoản bạn đọc của trường.
Mở tại thư viện trường ↗
Dùng tài liệu tham khảo cho đúng
- Đọc để hiểu cách người trước đặt câu hỏi, chọn phương pháp, trình bày số liệu — rồi tự làm với dữ liệu và bối cảnh của bạn.
- Ý, số liệu, bảng biểu lấy từ tài liệu này phải trích dẫn (tác giả, năm, tên đề tài, cơ sở đào tạo).
- Đề tài trùng tên vẫn làm được nếu khác đơn vị khảo sát, thời gian hoặc cách tiếp cận — nêu rõ điểm khác trong phần mở đầu.
Hướng dẫn chọn đề tài, cấu trúc và số liệu cho ngành này: Luận văn công nghệ thông tin · Hỏi đáp từng chương với người hướng dẫn số: Học Giả Số · Công cụ số: Luận Văn Số.
Đề tài cùng ngành
- Impacts of AI-Assisted Feedback on Organization and Argumentation in Academic Writing among English Major Juniors at An Giang University
- Phân loại ảnh mô bệnh học của mô vú nhằm hỗ trợ chẩn đoán ung thư vú
- Mô hình kết hợp cho bài toán rút trích thông tin từ ảnh
- Phương pháp kết hợp mạng sinh đối kháng và học liên kết trong nhận diện tấn công trong mạng khả lập trình
- Xác thực người học trực tuyến với phương pháp xác thực khuôn mặt
- Xây dựng hệ thống lưu trữ đặc trưng phục vụ cho bài toán mô hình hoá tổng hợp tiếp thị
- Phân tích dữ liệu bán hàng của công ty cổ phần bột giặt LIX và xây dựng mô hình dự báo doanh số
- Thuật toán song song cho khai thác các mẫu tuần tự có lợi ích cao phổ biến đóng
Tác giả muốn gỡ, sửa thông tin hoặc bổ sung bản toàn văn: gửi yêu cầu qua trang Liên hệ, kèm đường dẫn trang này.