Tại sao bài toán logarit rời rạc lại khó?

Bây giờ, tôi tự hỏi nếu có bất kỳ đối số tốt hơn.

Cuối cùng, không, không thực sự.

Chúng tôi không có bất kỳ bằng chứng nào cho thấy việc tính toán các bản ghi rời rạc là khó. Đối với vấn đề đó, chúng tôi không có bất kỳ bằng chứng nào cho thấy bất kỳ vấn đề nào trong $NP$ (tức là, bất kỳ vấn đề nào, nếu câu trả lời là "có", thì sẽ có bằng chứng có thể kiểm tra nhanh về điều đó) là khó.

Ví dụ, chúng tôi có một số bằng chứng một phần rằng trong mô hình "hộp đen", một bản ghi rời rạc trên một nhóm có thứ tự nguyên tố là khó. Mặt khác, các giả định đưa ra được biết là sai đối với các trường hữu hạn và do đó, điều đó ít hữu ích hơn người ta mong đợi.