scientific article; zbMATH DE number 3778752

MaRDI QIDQ3957950zbMATH OpenFDO

Authors Richard J. Lipton, Richard Karp

Publication date 1982

zbMATH Keywords

uniform measurenon-uniform complexity classnon-uniform complexity measuresreducibility among complexity classesuniform complexity classes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68W99)

Cited in

(10)

• One-way functions and circuit complexity
• scientific article; zbMATH DE number 7754310 (Why is no real title available?)
• Some connections between bounded query classes and non-uniform complexity.
• Tautologies with a unique Craig interpolant, uniform vs. nonuniform complexity
• Robust algorithms: a different approach to oracles
• Semiring reasoning frameworks in AI and their computational complexity
• Lower bounds on degrees of game-theoretic structures
• If NP has polynomial-size circuits, then MA=AM
• A survey of space complexity
• Cook's versus Valiant's hypothesis

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