Logic and Complexity: Independence results and the complexity of propositional calculus
Pavel Pudlák · Birkhäuser Basel eBooks · 1995
The problem of whether $$\mathcal{P} = \mathcal{N}\mathcal{P}$$ is generally recognized as one of the most important problems in contemporary mathematics. It is one of the many problems in complexity theory that have resisted for years all attempts to solve them. The problem $$\mathcal{P} = \mathcal{N}\mathcal{P}$$ ? originated in logic and thus there were some hopes that logic would help to solve it. Naturally the question of whether $$\mathcal{P} = \mathcal{N}\mathcal{P}$$ or a similar problem is independent from theories used as foundations of parts of mathematics, e.g. Peano arithmetic, also was brought up. Later more researchers started to use finite combinatorics and algebra in this field. This approach has been quite successful in solving some restricted versions of the problems, but the fundamental problems remain open.