Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
108 | Wolfgang Merkle, Yongge Wang |
Separations by Random Oracles and "Almost" Classes for Generalized Reducibilities. |
MFCS |
1995 |
DBLP DOI BibTeX RDF |
|
79 | Marcus Schaefer 0001, Frank Stephan 0001 |
Strong Reductions and Immunity for Exponential Time. |
STACS |
2003 |
DBLP DOI BibTeX RDF |
hardness for exponential time, polynomial time reducibilities, Computational and structural complexity |
74 | Victor L. Selivanov |
Some Reducibilities on Regular Sets. |
CiE |
2005 |
DBLP DOI BibTeX RDF |
|
68 | Patrizio Cintioli, Riccardo Silvestri |
Polynomial Time Introreducibility. |
Theory Comput. Syst. |
2003 |
DBLP DOI BibTeX RDF |
|
57 | David R. Bélanger |
Structures of Some Strong Reducibilities. |
CiE |
2009 |
DBLP DOI BibTeX RDF |
|
57 | Wolfgang Merkle |
Exact Pairs for Abstract Bounded Reducibilities. |
CSL |
1996 |
DBLP DOI BibTeX RDF |
|
57 | Montserrat Hermo |
Degrees and Reducibilities of Easy Tally Sets. |
MFCS |
1994 |
DBLP DOI BibTeX RDF |
|
57 | Alan L. Selman |
P-Selective Sets, Tally Languages, and the Behavior of Polynomial Time Reducibilities on NP. |
ICALP |
1979 |
DBLP DOI BibTeX RDF |
|
51 | Ravi Kumar 0001, D. Sivakumar 0001 |
Proofs, Codes, and Polynomial-Time Reducibilities. |
CCC |
1999 |
DBLP DOI BibTeX RDF |
reducibilities, proof systems, partial solutions |
51 | Wolfgang Merkle |
The Global Power of Additional Queries to p-Random Oracles. |
ICALP |
2000 |
DBLP DOI BibTeX RDF |
|
51 | Klaus Ambos-Spies, Elvira Mayordomo, Xizhong Zheng |
A Comparison of Weak Completeness Notions. |
CCC |
1996 |
DBLP DOI BibTeX RDF |
Weak Completeness, Measure, Genericity, Completeness |
46 | Irakli O. Chitaia, Keng Meng Ng, Andrea Sorbi, Yue Yang 0004 |
Minimal degrees and downwards density in some strong positive reducibilities and quasi-reducibilities. |
J. Log. Comput. |
2023 |
DBLP DOI BibTeX RDF |
|
45 | Jacobo Torán |
Reductions to Graph Isomorphism. |
FSTTCS |
2007 |
DBLP DOI BibTeX RDF |
Computational complexity, reducibilities, graph isomorphism |
45 | Klaus Ambos-Spies, Levke Bentzien |
Separating NP-Completeness Notions under Strong Hypotheses. |
CCC |
1997 |
DBLP DOI BibTeX RDF |
NP-completeness notions separation, strong hypotheses, NP-m-completeness, NP-T-completeness, bounded-query reducibilities, resource bounded Baire category concept, computational complexity, resource bounded measure |
40 | Andrea Sorbi |
Strong Positive Reducibilities. |
TAMC |
2009 |
DBLP DOI BibTeX RDF |
|
40 | Johann A. Makowsky |
Uniform Algebraic Reducibilities between Parameterized Numeric Graph Invariants. |
CiE |
2008 |
DBLP DOI BibTeX RDF |
|
40 | Roland Sh. Omanadze, Andrea Sorbi |
Strong Enumeration Reducibilities. |
Arch. Math. Log. |
2006 |
DBLP DOI BibTeX RDF |
Mathematics Subject Classification (2000) 03D30 |
40 | Steven Homer |
Minimal degrees for polynomial reducibilities. |
J. ACM |
1987 |
DBLP DOI BibTeX RDF |
|
34 | Alexey Stukachev |
On Mass Problems of Presentability. |
TAMC |
2006 |
DBLP DOI BibTeX RDF |
|
34 | Rodney G. Downey, Denis R. Hirschfeldt, Geoffrey LaForte |
Randomness and Reducibility. |
MFCS |
2001 |
DBLP DOI BibTeX RDF |
|
34 | Bernd Borchert, Riccardo Silvestri |
The General Notion of a Dot-Operator. |
CCC |
1997 |
DBLP DOI BibTeX RDF |
|
34 | Pierluigi Crescenzi |
A Short Guide to Approximation Preserving Reductions. |
CCC |
1997 |
DBLP DOI BibTeX RDF |
approximation preserving reductions, computational complexity, complexity, combinatorial optimization |
34 | Stephen A. Fenner, Steven Homer, Mitsunori Ogiwara, Alan L. Selman |
On Using Oracles That Compute Values. |
STACS |
1993 |
DBLP DOI BibTeX RDF |
|
34 | Miroslaw Kowaluk, Klaus W. Wagner |
Vector Language: Simple Description of Hard Instances (Extended Abstract). |
MFCS |
1990 |
DBLP DOI BibTeX RDF |
|
28 | Robert I. Soare |
Computability and Incomputability. |
CiE |
2007 |
DBLP DOI BibTeX RDF |
Turing a-machine, Church-Turing Thesis, Kurt Gödel, Turing o-machine, computable approximations, effectively continuous functions on reals, computability in analysis, strong reducibilities reexamined, computability, Alan Turing |
23 | Klaus Ambos-Spies, Rod Downey, Martin Monath |
Lowness properties for strong reducibilities and the computational power of maximal sets. |
Comput. |
2024 |
DBLP DOI BibTeX RDF |
|
23 | Bjørn Kjos-Hanssen, David J. Webb |
Strong Medvedev Reducibilities and the KL-Randomness Problem. |
CiE |
2022 |
DBLP DOI BibTeX RDF |
|
23 | Masaki Kobayashi |
Reducibilities of hyperbolic neural networks. |
Neurocomputing |
2020 |
DBLP DOI BibTeX RDF |
|
23 | Roland Sh. Omanadze |
On the connections between wttwttwttwttwtt- and QQ[Math Processing Error]Q-reducibilities. |
J. Log. Comput. |
2019 |
DBLP DOI BibTeX RDF |
|
23 | Kenshi Miyabe |
Coherence of Reducibilities with Randomness Notions. |
Theory Comput. Syst. |
2018 |
DBLP DOI BibTeX RDF |
|
23 | Nadine Losert |
Multiple permitting and bounded turing reducibilities. |
|
2018 |
RDF |
|
23 | Alex Gavryushkin, Bakhadyr Khoussainov, Frank Stephan 0001 |
Reducibilities among equivalence relations induced by recursively enumerable structures. |
Theor. Comput. Sci. |
2016 |
DBLP DOI BibTeX RDF |
|
23 | Kenshi Miyabe |
Reducibilities Relating to Schnorr Randomness. |
Theory Comput. Syst. |
2016 |
DBLP DOI BibTeX RDF |
|
23 | Luca Motto Ros, Philipp Schlicht, Victor L. Selivanov |
Wadge-like reducibilities on arbitrary quasi-Polish spaces. |
Math. Struct. Comput. Sci. |
2015 |
DBLP DOI BibTeX RDF |
|
23 | Luca Motto Ros, Philipp Schlicht |
Lipschitz and uniformly continuous Reducibilities on Ultrametric polish spaces. |
Logic, Computation, Hierarchies |
2014 |
DBLP DOI BibTeX RDF |
|
23 | Tomoyuki Yamakami |
Oracle Pushdown Automata, Nondeterministic Reducibilities, and the Hierarchy over the Family of Context-Free Languages. |
SOFSEM |
2014 |
DBLP DOI BibTeX RDF |
|
23 | Johanna N. Y. Franklin, Noam Greenberg, Frank Stephan 0001, Guohua Wu |
Anti-complex sets and reducibilities with tiny use. |
J. Symb. Log. |
2013 |
DBLP DOI BibTeX RDF |
|
23 | Ji-Won Huh, Shuji Isobe, Eisuke Koizumi, Hiroki Shizuya |
On the Length-Decreasing Self-Reducibility and the Many-One-Like Reducibilities for Partial Multivalued Functions. |
IEICE Trans. Inf. Syst. |
2013 |
DBLP DOI BibTeX RDF |
|
23 | Klaus Ambos-Spies, Timur Bakibayev |
Nontriviality for exponential time w.r.t. weak reducibilities. |
Theor. Comput. Sci. |
2013 |
DBLP DOI BibTeX RDF |
|
23 | Tomoyuki Yamakami |
Oracle Pushdown Automata, Nondeterministic Reducibilities, and the Hierarchy over the Family of Context-Free Languages |
CoRR |
2013 |
DBLP BibTeX RDF |
|
23 | Iskander Sh. Kalimullin |
Algorithmic reducibilities of algebraic structures. |
J. Log. Comput. |
2012 |
DBLP DOI BibTeX RDF |
|
23 | Barbara F. Csima, Rod Downey, Keng Meng Ng |
Limits on jump inversion for strong reducibilities. |
J. Symb. Log. |
2011 |
DBLP DOI BibTeX RDF |
|
23 | Irakli O. Chitaia, Roland Sh. Omanadze, Andrea Sorbi |
Immunity properties and strong positive reducibilities. |
Arch. Math. Log. |
2011 |
DBLP DOI BibTeX RDF |
|
23 | Luca Motto Ros |
Baire reductions and good Borel reducibilities. |
J. Symb. Log. |
2010 |
DBLP DOI BibTeX RDF |
|
23 | Arno Pauly |
On the (semi)lattices induced by continuous reducibilities. |
Math. Log. Q. |
2010 |
DBLP DOI BibTeX RDF |
|
23 | Luca Motto Ros |
Beyond Borel-amenability: Scales and superamenable reducibilities. |
Ann. Pure Appl. Log. |
2010 |
DBLP DOI BibTeX RDF |
|
23 | Klaus Ambos-Spies, Timur Bakibayev |
Nontriviality for Exponential Time w.r.t. Weak Reducibilities. |
TAMC |
2010 |
DBLP DOI BibTeX RDF |
|
23 | Luca Motto Ros |
Borel-amenable reducibilities for sets of reals. |
J. Symb. Log. |
2009 |
DBLP DOI BibTeX RDF |
|
23 | Arno Pauly |
On the (semi)lattices induced by continuous reducibilities |
CoRR |
2009 |
DBLP BibTeX RDF |
|
23 | Victor L. Selivanov |
Hierarchies and reducibilities on regular languages related to modulo counting. |
RAIRO Theor. Informatics Appl. |
2009 |
DBLP DOI BibTeX RDF |
|
23 | Victor L. Selivanov |
Fine hierarchies and m-reducibilities in theoretical computer science. |
Theor. Comput. Sci. |
2008 |
DBLP DOI BibTeX RDF |
|
23 | Sebastian Bab, Arfst Nickelsen |
One query reducibilities between partial information classes. |
Theor. Comput. Sci. |
2005 |
DBLP DOI BibTeX RDF |
|
23 | Felipe Cucker |
On sparseness, reducibilities, and complexity. |
Ann. Pure Appl. Log. |
2005 |
DBLP DOI BibTeX RDF |
|
23 | Sebastian Bab, Arfst Nickelsen |
One Query Reducibilities Between Partial Information Classes. |
MFCS |
2004 |
DBLP DOI BibTeX RDF |
|
23 | Valeriy K. Bulitko, Vadim Bulitko |
On existence of complete sets for bounded reducibilities. |
Math. Log. Q. |
2003 |
DBLP DOI BibTeX RDF |
|
23 | Valeriy K. Bulitko |
Post's Problem for Reducibilities of Bounded Complexity. |
Math. Log. Q. |
2002 |
DBLP DOI BibTeX RDF |
|
23 | Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu Watanabe 0001 |
The Difference between Polynomial-Time Many-One and Truth-Table Reducibilities on Distributional Problems. |
Theory Comput. Syst. |
2002 |
DBLP DOI BibTeX RDF |
|
23 | Wolfgang Merkle |
Lattice Embeddings for Abstract Bounded Reducibilities. |
SIAM J. Comput. |
2002 |
DBLP DOI BibTeX RDF |
|
23 | Wolfgang Merkle, Yongge Wang |
Separations by Random Oracles and "Almost" Classes for Generalized Reducibilities. |
Math. Log. Q. |
2001 |
DBLP DOI BibTeX RDF |
|
23 | Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu Watanabe 0001 |
On the Difference between Polynomial-Time Many-One and Truth-Table Reducibilities on Distributional Problems. |
STACS |
2001 |
DBLP DOI BibTeX RDF |
|
23 | Timothy H. McNicholl |
Intrinsic Reducibilities. |
Math. Log. Q. |
2000 |
DBLP DOI BibTeX RDF |
|
23 | Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu Watanabe 0001 |
On the difference between polynomial-time many-one and truth-table reducibilities on distributional problems |
Electron. Colloquium Comput. Complex. |
2000 |
DBLP BibTeX RDF |
|
23 | Wolfgang Merkle |
Exact Pairs for Abstract Bounded Reducibilities. |
Math. Log. Q. |
1999 |
DBLP DOI BibTeX RDF |
|
23 | Klaus Ambos-Spies |
Polynomial Time Reducibilities and Degrees. |
Handbook of Computability Theory |
1999 |
DBLP DOI BibTeX RDF |
|
23 | Piergiorgio Odifreddi |
Reducibilities. |
Handbook of Computability Theory |
1999 |
DBLP DOI BibTeX RDF |
|
23 | Cristian Calude, André Nies |
Chaitin Omega Numbers and Strong Reducibilities. |
J. Univers. Comput. Sci. |
1997 |
DBLP DOI BibTeX RDF |
|
23 | Phil Watson |
Embeddings in the Strong Reducibilities Between 1 and npm. |
Math. Log. Q. |
1997 |
DBLP DOI BibTeX RDF |
|
23 | Wolfgang Merkle |
A generalized account of resource bounded reducibilities. |
|
1997 |
RDF |
|
23 | Manindra Agrawal |
On the Isomorphism Conjecture for Weak Reducibilities. |
J. Comput. Syst. Sci. |
1996 |
DBLP DOI BibTeX RDF |
|
23 | Anuj Dawar |
Generalized Quantifiers and Logical Reducibilities. |
J. Log. Comput. |
1995 |
DBLP DOI BibTeX RDF |
|
23 | Pavol Duris, José D. P. Rolim |
Conjunctive and Disjunctive Reducibilities to Sparse and Tally Sets Revisited. |
Int. J. Found. Comput. Sci. |
1994 |
DBLP DOI BibTeX RDF |
|
23 | Manindra Agrawal |
On the Isomorphism Problem for Weak Reducibilities. |
SCT |
1994 |
DBLP DOI BibTeX RDF |
|
23 | Judy Goldsmith, Deborah Joseph, Paul Young |
Using Self-Reducibilities to Characterize Polynomial Time |
Inf. Comput. |
1993 |
DBLP DOI BibTeX RDF |
|
23 | K. Ganesan 0001, Steven Homer |
Complete Problems and Strong Polynomial Reducibilities. |
SIAM J. Comput. |
1992 |
DBLP DOI BibTeX RDF |
|
23 | Jianer Chen |
Characterizing Parallel Hierarchies by Reducibilities. |
Inf. Process. Lett. |
1991 |
DBLP DOI BibTeX RDF |
|
23 | Ricard Gavaldà, José L. Balcázar |
Strong and Robustly Strong Polynomial-Time Reducibilities to Sparse Sets. |
Theor. Comput. Sci. |
1991 |
DBLP DOI BibTeX RDF |
|
23 | Shouwen Tang, Ronald V. Book |
Polynomial-Time Reducibilities and "Almost All" Oracle Sets. |
Theor. Comput. Sci. |
1991 |
DBLP DOI BibTeX RDF |
|
23 | Shouwen Tang, Ronald V. Book |
Reducibilities on tally and sparse sets. |
RAIRO Theor. Informatics Appl. |
1991 |
DBLP DOI BibTeX RDF |
|
23 | José L. Balcázar |
Adaptive Logspace and Depth-Bounded Reducibilities. |
SCT |
1991 |
DBLP DOI BibTeX RDF |
|
23 | Ronald V. Book, Shouwen Tang |
Characterizing Polynomial Complexity Classes by Reducibilities. |
Math. Syst. Theory |
1990 |
DBLP DOI BibTeX RDF |
|
23 | Andrzej Orlicki |
Correction to "Strong Reducibilities of Enumerations and Partial Enumerated Algebras". |
Math. Log. Q. |
1989 |
DBLP DOI BibTeX RDF |
|
23 | Klaus Ambos-Spies |
Honest Polynomial Time Reducibilities and the P = ? NP Problem. |
J. Comput. Syst. Sci. |
1989 |
DBLP DOI BibTeX RDF |
|
23 | Richard Beigel, William I. Gasarch, James C. Owings |
Nondeterministic Bounded Query Reducibilities. |
Ann. Pure Appl. Log. |
1989 |
DBLP DOI BibTeX RDF |
|
23 | Ker-I Ko |
Distinguishing Conjunctive and Disjunctive Reducibilities by Sparse Sets |
Inf. Comput. |
1989 |
DBLP DOI BibTeX RDF |
|
23 | K. Ganesan 0001, Steven Homer |
Complete Problems and Strong Polynomial Reducibilities. |
STACS |
1989 |
DBLP DOI BibTeX RDF |
|
23 | Andrzej Orlicki |
Strong Reducibilities of Enumerations and Partial Enumerated Algebras. |
Math. Log. Q. |
1988 |
DBLP DOI BibTeX RDF |
|
23 | Ronald V. Book |
Sparse Sets, Tally Sets, and Polynomial Reducibilities. |
MFCS |
1988 |
DBLP DOI BibTeX RDF |
|
23 | Ricard Gavaldà, José L. Balcázar |
Strong and Robustly Strong Polynomial Time Reducibilities to Sparse Sets. |
MFCS |
1988 |
DBLP DOI BibTeX RDF |
|
23 | Ker-I Ko |
Distinguishing bounded reducibilities by sparse sets. |
SCT |
1988 |
DBLP DOI BibTeX RDF |
|
23 | Luc Longpré, Paul Young |
Cook is faster than Karp: a study of reducibilities in NP. |
SCT |
1988 |
DBLP DOI BibTeX RDF |
|
23 | Jim Kadin |
Restricted Turing Reducibilities & the Structure of the Polynomial Time Hierarchy. |
|
1988 |
RDF |
|
23 | Klaus Ambos-Spies |
Minimal Pairs for Polynomial Time Reducibilities. |
Computation Theory and Logic |
1987 |
DBLP DOI BibTeX RDF |
|
23 | Klaus Ambos-Spies |
Honest polynomial reducibilities, recursively enumerable sets, and the P=?NP problem. |
SCT |
1987 |
DBLP BibTeX RDF |
|
23 | Richard Beigel |
Query-limited reducibilities. |
|
1987 |
RDF |
|
23 | Klaus Ambos-Spies |
Randomness, Relativizations, and Polynomial Reducibilities. |
SCT |
1986 |
DBLP DOI BibTeX RDF |
|
23 | Ker-I Ko |
Reducibilities on Real Numbers. |
Theor. Comput. Sci. |
1984 |
DBLP DOI BibTeX RDF |
|
23 | Steven Homer |
Minimal Degrees for Honest Polynomial Reducibilities |
FOCS |
1984 |
DBLP DOI BibTeX RDF |
|
23 | Piergiorgio Odifreddi |
Forcing and Reducibilities. |
J. Symb. Log. |
1983 |
DBLP DOI BibTeX RDF |
|
23 | Piergiorgio Odifreddi |
Forcing and Reducibilities. III. Forcing in Fragments of Set Theory. |
J. Symb. Log. |
1983 |
DBLP DOI BibTeX RDF |
|
23 | Piergiorgio Odifreddi |
Forcing and Reducibilities. II. Forcing in Fragments of Analysis. |
J. Symb. Log. |
1983 |
DBLP DOI BibTeX RDF |
|