Title :
Lower bounds for natural proof systems
fDate :
Oct. 31 1977-Nov. 2 1977
Abstract :
Two decidable logical theories are presented, one complete for deterministic polynomial time, one complete for polynomial space. Both have natural proof systems. A lower space bound of n/log(n) is shown for the proof system for the PTIME complete theory and a lower length bound of 2cn/log(n) is shown for the proof system for the PSPACE complete theory.
Keywords :
Chromium; Computational complexity; Computational modeling; Extraterrestrial measurements; Length measurement; Logic; Particle measurements; Polynomials; Sorting; Turing machines;
Conference_Titel :
Foundations of Computer Science, 1977., 18th Annual Symposium on
Conference_Location :
Providence, RI, USA
DOI :
10.1109/SFCS.1977.16
