scientific article; zbMATH DE number 3985202

zbMATH Open0609.03016MaRDI QIDQ3749045FDOQ3749045

Authors: Uwe Schöning 

Publication date: 1986

Title of this publication is not available (Why is that?)

Recommendations

• On lower bounds of the closeness between complexity classes
• On one-way functions and polynomial-time isomorphisms
• Complete sets and closeness to complexity classes
• On Splitting of a Recursive Set with Polynomial Time Minimal Pairs
• Circuit-size lower bounds and non-reducibility to sparse sets

zbMATH Keywords

distanceNP-complete setEXPTIME-complete setintractable setsstructure in computationweak p-cylinder

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Complexity of computation (including implicit computational complexity) (03D15)

Cited In (5)

• Lower bound arguments with ``inaccessible numbers
• Obtaining lower bounds using artificial components
• Lower bounds and recursive methods for the problem of adjudicating conflicting claims
• Lower bounds for \(n\)-term approximations.
• On lower bounds of the closeness between complexity classes

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 Q3749045)