Trong lý thuyết độ phức tạp tính toán, giảm thời gian đa thức là một phương pháp giải một bài toán bằng cách sử dụng mộtkhác. Giảm thời gian đa thức thường được sử dụng trong lý thuyết độ phức tạp để xác định cả các lớp phức tạp và các bài toán hoàn chỉnh cho các lớp đó. …
Thời gian được coi là đa thức là gì?
Một thuật toán được cho là có thời gian đa thức nếu thời gian chạy của nó bị giới hạn trên bởi một biểu thức đa thức ở kích thước của đầu vào cho thuật toán, tức là, T (n)=O (nk)đối với một hằng số k dương nào đó.
Làm thế nào để bạn biết một cái gì đó có phải là thời gian đa thức hay không?
3 Câu trả lời. Một thuật toán là đa thức (có thời gian chạy đa thức) nếu đối với một số k, C>0, thời gian chạy của nó trên các đầu vào có kích thước n tối đa là Cnk. Tương tự, một thuật toán là đa thức nếu đối với một số k>0, thời gian chạy của nó trên các đầu vào có kích thước n là O (nk).
Điều gì sẽ xảy ra nếu mức giảm được cho phép theo cấp số nhân?
Nếu mức giảm được cho phép theo thời gian hàm mũ, thì nó có thể giải quyết hoàn toàn vấn đề ban đầu và tạo ra một trường hợp nhỏ của vấn đề mục tiêuĐiều này có nghĩa là mọi vấn đề trong NP đều có thể giảm xuống mọi vấn đề khác theo kiểu giảm thiểu như vậy, vì vậy mọi vấn đề trong NP đều hoàn thành NP để giảm thời gian theo cấp số nhân.
Thuật toán hàm mũ là gì?
Một thuật toán được cho là thời gian hàm mũ, nếu T (n) có giới hạn trên bởi 2poly( ) , trong đó poly (n) là một số đa thức trong n. Chính thức hơn, một thuật toán là thời gian hàm mũ nếu T (n) bị giới hạn bởi O (2nk) đối với một hằng số k.
