Lower bounds for natural proof systems
- 1 September 1977
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 254-266
- https://doi.org/10.1109/sfcs.1977.16
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
This publication has 4 references indexed in Scilit:
- Complexity of finitely presented algebrasPublished by Association for Computing Machinery (ACM) ,1977
- Space bounds for a game on graphsPublished by Association for Computing Machinery (ACM) ,1976
- The circuit value problem is log space complete for PACM SIGACT News, 1975
- Relationships between nondeterministic and deterministic tape complexitiesJournal of Computer and System Sciences, 1970