scientific article; zbMATH DE number 3778752

zbMATH Open0494.68061MaRDI QIDQ3957950FDOQ3957950

Authors: Richard J. Lipton, Richard Karp 

Publication date: 1982

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

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
• Title not available (Why is that?)
• 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)