Strong polynomial-time reducibility
type: Item
instance of: scholarly article
title: Strong polynomial-time reducibility
zbMATH Open document ID: 0865.03035
DOI: 10.1016/S0168-0072(96)00037-1
author: Juichi Shinoda
published in: Annals of Pure and Applied Logic
publication date: 1997-06-11T00:00:00Z
review text: If \(f\) and \(g\) are functions then \(f\leq_T^p g\) if there is a polynomial time algorithm, with access to oracle \(g\), that can compute \(f\). Take the set of all polynomial bounded functions (that is, they don't grow too fast). If \(f\leq_T^p g\) and \(g\leq_T^p f\) then we will say \(f\) and \(g\) are equivalent. This paper considers the structure of these equivalence classes (called degrees) under \(\leq_T^p\). In this paper the author shows that, for this structure, (1) if you look at all the degrees less than a given set, they do not form an upper semilattice, (2) a weak form of the exact pair theorem holds, (3) every degree is the sup of a minimal pair. The last result is in contrast to degrees of functions where a non-diamond theorem holds.
Mathematics Subject Classification ID: 03D30
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 03D15
zbMATH DE Number: 992113
zbMATH Keywords: polynomial-time reducibility
zbMATH Keywords: oracle
zbMATH Keywords: exact pair theorem
zbMATH Keywords: minimal pair
zbMATH Keywords: polynomial Turing degrees
zbMATH Keywords: automorphism
reviewed by: William Gasarch
MaRDI profile type: Publication
cites work: Honest polynomial time reducibilities and the \(P=?NP\) problem
cites work: The theory of the polynomial many-one degrees of recursive sets is undecidable
cites work: On \(\Pi_ 2\) theories of \(hp-T\) degrees of low sets
cites work: On computational complexity and honest polynomial degrees
cites work: Nondiamond theorems for polynomial time reducibility
cites work: Minimal degrees for polynomial reducibilities
cites work: On the Structure of Polynomial Time Reducibility
cites work: Q3329452
cites work: Riemann's hypothesis and tests for primality
cites work: Every finite lattice can be embedded in a finite partition lattice
cites work: A survey of one-way functions in complexity theory
cites work: The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory
Recommended article: Polynomial time introreducibility
Recommended article: Q4733404
Recommended article: Strong and weak reducibility of algorithmic problems
Recommended article: Q4934293
Recommended article: Strong isomorphism reductions in complexity theory
Recommended article: Complete problems and strong polynomial reducibilities
Recommended article: Complete Problems and Strong Polynomial Reducibilities
Recommended article: On polynomial-time relation reducibility
Recommended article: Nondiamond theorems for polynomial time reducibility
Recommended article: Strong and robustly strong polynomial-time reducibilities to sparse sets
description: scientific article; zbMATH DE number 992113