Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Hai kết quả về độ phức tạp của tính tối ưu c trong thiết kế thí nghiệm
Tóm tắt
Tìm kiếm thiết kế c-tối ưu của một mô hình hồi quy là một bài toán tối ưu cơ bản trong thống kê. Chúng tôi nghiên cứu độ phức tạp tính toán của bài toán này trong trường hợp miền thí nghiệm hữu hạn. Chúng tôi hình thành một phiên bản quyết định của bài toán và chứng minh rằng bài toán này là
$\boldsymbol{\mathit{NP}}$
-hoàn chỉnh. Chúng tôi cung cấp các ví dụ về những trường hợp phức tạp tính toán của bài toán thiết kế, được khơi gợi từ mật mã. Bài toán này, do thuộc về lớp
$\boldsymbol{\mathit{NP}}$
-hoàn chỉnh, sau đó được giản lược; chúng tôi chứng minh rằng phiên bản quyết định của sự giản lược, được gọi là c-tối ưu xấp xỉ, là P-hoàn chỉnh. Chúng tôi đưa ra một định lý tương đương cho lập trình tuyến tính: chúng tôi chỉ ra rằng c-tối ưu giản lược tương đương (theo nghĩa của tính khả giảm LOGSPACE-một-nhiều) với lập trình tuyến tính tổng quát.
Từ khóa
#c-tối ưu #thiết kế thí nghiệm #độ phức tạp tính toán #lập trình tuyến tính #mật mãTài liệu tham khảo
Agrawal, M., Kayal, N., Saxena, N.: PRIMES is in P. Ann. Math. 160, 781–793 (2004)
Atkinson, A., Donev, A., Tobias, R.: Optimum Experimental Designs with SAS. Oxford University Press, Oxford (2007)
Dobkin, D., Lipton, R., Reiss, S.: Linear programming is log-space hard for P. Inf. Process. Lett. 8(2), 96–97 (1979)
Garey, M., Johnson, D.: Computers and Intractability. A Guide to the Theory of NP-Completeness. Freeman, New York (1979)
Greenlaw, R., Hoover, H., Ruzzo, W.: Limits to Parallel Computation. P-completeness Theory. Oxford University Press, Oxford (1995)
Harman, R., Jurík, T.: Computing c-optimal experimental designs using the simplex method of linear programming. Comput. Stat. Data Anal. 53, 247–254 (2008)
Khachyian, L.: A polynomial algorithm for linear programming. Dokl. Soviet Acad. Sci. 244(5), 1093–1096 (1979)
Papadimitriou, C.: Computational Complexity. Addison-Wesley, Longman (1995)
Pázman, A.: Foundations of Optimum Experimental Design. Reidel, Dordrecht (1986)
Pukelsheim, F., Rieder, S.: Efficient rounding in approximate designs. Biometrika 79, 763–770 (1992)
Schrijver, A.: Theory of Linear and Integer Programming. Wiley, New York (1986)