Logic and Complexity: Independence results and the complexity of propositional calculus

Pavel Pudlák
Additional contact information
Pavel Pudlák: Academy of Sciences of Czech Republic, Mathematical Institute

A chapter in Proceedings of the International Congress of Mathematicians, 1995, pp 288-297 from Springer

Abstract: Abstract The problem of whether $$\mathcal{P} = \mathcal{N}\mathcal{P}$$ = N 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}$$ = N ? 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}$$ = N 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.

Date: 1995
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-0348-9078-6_22

Ordering information: This item can be ordered from
http://www.springer.com/9783034890786

DOI: 10.1007/978-3-0348-9078-6_22

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().