scientific article; zbMATH DE number 841094

MaRDI QIDQ4863250zbMATH OpenFDO

Authors Andrea Sorbi

Publication date 4 February 1996

zbMATH Keywords

Brouwer algebrasdegrees of difficultymass problemMedvedev degreesMedvedev latticesurveyTuring degrees of unsolvability

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30)

Recommendations

• A Note on Closed Degrees of Difficulty of the Medvedev Lattice
• On the structure of the Medvedev lattice
• scientific article; zbMATH DE number 7650265
• scientific article; zbMATH DE number 5234254
• scientific article; zbMATH DE number 3857081
• scientific article; zbMATH DE number 3914306
• scientific article; zbMATH DE number 1643917
• The Complexity and Distribution of Hard Problems
• The Medvedev lattice of computably closed sets
• Degrees of monotone complexity

Cited in

(33)

• Two measures of difficulty
• Highness properties close to PA completeness
• Comparing the degrees of enumerability and the closed Medvedev degrees
• Constructive logic and the Medvedev lattice
• A survey of Mučnik and Medvedev degrees
• Some Quotient Lattices of the Medvedev Lattice
• The First Order Theories of the Medvedev and Muchnik Lattices
• Natural factors of the Muchnik lattice capturing IPC
• Coding true arithmetic in the Medvedev degrees of ^0_1 classes
• Intuitionistic logic and Muchnik degrees
• Characterizing the strongly jump-traceable sets via randomness
• Natural factors of the Medvedev lattice capturing IPC
• A Note on Closed Degrees of Difficulty of the Medvedev Lattice
• Medvedev degrees of generalized r.e. separating classes
• Topological aspects of the Medvedev lattice
• The finite intervals of the Muchnik lattice
• Weihrauch goes Brouwerian
• Characterizing the join-irreducible Medvedev degrees
• Minimal covers in the Weihrauch degrees
• Computability of countable subshifts in one dimension
• Categorifying computable reducibilities
• On the Weihrauch degree of the additive Ramsey theorem
• Hilbert's tenth problem for term algebras with a substitution operator
• Complemented subsets and Boolean-valued, partial functions
• Defining long words succinctly in FO and MSO
• On the first-order parts of problems in the Weihrauch degrees
• Algorithmically random series
• A topos for extended Weihrauch degrees
• The Medvedev lattice of computably closed sets
• First-order logic in the Medvedev lattice
• Degrees of difficulty of generalized r.e. separating classes
• Intermediate logics and factors of the Medvedev lattice
• Kripke models, distributive lattices, and Medvedev degrees

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4863250)