Concepedia

Oracle Machines

Oracle Machines is a theoretical computational model that extends a Turing machine by incorporating an oracle—a black box capable of solving specific decision problems in a single computational step, thereby enabling the exploration of relative computability and hierarchies of unsolvability.

52

Publications

2.3K

Citations

114

Authors

62

Institutions

Publications per year

2017–2026

10

Parents

Publications

52

Relative to a Random Oracle<i>A</i>, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1

Charles H. Bennett, John Gill · SIAM Journal on Computing · 1981 · 379 citations

, , +12

The Demise of the “Greek Oracle” Model for Medical Diagnostic Systems

Randolph A. Miller, Fred E. Masarie · Methods of Information in Medicine · 1990 · 169 citations

, , +12

Quantitative Relativizations of Complexity Classes

Ronald V. Book, Timothy J. Long, Alan L. Selman · SIAM Journal on Computing · 1984 · 144 citations

, , +17

Lower bounds on the efficiency of generic cryptographic constructions

Rosario Gennaro, Luca Trevisan · 2002 · 137 citations

, , +15

Duce, an oracle-based approach to constructive induction

Stephen Muggleton · 1987 · 130 citations

, , +9

1–5 of 52

Authors

114

  1. JF
    José Félix Costa

    University of Lisbon, Portugal

    4 publications · 107 citations

    4

    h-index

  2. JV
    John V. Tucker

    Swansea University, United Kingdom

    4 publications · 107 citations

    4

    h-index

  3. EB
    Edwin Beggs

    Swansea University, United Kingdom

    4 publications · 107 citations

    4

    h-index

  4. RV
    Ronald V. Book

    University of California, Santa Barbara, United States

    3 publications · 236 citations

    3

    h-index

  5. SA
    Sergei Anfilets

    Brest State Technical University, Belarus

    2 publications · 44 citations

    2

    h-index

1–5 of 114

Institutions

62

  1. Swansea University

    Swansea, United Kingdom

    4 h-index

    8 publications

    214 citations

  2. Instituto Politécnico de Lisboa

    Lisbon, Portugal

    4 h-index

    7 publications

    194 citations

  3. University of Lisbon

    Lisbon, Portugal

    3 h-index

    6 publications

    174 citations

  4. Fundação para a Ciência e Tecnologia

    Lisbon, Portugal

    3 h-index

    5 publications

    136 citations

  5. University of California, Santa Barbara

    Santa Barbara, United States

    3 h-index

    3 publications

    202 citations

  6. Newcastle University

    Newcastle upon Tyne, United Kingdom

    2 h-index

    2 publications

    45 citations

  7. Brest State Technical University

    Brest, Belarus

    2 h-index

    12 publications

    282 citations

  8. Stony Brook University

    Stony Brook, United States

    2 h-index

    2 publications

    76 citations

1–8 of 62

Venues

  1. SIAM Journal on Computing

    6 publications · 684 citations

    6

    h-index

  2. International Journal of Foundations of Computer Science

    IJFCS · 2 publications · 25 citations

    2

    h-index

  3. International Journal of Computing

    2 publications · 44 citations

    2

    h-index

  4. 2

    h-index

  5. Theoretical Computer Science

    2 publications · 99 citations

    2

    h-index

1–5