Concepedia

Truth-table Reducibility

Truth-Table Reducibility is a type of computability-theoretic reducibility in which a set \( A \) is reducible to a set \( B \) via a total computable function that, given an input \( n \), produces a finite Boolean combination of queries to \( B \) whose evaluation determines membership of \( n \) in \( A \).

64

Publications

3.8K

Citations

90

Authors

65

Institutions

Publications per year

2017–2026

1

Variants

Tt-reducibility

Parents

Publications

64

Handbook of mathematical logic, edited by Jon Barwise with the cooperation of H. J. Keisler, K. Kunen, Y. N. Moschovakis, and A. S. Troelstra, Studies in logic and the foundations of mathematics, vol. 90, North-Holland Publishing Company, Amsterdam, New York, and Oxford, 1978 (© 1977), xi + 1165 pp. - C. Smoryński. D.1. The incompleteness theorems. Pp. 821–865. - Helmut Schwichtenberg. D.2. Proof theory: some applications of cut-elimination. Pp. 867–895. - Richard Statman. D.3. Herbrand's theorem and Gentzen's notion of a direct proof. Pp. 897–912. - Solomon Feferman. D.4. Theories of finite type related to mathematical practice. Pp. 913–971. - A. S. Troelstra. D.5. Aspects of constructive mathematics. Pp. 973–1052. - Michael P. Fourman. D.6. The logic of topoi. Pp. 1053–1090. - Henk P. Barendregt. D.1. The type free lambda calculus. Pp. 1091–1132. - Jeff Paris and Leo Harrington. D.8. A mathematical incompleteness in Peano arithmetic. Pp. 1133–1142.

William A. Howard · Journal of Symbolic Logic · 1984 · 840 citations

, , +11

Bounded Query Classes

Klaus W. Wagner · SIAM Journal on Computing · 1990 · 294 citations

, , +17

On Cores and Prime Implicants of Truth Functions

W. V. Quine · American Mathematical Monthly · 1959 · 173 citations

, , +12

PP is closed under intersection

Richard Beigel, Nick Reingold, Daniel A. Spielman · 1991 · 160 citations

, , +17

P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP

Alan L. Selman · Theory of Computing Systems · 1979 · 153 citations

, , +12

1–5 of 64

Authors

90

  1. MO
    Mitsunori Ogiwara

    University of Electro-Communications, Japan

    4 publications · 218 citations

    4

    h-index

  2. RB
    Richard Beigel

    Yale University, United States

    4 publications · 340 citations

    4

    h-index

  3. NR
    Nick Reingold

    AT&T (United States), United States

    4 publications · 332 citations

    4

    h-index

  4. LF
    Lance Fortnow

    University of Chicago, United States

    3 publications · 89 citations

    3

    h-index

  5. OW
    Osamu Watanabe

    Tokyo Institute of Technology, Japan

    3 publications · 192 citations

    3

    h-index

1–5 of 90

Institutions

65

  1. Yale University

    New Haven, United States

    3 h-index

    5 publications

    554 citations

  2. Princeton University

    Princeton, United States

    3 h-index

    5 publications

    189 citations

  3. Universitat Politècnica de Catalunya

    Barcelona, Spain

    3 h-index

    4 publications

    101 citations

  4. University of Electro-Communications

    Tokyo, Japan

    2 h-index

    3 publications

    116 citations

  5. Harvard University Press

    Cambridge, United States

    2 h-index

    2 publications

    200 citations

  6. University of Würzburg

    Würzburg, Germany

    2 h-index

    3 publications

    138 citations

  7. University of Washington

    Seattle, United States

    2 h-index

    5 publications

    178 citations

  8. Tokyo Institute of Technology

    Tokyo, Japan

    2 h-index

    4 publications

    326 citations

1–8 of 65

Venues

  1. SIAM Journal on Computing

    10 publications · 714 citations

    10

    h-index

  2. Journal of Symbolic Logic

    5 publications · 939 citations

    5

    h-index

  3. Theoretical Computer Science

    3 publications · 106 citations

    3

    h-index

  4. Transactions of the American Mathematical Society

    TRAN · 3 publications · 70 citations

    3

    h-index

  5. American Mathematical Monthly

    2 publications · 271 citations

    2

    h-index

1–5