Switch to: References

Add citations

You must login to add citations.
  1. On Nondeterminism, Enumeration Reducibility and Polynomial Bounds.Kate Copestake - 1997 - Mathematical Logic Quarterly 43 (3):287-310.
    Enumeration reducibility is a notion of relative computability between sets of natural numbers where only positive information about the sets is used or produced. Extending e‐reducibility to partial functions characterises relative computability between partial functions. We define a polynomial time enumeration reducibility that retains the character of enumeration reducibility and show that it is equivalent to conjunctive non‐deterministic polynomial time reducibility. We define the polynomial time e‐degrees as the equivalence classes under this reducibility and investigate their structure on the recursive (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • A note on the enumeration degrees of 1-generic sets.Liliana Badillo, Caterina Bianchini, Hristo Ganchev, Thomas F. Kent & Andrea Sorbi - 2016 - Archive for Mathematical Logic 55 (3-4):405-414.
    We show that every nonzero Δ20\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Delta^{0}_{2}}$$\end{document} enumeration degree bounds the enumeration degree of a 1-generic set. We also point out that the enumeration degrees of 1-generic sets, below the first jump, are not downwards closed, thus answering a question of Cooper.
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • Complexity of the -query Tautologies in the Presence of a Generic Oracle.Toshio Suzuki - 2000 - Notre Dame Journal of Formal Logic 41 (2):142-151.
    Extending techniques of Dowd and those of Poizat, we study computational complexity of in the case when is a generic oracle, where is a positive integer, and denotes the collection of all -query tautologies with respect to an oracle . We introduce the notion of ceiling-generic oracles, as a generalization of Dowd's notion of -generic oracles to arbitrary finitely testable arithmetical predicates. We study how existence of ceiling-generic oracles affects behavior of a generic oracle, by which we show that is (...)
    Download  
     
    Export citation  
     
    Bookmark   3 citations  
  • Forcing and reducibilities.Piergiorgio Odifreddi - 1983 - Journal of Symbolic Logic 48 (2):288-310.
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • Forcing and Reducibilities.Piergiorgio Odifreddi - 1983 - Journal of Symbolic Logic 48 (2):288-310.
    Download  
     
    Export citation  
     
    Bookmark   4 citations  
  • Forcing and reducibilities. II. forcing in fragments of analysis.Piergiorgio Odifreddi - 1983 - Journal of Symbolic Logic 48 (3):724-743.
    Download  
     
    Export citation  
     
    Bookmark   2 citations  
  • An effective selection theorem.Ashok Maitra - 1982 - Journal of Symbolic Logic 47 (2):388-394.
    Download  
     
    Export citation  
     
    Bookmark  
  • Notions of weak genericity.Stuart A. Kurtz - 1983 - Journal of Symbolic Logic 48 (3):764-770.
    Download  
     
    Export citation  
     
    Bookmark   12 citations  
  • Measure and category in effective descriptive set theory.Alexander S. Kechris - 1973 - Annals of Mathematical Logic 5 (4):337.
    Download  
     
    Export citation  
     
    Bookmark   24 citations  
  • Pseudo-Jump Operators. II: Transfinite Iterations, Hierarchies and Minimal Covers.Carl G. Jockusch & Richard A. Shore - 1984 - Journal of Symbolic Logic 49 (4):1205 - 1236.
    Download  
     
    Export citation  
     
    Bookmark   26 citations  
  • A recursion theoretic characterization of the Topological Vaught Conjecture in the Zermelo‐Fraenkel set theory.Vassilios Gregoriades - 2017 - Mathematical Logic Quarterly 63 (6):544-551.
    We prove a recursion theoretic characterization of the Topological Vaught Conjecture in the Zermelo‐Fraenkel set theory by using tools from effective descriptive set theory and by revisiting the result of Miller that orbits in Polish G‐spaces are Borel sets.
    Download  
     
    Export citation  
     
    Bookmark  
  • Almost weakly 2-generic sets.Stephen A. Fenner - 1994 - Journal of Symbolic Logic 59 (3):868-887.
    There is a family of questions in relativized complexity theory--weak analogs of the Friedberg Jump-Inversion Theorem--that are resolved by 1-generic sets but which cannot be resolved by essentially any weaker notion of genericity. This paper defines aw2-generic sets. i.e., sets which meet every dense set of strings that is r.e. in some incomplete r.e. set. Aw2-generic sets are very close to 1-generic sets in strength, but are too weak to resolve these questions. In particular, it is shown that for any (...)
    Download  
     
    Export citation  
     
    Bookmark