Loại định nghĩa và phân tích độ cứng của một vấn đề, sử dụng "thí nghiệm", có phải là tiêu chuẩn để phân tích độ phức tạp của vấn đề không?

Trong cuốn Giới thiệu về mật mã hiện đại của Katz, có một số bài toán khó, và đối với mỗi bài toán, có một thử nghiệm, trong đó thuật toán tạo ra một thể hiện sự cố và một thuật toán khác giải quyết thể hiện sự cố. Ví dụ, xét bài toán logarit rời rạc trong 9.3.2:

Đặt GG là một thuật toán tạo nhóm mà với mỗi n, tạo ra (G,q,p).

Gọi A là thuật toán giải bài toán.

Thử nghiệm logarit rời rạc DLog_{A,GG} (n):

1. Chạy GG(1^n ) để thu được (G , q, g), trong đó G là nhóm tuần hoàn có thứ tự q (với kqk = n) và g là bộ tạo của G .
2. Chọn một h thống nhất trong G .
3. A được đưa ra G , q, g, h và đầu ra x trong Z_q .
4. Đầu ra của thử nghiệm được xác định là 1 nếu g^x = h và 0 nếu ngược lại.

ĐỊNH NGHĨA 9.63 Chúng ta nói rằng bài toán logarit rời rạc là khó so với GG nếu đối với tất cả các thuật toán thời gian đa thức xác suất A tồn tại một hàm không đáng kể sao cho Pr[DLog A,GG(n) = 1] = negl(n).

Đó có phải là loại định nghĩa và phân tích độ khó của một vấn đề, liên quan đến khái niệm "thử nghiệm", tiêu chuẩn để phân tích độ phức tạp của các vấn đề nói chung (không chỉ trong mật mã)?

Các sách về phân tích độ phức tạp của vấn đề có sử dụng loại định nghĩa và phân tích độ khó của vấn đề này không?

Cảm ơn.