Efficient programs of NPC problems should be length upper-bounded, and a   thought experiment to search for them by machine enumeration
  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. 
YuQian Zhou
cs.CC