Optimal Approximations and Polynomially Levelable Sets
From MaRDI portal
Publication:3787474
Recommendations
- E-complete sets do not have optimal polynomial time approximations
- scientific article; zbMATH DE number 4029534
- scientific article; zbMATH DE number 3913678
- On optimal polynomial time approximations: p-levelability vs. \(\Delta\)-levelability
- Polynomial Time Productivity, Approximations, and Levelability
Cited in
(22)- E-complete sets do not have optimal polynomial time approximations
- Asymptotically Optimal Hitting Sets Against Polynomials
- scientific article; zbMATH DE number 3913678 (Why is no real title available?)
- Genericity, Randomness, and Polynomial-Time Approximations
- Better approximations of non-Hamiltonian graphs
- scientific article; zbMATH DE number 4029534 (Why is no real title available?)
- Productive functions and isomorphisms
- Polynomial Time Productivity, Approximations, and Levelability
- Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
- Nonlevelable sets and immune sets in the accepting density hierarchy inNP
- Notes on polynomial levelability
- On the size of classes with weak membership properties
- An efficient case for computing minimum linear arboricity with small maximum degree
- Resource bounded immunity and simplicity
- On sets polynomially enumerable by iteration
- On inefficient special cases of NP-complete problems
- A classification of complexity core lattices
- The structure of generalized complexity cores
- Exponential-time and subexponential-time sets
- Approximation of coNP sets by NP-complete sets
- OnP-subset structures
- On optimal polynomial time approximations: p-levelability vs. \(\Delta\)-levelability
This page was built for publication: Optimal Approximations and Polynomially Levelable Sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3787474)
