I just want to know if people in the complexity initiated the name 'class' because the term 'class' in Zermelo-Fraenkel set theory or not?

For me, I assume the answer is Yes; because it doesn't seem right that it was coincidence and we use all time set theories tools to prove inclusions. But what made me asked this question is that I never found a reference in Sipser and Barak-Arrora that 'class' came from ZF-set theory.

Class in ZF-set theory is a collections of sets that have some common things. For example: Class P has set of languages which all of them are bounded by polynomial of the size of the input. Note that set is different from Class, see here.

  • 1
    $\begingroup$ According to Wiktionary, a class is "A group, collection, category or set sharing characteristics or attributes." In set theory, class has a particular technical meaning, but a complexity class is not a proper class. $\endgroup$ Jul 17 at 19:53
  • 3
    $\begingroup$ The reason that "set theory tools" are used to prove inclusions is that inclusion is a set-theoretic concept. Set theory is an underlying language of mathematics. It's not used in a particularly deep way in complexity theory, though the technique of diagonalization is borrowed from set theory. $\endgroup$ Jul 17 at 19:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.