Logo
Unionpedia
Giao tiếp
Tải nội dung trên Google Play
Mới! Tải Unionpedia trên thiết bị Android™ của bạn!
Cài đặt
truy cập nhanh hơn trình duyệt!
 

ZPP (độ phức tạp)

Mục lục ZPP (độ phức tạp)

Trong lý thuyết độ phức tạp tính toán, ZPP (viết tắt của zero-error probabilistic polynomial time - thời gian đa thức với xác suất sai bằng không) là lớp độ phức tạp bao gồm các bài toán sao cho tồn tại máy Turing ngẫu nhiên với các tính chất sau.

8 quan hệ: Bất đẳng thức Markov, BPP (độ phức tạp), Giá trị kỳ vọng, Lý thuyết độ phức tạp tính toán, Máy tính lượng tử, Máy Turing, P (độ phức tạp), RP (độ phức tạp).

Bất đẳng thức Markov

Bất đẳng thức Markov cho một chặn trên của độ đo của tập hợp các giá trị của x được đánh dấu đỏ, tại đó giá trị của một hàm không âm f(x)\ge\epsilon. Chặn trên này được tính bằng tỉ số giữa giá trị trung bình của f và \epsilon Trong lý thuyết xác suất, Bất đẳng thức Markov cho một chặn trên cho xác suất một hàm số không âm của một biến ngẫu nhiên nhận giá trị lớn hơn một hằng số dương.

Mới!!: ZPP (độ phức tạp) và Bất đẳng thức Markov · Xem thêm »

BPP (độ phức tạp)

Trong lý thuyết độ phức tạp tính toán, BPP (viết tắt của cụm từ tiếng Anh bounded-error probabilistic polynomial) là lớp các bài toán quyết định giải được bằng máy Turing ngẫu nhiên trong thời gian đa thức, với xác suất sai không quá 1/3 cho mọi trường hợp.

Mới!!: ZPP (độ phức tạp) và BPP (độ phức tạp) · Xem thêm »

Giá trị kỳ vọng

Trong Lý thuyết xác suất, giá trị kỳ vọng, giá trị mong đợi (hoặc kỳ vọng toán học), hoặc trung bình (mean) của một biến ngẫu nhiên là trung bình có trọng số của tất cả các giá trị của thể của biến đó, hay là được tính bằng tổng các tích giữa xác suất xảy ra của mỗi giá trị có thể của biến với giá trị đó.

Mới!!: ZPP (độ phức tạp) và Giá trị kỳ vọng · Xem thêm »

Lý thuyết độ phức tạp tính toán

Lý thuyết độ phức tạp tính toán là một nhánh của lý thuyết tính toán trong lý thuyết khoa học máy tính và toán học tập trung vào phân loại các vấn đề tính toán theo độ khó nội tại của chúng.

Mới!!: ZPP (độ phức tạp) và Lý thuyết độ phức tạp tính toán · Xem thêm »

Máy tính lượng tử

Cách biểu diễn bằng Mặt cầu Bloch cho một qubit, yếu tố cơ bản trong máy tính lượng tử. Máy tính lượng tử (còn gọi là siêu máy tính lượng tử) là một thiết bị tính toán sử dụng trực tiếp các hiệu ứng của cơ học lượng tử như tính chồng chập và vướng víu lượng tử để thực hiện các phép toán trên dữ liệu đưa vào.

Mới!!: ZPP (độ phức tạp) và Máy tính lượng tử · Xem thêm »

Máy Turing

Máy Turing Máy Turing là một mô hình về thiết bị xử lý các ký tự, tuy đơn giản, nhưng có thể thực hiện được tất cả các thuật toán máy tính.

Mới!!: ZPP (độ phức tạp) và Máy Turing · Xem thêm »

P (độ phức tạp)

Trong lý thuyết độ phức tạp tính toán, P, còn được gọi là PTIME hoặc DTIME(n^), là một trong những lớp cơ bản nhất trong các lớp độ phức tạp tính toán.

Mới!!: ZPP (độ phức tạp) và P (độ phức tạp) · Xem thêm »

RP (độ phức tạp)

Trong lý thuyết độ phức tạp tính toán, RP (viết tắt của "randomized polynomial time") là lớp độ phức tạp bao gồm các bài toán sao cho tồn tại máy Turing ngẫu nhiên với các tính chất sau.

Mới!!: ZPP (độ phức tạp) và RP (độ phức tạp) · Xem thêm »

Lối raIncoming
Chào! Chúng tôi đang ở trên Facebook bây giờ! »