Concepedia

Rudimentary reductions revisited

Eric Allender, Vivek Gore

Information Processing Letters · 1991 · 24 citations · 12 references

DOI

References

12

Parity, circuits, and the polynomial-time hierarchy

Merrick L. Furst, James B. Saxe, Michael Sipser · Theory of Computing Systems · 1984 · 939 citations

, , +11

∑11-Formulae on finite structures

Miklós Ajtai · Annals of Pure and Applied Logic · 1983 · 586 citations

, , +7

Separating the polynomial-time hierarchy by oracles

Andrew Chi-Chih Yao · 1985 · 554 citations

, , +17

On uniformity within NC1

David A. Mix Barrington, Neil Immerman, Howard Straubing · Journal of Computer and System Sciences · 1990 · 485 citations

, , +2

On uniform circuit complexity

Walter L. Ruzzo · Journal of Computer and System Sciences · 1981 · 434 citations

, , +17