complexity-theory Definition Memory Requirement Given a program Π and an input I, the memory requirement of Π on I is defined as the number of bits required in memory for the execution of Π on I.