Abstract: An analysis of distinctions between a mathematical notion of an algorithm and a program is presented in the paper. The notions of the number of steps and the run used memory size for a Pascal, Turbo Prolog, Visual Prolog or Refal-5 program run are introduced. For every of these programming languages a theorem setting conditions upon a function implementation for polynomial time effectiveness is presented. For a Turbo or Visual Prolog program It is proved that a polynomial number of steps is sufficient for its belonging to the class FP. But for a Pascal or Refal-5 program it is necessary that it additionally has a polynomially bounded run memory size.

Keywords: complexity theory, class FP, programming languages Pascal, Turbo Prolog, Visual Prolog and Refal- 5.

ACM Classification Keywords: F.2.m ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY Miscellaneous.

Link:

POLYNOMIAL-TIME EFFECTIVENESS OF PASCAL, TURBO PROLOG, VISUAL PROLOG AND REFAL-5 PROGRAMS

Nikolay Kosovskiy, Tatiana Kosovskaya

http://www.foibg.com/ijima/vol01/ijima01-1-p09.pdf