Equivalence Relations, Invariants, and Normal Forms, II

We consider the questions whether polynomial time solutions for the easier problems of the list for 55 (opens in new tab) yield NP solutions for the harder ones, or vice versa. We show that affirmative answers to several of these questions are equivalent to natural principles like NP = co-NP, (NP intersect co-NP) = P, and the shrinking principle for NP sets. We supplement known oracles with enough new ones to show that all questions considered have negative answers relative to some oracles. In other words, these questions cannot be answered affirmatively by means of relativizable polynomial-time Turing reductions. Finally, we show that the analogous questions in the framework where Borel sets play the role of polynomial time decidable sets have negative answers.