Thuật toán thiên hà
Thuật toán thiên hà là một thuật toán mà chạy nhanh hơn các thuật toán khác với một dữ liệu vào đủ lớn, nhưng số "đủ lớn" đó lại quá lớn đến nỗi nó không được dùng trong thực tế. Thuật toán thiên hà được đặt tên bởi Richard Lipton và Ken Regan,[1] vì nó sẽ không bao giờ được sử dụng với một dữ liệu chỉ ở mức hành tinh trên Trái Đất.
Một số ứng dụng của thuật toán
Kể cả khi nó không thể được dùng trong thực tế, các thuật toán thiên hà vẫn đóng góp vào khoa học máy tính:
- Một thuật toán, kể cả nó không thực tế, vẫn có thể chỉ ra một phương pháp mà có thể dùng để tạo một thuật toán khác thực tế hơn.
- Khả năng tính toán của máy tính có thể đuổi kịp ngưỡng vượt lên, và từ đó một thuật toán phi thực tế có thể được sử dụng trong thực tế.
- Một thuật toán phi thực tế vẫn có thể chỉ ra rằng giới hạn được dự đoán có thể thực hiện được, hay những giới hạn cũ bị sai, và nâng cao hơn kiến thức của chúng ta về thuật toán. Như Lipton đã từng nói:[1]
Đó có thể là một lý do rất quan trọng và to lớn để chúng ta tìm những thuật toán đó. Ví dụ là nếu ngày mai có người nào đó tìm được một thuật toán phân tích trong thời gian rất lớn nhưng lại chứng minh được là chạy trong thời gian đa thức, nó có thể thay đổi suy nghĩ của chúng ta về phân tích. Thuật toán này có thể không bao giờ được sử dụng, nhưng nó có thể đưa nghiên cứu sâu hơn về việc phân tích.
Tương tự, một thuật toán chạy chậm nhưng trong thời gian đa thức 