scientific article; zbMATH DE number 841094

MaRDI QIDQ4863250zbMATH OpenFDO

Authors Andrea Sorbi

Publication date 4 February 1996

zbMATH Keywords

surveyBrouwer algebrasMedvedev degreesTuring degrees of unsolvabilityMedvedev latticemass problemdegrees of difficulty

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

(25)

• Characterizing the join-irreducible Medvedev degrees
• A Note on Closed Degrees of Difficulty of the Medvedev Lattice
• The Medvedev lattice of computably closed sets
• Computability of countable subshifts in one dimension
• Coding true arithmetic in the Medvedev degrees of ^0_1 classes
• The finite intervals of the Muchnik lattice
• Topological aspects of the Medvedev lattice
• Degrees of difficulty of generalized r.e. separating classes
• A survey of Mučnik and Medvedev degrees
• Weihrauch goes Brouwerian
• Intermediate logics and factors of the Medvedev lattice
• Medvedev degrees of generalized r.e. separating classes
• Kripke models, distributive lattices, and Medvedev degrees
• Constructive logic and the Medvedev lattice
• Minimal covers in the Weihrauch degrees
• First-order logic in the Medvedev lattice
• Highness properties close to PA completeness
• Natural factors of the Medvedev lattice capturing IPC
• Some Quotient Lattices of the Medvedev Lattice
• The First Order Theories of the Medvedev and Muchnik Lattices
• Two measures of difficulty
• Characterizing the strongly jump-traceable sets via randomness
• Comparing the degrees of enumerability and the closed Medvedev degrees
• Natural factors of the Muchnik lattice capturing IPC
• Intuitionistic logic and Muchnik 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)