xu-2024-polynomial-time-llms-belong-to-ce-set

IN premise — summaries/2026/08/24/xu-2024-hallucination-innate-s3-hallucination-is-inevitable-for-llms.md

Created 2026-08-24T17:11:29+00:00

All polynomial-time-bounded LLMs (i.e., all current LLMs) belong to a computably enumerable set, placing them within the scope of Theorems 1 and 2 of Xu et al. (2024) without requiring the stronger Theorem 3.

Summary

Every LLM in use today operates within polynomial-time limits, which means it falls into a class of systems that can be explicitly listed and enumerated by a machine. This matters because it lets the system apply the core limitations proven in Theorems 1 and 2 of Xu et al. (2024) to all real-world LLMs without having to invoke the heavier, more restrictive assumptions of Theorem 3.