Optimal Approximations and Polynomially Levelable Sets
From MaRDI portal
Publication:3787474
DOI10.1137/0215027zbMATH Open0644.68054OpenAlexW1964186004MaRDI QIDQ3787474FDOQ3787474
Authors: Pekka Orponen, David A. Russo, Uwe Schöning 
Publication date: 1986
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0215027
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
computational complexityapproximation algorithmspolynomial reductionspaddabilitypolynomial levelabilityintractable setsself reducibility
Cited In (22)
- Better approximations of non-Hamiltonian graphs
- Title not available (Why is that?)
- E-complete sets do not have optimal polynomial time approximations
- Genericity, Randomness, and Polynomial-Time Approximations
- A classification of complexity core lattices
- The structure of generalized complexity cores
- Resource bounded immunity and simplicity
- Notes on polynomial levelability
- On optimal polynomial time approximations: p-levelability vs. \(\Delta\)-levelability
- Productive functions and isomorphisms
- Exponential-time and subexponential-time sets
- On the size of classes with weak membership properties
- On sets polynomially enumerable by iteration
- Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
- Approximation of coNP sets by NP-complete sets
- Title not available (Why is that?)
- Nonlevelable sets and immune sets in the accepting density hierarchy inNP
- OnP-subset structures
- On inefficient special cases of NP-complete problems
- Polynomial Time Productivity, Approximations, and Levelability
- An efficient case for computing minimum linear arboricity with small maximum degree
- Asymptotically Optimal Hitting Sets Against Polynomials
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)
