Ngày 19/8/2026, nhóm Apple Machine Learning Research công bố nghiên cứu lý thuyết khẳng định bài toán duyệt chỉ mục đảo (inverted index traversal) đạt mức P-đầy đủ (P-completeness) khi xử lý các truy vấn Boolean dạng đồ thị có hướng không chu trình (DAG). Kết quả này làm sáng tỏ rào cản tính toán mà các hệ thống tìm kiếm thông tin đang gặp phải khi phục vụ các tác tử trí tuệ nhân tạo (AI agents) thực thi các tác vụ suy luận phức tạp.
Theo báo cáo của Apple, các AI agent hiện đại đang ngày càng dựa nhiều vào hạ tầng cơ sở dữ liệu và công cụ tìm kiếm để triển khai các quy trình làm việc suy luận kết hợp mạng nơ-ron và ký hiệu học (neuro-symbolic reasoning). Trong quá trình xử lý, các chuỗi logic này thường được biên dịch thành những cấu trúc truy vấn Boolean lồng ghép nhiều tầng và mang tính phi đơn điệu (non-monotonic) trên các trường dữ liệu văn bản. Nhóm nghiên cứu nhấn mạnh rằng những chiến lược đánh giá truy vấn truyền thống vốn được thiết kế cho tìm kiếm văn bản đơn giản đang vấp phải những giới hạn lý thuyết rất nghiêm trọng khi buộc phải xử lý dạng cấu trúc đồ thị phức tạp này.
Phân tích kỹ thuật từ Apple chỉ ra rằng các mô hình duyệt con trỏ lặp có trạng thái theo phương thức duyệt từng tài liệu một (Document-at-a-Time, viết tắt là DAAT) bị ràng buộc cấu trúc bởi lớp phức tạp tính toán NC^1 đối với việc đánh giá công thức. Khi hệ thống phải mở rộng các nhánh logic tái hội tụ (re-convergent logic) trong một đồ thị truy vấn, độ phức tạp tính toán trong trường hợp xấu nhất sẽ bị bùng nổ theo hàm mũ ở mức O(2^|Q|), với |Q| là kích thước truy vấn. Ở chiều ngược lại, các phương pháp hiện thực hóa đệ quy (recursive materialization) cũng không thể giải quyết triệt để bài toán do những rào cản về bộ nhớ và chi phí tính toán trung gian.
Với việc xác lập tính chất P-complete của bài toán duyệt chỉ mục đảo trên Boolean query DAGs, nghiên cứu của Apple chứng minh rằng các truy vấn loại này về mặt bản chất là tuần tự và rất khó để tăng tốc bằng kỹ thuật xử lý song song trên quy mô lớn. Đây là rào cản trực tiếp đối với hiệu năng của các hệ thống AI phụ thuộc vào việc tra cứu dữ liệu thời gian thực. Báo cáo của nhóm nghiên cứu Apple Machine Learning Research hiện tập trung hoàn toàn vào việc chứng minh toán học và phân tích độ phức tạp thuật toán, đồng thời chưa đưa ra kiến trúc phần mềm thay thế cụ thể cũng như chưa công bố thời điểm thử nghiệm trên các hệ thống AI thương mại.