On \(\Pi_ 2\) theories of \(hp-T\) degrees of low sets

DOI10.1016/0304-3975(92)00077-5zbMath0801.68064OpenAlexW2027840331MaRDI QIDQ1314385

Juichi Shinoda, Teruko Tsuda, Kunimasa Aoki

Publication date: 29 November 1994

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(92)00077-5

zbMATH Keywords

reducibilitydecidabilityrecursive sets\(\Pi_ 2\) theoryhonest polynomial time Turing degrees

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Recursively (computably) enumerable sets and degrees (03D25)

Related Items (1)

Strong polynomial-time reducibility

Cites Work

• Honest polynomial time reducibilities and the \(P=?NP\) problem
• Honest polynomial degrees and \(P=?NP\)
• The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory
• Strong minimal pair theorem for the honest polynomial degrees of \(\Delta{}^ 0_ 2\) low sets
• On computational complexity and honest polynomial degrees
• Minimal degrees for polynomial reducibilities
• On the Structure of Polynomial Time Reducibility
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On \(\Pi_ 2\) theories of \(hp-T\) degrees of low sets