Talk:Propositional proof system
Latest comment: 4 years ago by Alina Morad in topic Gentzen without Cut in Picture
This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | |||||||||||
|
Header edit
The set of propositional tautologies is a coNP-complete. Sets do not have a computational complexity, but algorithms do. I would suggest to remove the whole paragraph because what it says is not explained and what is explained is not true.
Gentzen without Cut in Picture edit
According to the Cut Elimination Theorem (e.g. https://en.wikipedia.org/wiki/Cut-elimination_theorem) Gentzen with and without cut have the same effect regarding the polynomial proof of tautologies. So I think that Gentzen without cut should be replaced above below Gentzen with Cut. --Alina Morad (talk) 20:51, 5 January 2020 (UTC)