2012/04/25 by Yuqian Zhou, Zhou, YuQian
Computer Science · #C.1.3 #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Logic, Reasoning, and Knowledge #Logic, programming, and type systems
paper · pdf · doi:10.48550/arxiv.1204.5576
openalex publication_date 2012/04/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper proposes a thought experiment to search for efficient bounded algorithms of NPC problems by machine enumeration. The key contributions are: -- On Universal Turing Machines, a program's time complexity should be characterized as: execution time(n) = loading time(n) + running time(n). -- Introduces the concept of bounded algorithms; proposes a comparison based criterion to decide if a bounded algorithm is inefficient; and establishes the length upper bound of efficient bounded programs. -- Introduces the growth rate characteristic function to evaluate program complexity, which is more easily machine checkable based on observations. -- Raises the theoretical question: if there exists any bounded algorithm with polynomial execution time for NPC problems.