scientific article

zbMath0494.68061MaRDI QIDQ3957950

Richard J. Lipton, Richard M. Karp

Publication date: 1982

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

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)

Related Items

Tautologies with a unique Craig interpolant, uniform vs. nonuniform complexity, One-way functions and circuit complexity, Lower bounds on degrees of game-theoretic structures, Unnamed Item, Some connections between bounded query classes and non-uniform complexity., Cook's versus Valiant's hypothesis, If NP has polynomial-size circuits, then MA=AM, A survey of space complexity, Robust algorithms: a different approach to oracles