Constructive complexity
From MaRDI portal
Publication:1182305
DOI10.1016/0166-218X(91)90074-7zbMath0768.68015DBLPjournals/dam/AbrahamsonFLM91OpenAlexW2912709233WikidataQ57360155 ScholiaQ57360155MaRDI QIDQ1182305
Bernard M. E. Moret, Michael A. Langston, Michael R. Fellows, Karl A. Abrahamson
Publication date: 28 June 1992
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0166-218x(91)90074-7
decision problemspolynomial-time solvabilityself-reducibilityblind oraclesconstructive theory of complexityoracle machines
Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Robust algorithms: a different approach to oracles
- On helping by robust oracle machines
- Nonconstructive advances in polynomial-time complexity
- The complexity of optimization problems
- Probabilistic algorithm for testing primality
- Disjoint Paths—A Survey
- Efficient Factoring Based on Partial Information
- The density and complexity of polynomial cores for intractable sets
- Nonconstructive tools for proving polynomial-time decidability
- On self-transformable combinatorial problems
- `` Strong NP-Completeness Results
- On the nlog n isomorphism technique (A Preliminary Report)
- The NP-completeness column: An ongoing guide
This page was built for publication: Constructive complexity
