Count\((q)\) versus the pigeon-hole principle (Q1360313)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Count\((q)\) versus the pigeon-hole principle |
scientific article |
Statements
Count\((q)\) versus the pigeon-hole principle (English)
0 references
1 April 1998
0 references
The paper contributes to the area which studies the status of elementary counting principles (like pigeon-hole principle) in Bounded Arithmetic. Such questions are in a nontrivial way connected to some questions (like the well-known P-NP problem) in complexity theory. The author continues his previous work on solving the so-called \(\text{Count}(q)\) versus \(\text{Count}(p)\) problem; the main onstruction is here simplified. A complete classification of the mentioned \(\text{Count}(q)\) versus \(\text{Count}(p)\) problem is obtained as a corollary of the main technical theorem (which shows the existence of a certain model satisfying the \(\text{Count}(p)\) principle). Another corollary shows that the pigeon-hole principle for injective maps does not follow from any of the \(\text{Count}(q)\) principles; this solves an open question.
0 references
counting principles
0 references
Bounded Arithmetic
0 references
pigeonhole principle
0 references