scientific article; zbMATH DE number 3985202

MaRDI QIDQ3749045zbMATH OpenFDO

Authors Uwe Schöning

Publication date 1986

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)

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

Cited in

(5)

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

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)