Proceedings of 1993 IEEE 8th Annual Conference on Structure in Complexity Theory

摘要

The following topics are dealt with: uncheatable benchmarks; complexity classes; computational complexity; polynomial-time optimization; p-selective sets; NP-complete problems; isomorphisms; circuit complexity; Boolean functions; oracles; counting classes; reducibility; sparse sets; formal language theory; PRAMs; and neural computation.