×

zbMATH — the first resource for mathematics

Approximate counting by hashing in bounded arithmetic. (English) Zbl 1180.03055
It is shown how to formalize approximate counting via hash functions in subsystems of bounded arithmetic using variants of the weak pigeonhole principle. Several applications are also discussed, in particular an open problem of Krajíček, Pudlák and Takeuti is solved and a generalization of the tournament principle is proved (this allows the author to show that the collapse of the bounded arithmetic hierarchy implies collapse of the polynomial-time hierarchy). Two applications from computational complexity are included as well.

MSC:
03F30 First-order arithmetic and fragments
03D15 Complexity of computation (including implicit computational complexity)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Logic from Computer Science, Proceedings of a workshop held November 13–17, 1989 in Berkeley 21 pp 287– (1992)
[2] Bounded arithmetic, prepositional logic, and complexity theory 60 (1995)
[3] DOI: 10.1093/logcom/exm017 · Zbl 1132.03029 · doi:10.1093/logcom/exm017
[4] Arithmetic, proof theory, and computational complexity pp 1–
[5] Arithmetic, proof theory, and computational complexity 23 (1993)
[6] DOI: 10.1016/0022-0000(79)90044-8 · Zbl 0412.68090 · doi:10.1016/0022-0000(79)90044-8
[7] Notes on polynomially bounded arithmetic 61 pp 942– (1996)
[8] DOI: 10.1016/0020-0190(96)00016-6 · Zbl 0875.68425 · doi:10.1016/0020-0190(96)00016-6
[9] Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science pp 514– (1989)
[10] DOI: 10.1016/j.jcss.2003.07.015 · Zbl 1133.68020 · doi:10.1016/j.jcss.2003.07.015
[11] DOI: 10.2307/3612854 · Zbl 0134.43502 · doi:10.2307/3612854
[12] First-order proof theory of arithmetic 137 pp 79– (1998)
[13] Proceedings of the 15th Annual ACM Symposium on Theory of Computing pp 330– (1983)
[14] DOI: 10.1016/0168-0072(94)00057-A · Zbl 0829.03035 · doi:10.1016/0168-0072(94)00057-A
[15] DOI: 10.1007/s000370050007 · Zbl 0912.68054 · doi:10.1007/s000370050007
[16] Making infinite structures finite in models of second order bounded arithmetic pp 289–
[17] ACM Transactions on Computational Logic
[18] 134 pp 149– (1988)
[19] DOI: 10.1007/3-540-54487-9_67 · doi:10.1007/3-540-54487-9_67
[20] DOI: 10.1002/malq.200610019 · Zbl 1109.03067 · doi:10.1002/malq.200610019
[21] DOI: 10.1016/j.apal.2003.12.003 · Zbl 1057.03047 · doi:10.1016/j.apal.2003.12.003
[22] Metamathematics of first-order arithmetic (1993) · Zbl 0781.03047
[23] DOI: 10.4153/CMB-1971-007-1 · Zbl 0209.55804 · doi:10.4153/CMB-1971-007-1
[24] Randomness and computation 5 pp 73– (1989)
[25] Proceedings of RANDOM-APPROX ’99 1671 pp 131– (1999)
[26] DOI: 10.2307/3613396 · Zbl 0117.17402 · doi:10.2307/3613396
[27] Consequences of the provability of NP P/poly 72 pp 1353– (2007)
[28] Proceedings of the 7th Annual ACM Symposium on Theory of Computing pp 83– (1975)
[29] Proceedings of the 2nd International Congress of Logic, Methodology and Philosophy of Science pp 24– (1965)
[30] Provability of the pigeonhole principle and the existence of infinitely many primes 53 pp 1235– (1988) · Zbl 0688.03042
[31] DOI: 10.1006/jcss.2002.1830 · Zbl 1051.03049 · doi:10.1006/jcss.2002.1830
[32] DOI: 10.1016/0168-0072(91)90043-L · Zbl 0736.03022 · doi:10.1016/0168-0072(91)90043-L
[33] Approximate Euler characteristic, dimension, and weak pigeonhole principles 69 pp 201– (2004) · Zbl 1068.03024
[34] DOI: 10.1112/S0024611500012557 · Zbl 1034.03045 · doi:10.1112/S0024611500012557
[35] Approximate counting in bounded arithmetic 72 pp 959– (2007)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.