Mục lục:
- Định nghĩa - Thời gian đa thức không xác định (NP) có nghĩa là gì?
- Techopedia giải thích Thời gian đa thức không xác định (NP)
Định nghĩa - Thời gian đa thức không xác định (NP) có nghĩa là gì?
Thời gian đa thức không xác định (NP) thực sự là một điểm đánh dấu được sử dụng để chỉ ra một tập hợp các vấn đề và giới hạn về khả năng của một số loại máy tính. NP đề cập đến tập hợp các vấn đề có thể được giải quyết trong thời gian đa thức bằng máy Turing không xác định.
Techopedia giải thích Thời gian đa thức không xác định (NP)
Thời gian đa thức không xác định dựa trên cụm từ "thời gian đa thức", trong đó đề cập đến việc một thuật toán có thể thực hiện trong giới hạn nhất định có liên quan đến tốc độ hay không. Thời gian đa thức nổi lên như một cách để nói về tính khả thi của công việc và phát triển thuật toán.
Nếu một sự cố xảy ra trong thời gian đa thức không xác định, máy Turing không xác định trước tiên có thể đoán giải pháp, sau đó chạy một thuật toán có thể xác minh để xác nhận xem suy đoán đó có đúng hay không. Các chương trình định nghĩa hoặc định nghĩa máy dựa trên trình xác minh về bản chất sẽ kiểm tra các lựa chọn ban đầu của máy Turing không xác định để xác minh kết quả.
Tất cả điều này là cấu trúc tính toán lý thuyết cao. Trong khi máy học đã và đang xâm nhập vượt ra ngoài các hệ thống xác định, ý tưởng xác minh các lựa chọn không xác định vẫn còn ở giai đoạn sơ khai. Tìm kiếm sự phát triển hơn trên biên giới này của máy tính.
