Complexity classes

List of complexity classes

This is a list of complexity classes in computational complexity theory. For other computational and complexity subjects, see list of computability and complexity topics. Many of these classes have a 'co' partner which consists of the complements of all languages in the original class. For example, if a language L is in NP then the complement of L is in co-NP. (This does not mean that the complement of NP is co-NP—there are languages which are known to be in both, and other languages which are known to be in neither.) "The hardest problems" of a class refer to problems which belong to the class such that every other problem of that class can be reduced to it. Furthermore, the reduction is also a problem of the given class, or its subset. (Wikipedia).

Video thumbnail

VC Dimension

Shattering, VC dimension, and quantifying classifier complexity

From playlist cs273a

Video thumbnail

What are the Types of Numbers? Real vs. Imaginary, Rational vs. Irrational

We've mentioned in passing some different ways to classify numbers, like rational, irrational, real, imaginary, integers, fractions, and more. If this is confusing, then take a look at this handy-dandy guide to the taxonomy of numbers! It turns out we can use a hierarchical scheme just lik

From playlist Algebra 1 & 2

Video thumbnail

Results and open problems in theory of quantum complexity - Anindya De

Andris Ambainis University of Latvia; Member, School of Mathematics April 22, 2014 I will survey recent results and open problems in several areas of quantum complexity theory, with emphasis on open problems which can be phrased in terms of classical complexity theory or mathematics but ha

From playlist Mathematics

Video thumbnail

GT23. Composition and Classification

Abstract Algebra: We use composition series as another technique for studying finite groups, which leads to the notion of solvable groups and puts the focus on simple groups. From there, we survey the classification of finite simple groups and the Monster group.

From playlist Abstract Algebra

Video thumbnail

11b Machine Learning: Computational Complexity

Short lecture on the concept of computational complexity.

From playlist Machine Learning

Video thumbnail

Big O Notation: A Few Examples

This video is about Big O Notation: A Few Examples Time complexity is commonly estimated by counting the number of elementary operations (elementary operation = an operation that takes a fixed amount of time to preform) performed in the algorithm. Time complexity is classified by the nat

From playlist Computer Science and Software Engineering Theory with Briana

Video thumbnail

Periodic Classification of Elements - Introduction | Don't Memorise

Imagine you have to begin a library. And you have thousands of books of different genre. How would you arrange the books? Will you keep all the books together. Nope! For people to find the books of their interest easily you will arrange them in groups. Similarly, even in Chemistry, there a

From playlist Periodic Classification

Video thumbnail

Determine a Time Complexity of Code Using Big-O Notation: O(1), O(n), O(n^2)

This video explains how to determine the time complexity of given code. http://mathispower4u.com

From playlist Additional Topics: Generating Functions and Intro to Number Theory (Discrete Math)

Video thumbnail

Omer Bobrowski: Random Simplicial Complexes, Lecture I

A simplicial complex is a collection of vertices, edges, triangles, tetrahedra and higher dimensional simplexes glued together. In other words, it is a higher-dimensional generalization of a graph. In recent years there has been a growing effort in developing the theory of random simplicia

From playlist Workshop: High dimensional spatial random systems

Video thumbnail

Paul GUNNELLS - Cohomology of arithmetic groups and number theory: geometric, ... 4

In this lecture series, the first part will be dedicated to cohomology of arithmetic groups of lower ranks (e.g., Bianchi groups), their associated geometric models (mainly from hyperbolic geometry) and connexion to number theory. The second part will deal with higher rank groups, mainly

From playlist École d'Été 2022 - Cohomology Geometry and Explicit Number Theory

Video thumbnail

Julien Grivaux - The Lie algebra attached to a tame closed embedding

Abstract: If X is a smooth closed subscheme of an ambient smooth scheme Y, Calaque, Caldararu and Tu have endowed the shifted normal bundle NX/Y[−1] with a derived Lie algebroid structure. This structure generalizes the Lie algebra structure on the shifted tangent bundle TX[−1] on a smoot

From playlist Algebraic Analysis in honor of Masaki Kashiwara's 70th birthday

Video thumbnail

Optional Recitation | MIT 6.00SC Introduction to Computer Science and Programming, Spring 2011

Optional Recitation: Algorithm Complexity and Class Review Instructor: Sarina Canelake View the complete course: http://ocw.mit.edu/6-00SCS11 License: Creative Commons BY-NC-SA More information at http://ocw.mit.edu/terms More courses at http://ocw.mit.edu

From playlist MIT 6.00SC Introduction to Computer Science and Programming

Video thumbnail

11. Understanding Program Efficiency, Part 2

MIT 6.0001 Introduction to Computer Science and Programming in Python, Fall 2016 View the complete course: http://ocw.mit.edu/6-0001F16 Instructor: Prof. Eric Grimson In this lecture, Prof. Grimson continues discussing different classes of algorithmic complexity, including logarithmic com

From playlist 6.0001 Introduction to Computer Science and Programming in Python. Fall 2016

Video thumbnail

Francesc Fité, Sato-Tate groups of abelian varieties of dimension up to 3

VaNTAGe seminar on April 7, 2020 License: CC-BY-NC-SA Closed captions provided by Jun Bo Lau.

From playlist The Sato-Tate conjecture for abelian varieties

Video thumbnail

3.9b - More Expressivity with Web Ontology Language - OWL 2

Information Service Engineering 2021 Prof. Dr. Harald Sack Karlsruhe Institute of Technology Summer semester 2021 Lecture 9: Knowledge Graphs - 4 3.9b More Expressivity with Web Ontology Language - OWL complex class definitions - OWL property restrictions - OWL Strict binding and loose b

From playlist ISE2021 - Lecture 09, 16.06.2021

Video thumbnail

GoGaRuCo 2010 - Keynote: (Parenthetically Speaking) by: Jim Weirich

Help us caption & translate this video! http://amara.org/v/GZSl/

From playlist GoGaRuCo 2010

Video thumbnail

Total Functions in the Polynomial Hierarchy - Robert Kleinberg

Computer Science/Discrete Mathematics Seminar I Topic: Total Functions in the Polynomial Hierarchy Speaker: Robert Kleinberg Affiliation: Cornell University Date: February 08, 2021 For more video please visit http://video.ias.edu

From playlist Mathematics

Video thumbnail

Category Theory 3.1: Examples of categories, orders, monoids

Examples of categories, orders, monoids.

From playlist Category Theory

Related pages

AC (complexity) | NSPACE | Randomized algorithm | NL (complexity) | AC0 | ACC0 | Context-free language | NTIME | Complement (complexity) | NP-easy | PPAD (complexity) | RP (complexity) | R (complexity) | ELEMENTARY | NE (complexity) | QIP (complexity) | Oracle machine | APX | ESPACE | Function problem | DTIME | EXPSPACE | PSPACE | Polynomial-time approximation scheme | 2-EXPTIME | Co-NP | PH (complexity) | PP (complexity) | EXPTIME | NP-equivalent | LOGCFL | Probabilistically checkable proof | RE (complexity) | ZPP (complexity) | S2P (complexity) | Co-NP-complete | NC (complexity) | Alternating Turing machine | P-complete | L (complexity) | Polynomial hierarchy | Exponential hierarchy | PR (complexity) | PSPACE-complete | Arthur–Merlin protocol | NP (complexity) | DSPACE | P/poly | Interactive proof system | QMA | NEXPTIME | SL (complexity) | BQP | TFNP | RL (complexity) | E (complexity) | FNP (complexity) | Computational complexity theory | P (complexity) | Optimization problem | FP (complexity) | List of computability and complexity topics | UP (complexity) | Complexity class