Search results for "reducibilities"

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