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.
Cited in
(9)- Diagonalization, uniformity, and fixed-point theorems
- Minimum-complexity pairing functions
- Topological perspective on the hybrid proof rules
- scientific article; zbMATH DE number 3841832 (Why is no real title available?)
- scientific article; zbMATH DE number 3873308 (Why is no real title available?)
- scientific article; zbMATH DE number 3938569 (Why is no real title available?)
- scientific article; zbMATH DE number 4002078 (Why is no real title available?)
- scientific article; zbMATH DE number 3596249 (Why is no real title available?)
- Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems)
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)