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, 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: Tương tự, một thuật toán chạy chậm nhưng trong thời gian đa thức  cho bài toán thỏa mãn tính đúng sai, mặc dù không được sử dụng trong thực tế, sẽ giải quyết được bài toán P so với NP, được coi là một trong những vấn đề quan trọng nhất chưa có lời giải trong khoa học máy tính và là một trong các bài toán thiên niên kỷ.

Tham khảo 

Phân tích thuật toán
Ký hiệu toán học