scientific article; zbMATH DE number 4012593

From MaRDI portal
Publication:3762301





[For the entire collection see Zbl 0591.00015.] By setting up a topology on the class of recursive languages, the author shows that the class of unprovably intractable languages (within any provable time-class) is downward-closed under many-one reducibility. Applications are given to languages A that unprovably separate \(P^ A\) from \(NP^ A\), or are unprovably non-p-isomorphic to SAT. Further applications involve P-immune sets, and reducibility structures with infinitely many incomparable pairs.












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 Q3762301)