“Natural” properties of flowchart step-counting measures

摘要

A system of program schemata is viewed as a schema for a class of natural computational complexity measures. Certain properties of this class of measures, such as recursive enumerability of complexity classes and a weak notion of “conformity,” are shown to derive from the schematic structure. Other properties, earlier proposed as “natural,” are shown to be more superficial, depending upon the interpretation given to the primitive operations. These are “properness,” “finite invariance,” and “density.” Two other natural properties of the flowchart measures are given, together with a short assessment of possible progress in defining “naturalness” in complexity measures.