Optimal Approximations and Polynomially Levelable Sets
From MaRDI portal
Publication:3787474
DOI10.1137/0215027zbMath0644.68054MaRDI QIDQ3787474
Pekka Orponen, Uwe Schoening, David A. Russo
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
computational complexity; approximation algorithms; polynomial reductions; paddability; polynomial levelability; intractable sets; self reducibility
68Q25: Analysis of algorithms and problem complexity
Related Items
Productive functions and isomorphisms, On sets polynomially enumerable by iteration, Exponential-time and subexponential-time sets, On the size of classes with weak membership properties, Better approximations of non-Hamiltonian graphs, Genericity, Randomness, and Polynomial-Time Approximations