Honest Polynomial Reducibilities, Recursively Enumerable Sets, and the P=?NP Problem
Klaus Ambos‐Spies · 1987
A set A is ≤P-minimal, ≤P any polynomial time reducibility, if it is not polynomial time computable and any set Β which ≤P-reduces to A is either polynomial time computable or ≤P-equivalent to A. By extending a result of Homer [8], we show that P=NP implies the existence of recursively enumerable ≤hPm-minimal and ≤hpT-minimal sets, where ≤hPmand ≤hPTdenote the polynomially honest versions of polynomial time many-one and Turing reducibility, respectively. Furthermore, structural properties related to ≤hPm(T)-minimality are investigated.