Skip to main content
fix Zoo link
Source Link
András Salamon
  • 2.4k
  • 2
  • 18
  • 33

The best reference for relationships between complexity classes is the Complexity ZooComplexity Zoo. It also includes useful sections such as the Petting Zoo and the Special Exhibit of quantum classes. Perhaps because the Zoo is so extensive (nearly 500 entries currently), new classes are added regularly, while many old classes have yet to be added, no-one has written a comprehensive survey.

Some of the interesting structure of the lattice of classes is captured by descriptive complexity, which relates many of the main classes to fragments of logic.

Recent textbooks like Arora/Barak, Kozen, and Sipser do cover many of the "standard" relationships you mention.

The best reference for relationships between complexity classes is the Complexity Zoo. It also includes useful sections such as the Petting Zoo and the Special Exhibit of quantum classes. Perhaps because the Zoo is so extensive (nearly 500 entries currently), new classes are added regularly, while many old classes have yet to be added, no-one has written a comprehensive survey.

Some of the interesting structure of the lattice of classes is captured by descriptive complexity, which relates many of the main classes to fragments of logic.

Recent textbooks like Arora/Barak, Kozen, and Sipser do cover many of the "standard" relationships you mention.

The best reference for relationships between complexity classes is the Complexity Zoo. It also includes useful sections such as the Petting Zoo and the Special Exhibit of quantum classes. Perhaps because the Zoo is so extensive (nearly 500 entries currently), new classes are added regularly, while many old classes have yet to be added, no-one has written a comprehensive survey.

Some of the interesting structure of the lattice of classes is captured by descriptive complexity, which relates many of the main classes to fragments of logic.

Recent textbooks like Arora/Barak, Kozen, and Sipser do cover many of the "standard" relationships you mention.

Source Link
András Salamon
  • 2.4k
  • 2
  • 18
  • 33

The best reference for relationships between complexity classes is the Complexity Zoo. It also includes useful sections such as the Petting Zoo and the Special Exhibit of quantum classes. Perhaps because the Zoo is so extensive (nearly 500 entries currently), new classes are added regularly, while many old classes have yet to be added, no-one has written a comprehensive survey.

Some of the interesting structure of the lattice of classes is captured by descriptive complexity, which relates many of the main classes to fragments of logic.

Recent textbooks like Arora/Barak, Kozen, and Sipser do cover many of the "standard" relationships you mention.