Hệ thống phân cấp hữu hạn nào ngụ ý rằng bài toán đẳng cấu đồ thị là NP-hoàn chỉnh? 
Bài toán đẳng cấu đồ thị là bài toán tính toán xác định liệu hai đồ thị hữu hạn có đẳng cấu hay không. Một vấn đề quan trọng chưa được giải quyết trong lý thuyết phức tạp là liệu bài toán đẳng cấu đồ thị có nằm trong P, NP-đầy đủ hay NP-trung gian hay không. Câu trả lời không được biết, nhưng người ta tin rằng vấn đề ít nhất là không phải là NP-đầy đủ. Nếu đẳng cấu đồ thị là NP-đầy đủ, hệ thống phân cấp thời gian đa thức sẽ sụp đổ ở cấp độ thứ hai. Vì người ta tin rằng hệ thống phân cấp đa thức không sụp đổ ở bất kỳ cấp độ hữu hạn nào, nên người ta tin rằng đẳng cấu đồ thị không phải là NP-đầy đủ. Thuật toán tốt nhất cho bài toán này, do Laszlo Babai và Eugene Luks có thời gian chạy 2O (√ (n log (n))) cho các đồ thị có n đỉnh.
Hệ thống phân cấp thời gian đa thức