POLYNOMIAL-TIME EFFECTIVENESS OF PASCAL, TURBO PROLOG, VISUAL PROLOG AND REFAL-5 PROGRAMS
Nikolay Kosovskiy, Tatiana Matveevna Kosovskaya · 2012
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.