Concepedia

Reducibility

Reducibility is a formal relation in computability theory that classifies decision problems by determining whether one problem can be algorithmically transformed into another, thereby establishing relative solvability through the existence of a computable function mapping instances of the first problem to instances of the second.

849

Publications

38K

Citations

2.3K

Authors

837

Institutions

Publications per year

2017–2026

181

Parents

Publications

849

On the Structure of Polynomial Time Reducibility

Richard E. Ladner · Journal of the ACM · 1975 · 790 citations · Full text

, , +5

Structural reducibility of multilayer networks

Manlio De Domenico, Vincenzo Nicosia, Àlex Arenas et al. · Nature Communications · 2015 · 651 citations · Full text

, , +15

A comparison of polynomial time reducibilities

Richard E. Ladner, Nancy Lynch, Alan L. Selman · Theoretical Computer Science · 1975 · 414 citations

, , +10

Space-bounded reducibility among combinatorial problems

Neil D. Jones · Journal of Computer and System Sciences · 1975 · 365 citations

, , +12

The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions

Calvin C. Elgot, Martin Davis · Mathematics of Computation · 1966 · 329 citations

, , +16

1–5 of 849

Authors

2.3K

  1. AS
    Andrzej Schinzel

    Institute of Mathematics, Poland

    7 publications · 165 citations

    7

    h-index

  2. AL
    Alan L. Selman

    University at Buffalo, State University of New York, United States

    7 publications · 759 citations

    7

    h-index

  3. MO
    Mitsunori Ogiwara

    University of Electro-Communications, Japan

    6 publications · 248 citations

    6

    h-index

  4. BM
    Benjamin Martin

    University of Canterbury, New Zealand

    5 publications · 244 citations

    5

    h-index

  5. MB
    Michael Bate

    University of Cambridge, United Kingdom

    5 publications · 244 citations

    5

    h-index

1–5 of 2.3K

Institutions

837

  1. Centre National de la Recherche Scientifique

    Paris, France

    19 h-index

    65 publications

    3.1K citations

  2. Chinese Academy of Sciences

    Beijing, China

    17 h-index

    96 publications

    4.9K citations

  3. Nanjing University

    Nanjing, China

    10 h-index

    30 publications

    2.9K citations

  4. University of Chicago

    Chicago, United States

    9 h-index

    12 publications

    319 citations

  5. Massachusetts Institute of Technology

    Cambridge, United States

    9 h-index

    14 publications

    642 citations

  6. Tsinghua University

    Beijing, China

    9 h-index

    45 publications

    4.2K citations

  7. University of Wisconsin–Madison

    Madison, United States

    8 h-index

    10 publications

    603 citations

  8. Université Paris Cité

    Paris, France

    8 h-index

    9 publications

    393 citations

1–8 of 837

Venues

  1. Journal of Symbolic Logic

    37 publications · 1.8K citations

    23

    h-index

  2. Transactions of the American Mathematical Society

    TRAN · 18 publications · 666 citations

    15

    h-index

  3. Theoretical Computer Science

    16 publications · 968 citations

    14

    h-index

  4. The Journal of Physical Chemistry C

    14 publications · 789 citations

    14

    h-index

  5. SIAM Journal on Computing

    12 publications · 733 citations

    12

    h-index

1–5