Complexity classes | Circuit complexity

NC (complexity)

In computational complexity theory, the class NC (for "Nick's Class") is the set of decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors. In other words, a problem with input size n is in NC if there exist constants c and k such that it can be solved in time O(logc n) using O(nk) parallel processors. Stephen Cook coined the name "Nick's class" after Nick Pippenger, who had done extensive research on circuits with polylogarithmic depth and polynomial size. Just as the class P can be thought of as the tractable problems (Cobham's thesis), so NC can be thought of as the problems that can be efficiently solved on a parallel computer. NC is a subset of P because polylogarithmic parallel computations can be simulated by polynomial-time sequential ones. It is unknown whether NC = P, but most researchers suspect this to be false, meaning that there are probably some tractable problems that are "inherently sequential" and cannot significantly be sped up by using parallelism. Just as the class NP-complete can be thought of as "probably intractable", so the class P-complete, when using NC reductions, can be thought of as "probably not parallelizable" or "probably inherently sequential". The parallel computer in the definition can be assumed to be a parallel, random-access machine (PRAM). That is a parallel computer with a central pool of memory, and any processor can access any bit of memory in constant time. The definition of NC is not affected by the choice of how the PRAM handles simultaneous access to a single bit by more than one processor. It can be CRCW, CREW, or EREW. See PRAM for descriptions of those models. Equivalently, NC can be defined as those decision problems decidable by a uniform Boolean circuit (which can be calculated from the length of the input, for NC, we suppose we can compute the Boolean circuit of size n in logarithmic space in n) with polylogarithmic depth and a polynomial number of gates with a maximum fan-in of 2. RNC is a class extending NC with access to randomness. (Wikipedia).

Video thumbnail

The chaotic complexity of natural numbers | Data structures in Mathematics Math Foundations 175

This is a sobering and perhaps disorienting introduction to the fact that arithmetic with bigger numbers starts to look quite different from the familiar arithmetic that we do with the small numbers we are used to. The notion of complexity is key in our treatment of this. We talk about bot

From playlist Math Foundations

Video thumbnail

Clojure Conj 2012 - Whence Complexity?

Whence Complexity? by: Michael Nygard Quantum Mechanics and General Relativity don't agree on much, but both claim that every physical process is perfectly reversible. The Second Law of Themodynamics says, "Not likely!" The Second Law may win in the long run, but today, at (nearly) every

From playlist Clojure Conf 2012

Video thumbnail

Complex numbers are AWESOME

Why are complex numbers awesome? What are they and how are they useful? Free ebook http://bookboon.com/en/introduction-to-complex-numbers-ebook Test your understanding via a short quiz http://goo.gl/forms/3T2ZqTfgrL Make learning "complex" numbers easy through an interactive, fun and

From playlist Intro to Complex Numbers

Video thumbnail

Mathematical modeling of evolving systems

Discover the multidisciplinary nature of the dynamical principles at the core of complexity science. COURSE NUMBER: CAS 522 COURSE TITLE: Dynamical Systems LEVEL: Graduate SCHOOL: School of Complex Adaptive Systems INSTRUCTOR: Enrico Borriello MODE: Online SEMESTER: Fall 2021 SESSION:

From playlist What is complex systems science?

Video thumbnail

MF150: What exactly is a set? | Data Structures in Mathematics Math Foundations | NJ Wildberger

What exactly is a set?? This is a crucial question in the modern foundations of mathematics. Here we begin an examination of this thorny issue, first by discussing the usual English usage of the term, as well as alternate terms, such as collection, aggregate, bunch, class, menagerie etc th

From playlist Math Foundations

Video thumbnail

Lower Bound on Complexity - Intro to Algorithms

This video is part of an online course, Intro to Algorithms. Check out the course here: https://www.udacity.com/course/cs215.

From playlist Introduction to Algorithms

Video thumbnail

Deeper Combinatorial Lower Bounds - Siu Man Chan

Siu Man Chan Princeton University January 21, 2014 We will discuss space and parallel complexity, ranging from some classical results which motivated the study, to some recent results concerning combinatorial lower bounds in restricted settings. We will highlight some of their connections

From playlist Mathematics

Video thumbnail

Charles Stine: The Complexity of Shake Slice Knots

Charles Stine, Brandeis University Title: The Complexity of Shake Slice Knots It is a well studied conjecture that a shake slice knot is in fact slice. Many counterexamples have been given, but most are close to being slice in a technical sense. In this talk, we will give a precise way to

From playlist 39th Annual Geometric Topology Workshop (Online), June 6-8, 2022

Video thumbnail

Matthew Kennedy: Noncommutative convexity

Talk by Matthew Kennedy in Global Noncommutative Geometry Seminar (Europe) http://www.noncommutativegeometry.nl/ncgseminar/ on May 5, 2021

From playlist Global Noncommutative Geometry Seminar (Europe)

Video thumbnail

Keynote Presentation: Embracing Complexity

Get a Free Trial: https://goo.gl/C2Y9A5 Get Pricing Info: https://goo.gl/kDvGHt Ready to Buy: https://goo.gl/vsIeA5 Complexity is neither good nor bad. It is a reality of life. It is a condition that must be addressed whether you want to build a smart system or understand the world aroun

From playlist MATLAB Virtual Conference 2013

Video thumbnail

Video 3: The Binomial Theorem

MIT HFH.101 Indian Institutes of Technology Joint Entrance Exam Preparation, Fall 2016 View the complete course: https://ocw.mit.edu/high-school/iit-jee/exam-prep Instructor: Rohit Kannan This video details the binomial theorem, illustrates its application, and derives some related result

From playlist MIT Indian Institutes of Technology Joint Entrance Exam Preparation, Fall 2016

Video thumbnail

Johannes Nicaise: The non-archimedean SYZ fibration and Igusa zeta functions - part 2/3

Abstract : The SYZ fibration is a conjectural geometric explanation for the phenomenon of mirror symmetry for maximal degenerations of complex Calabi-Yau varieties. I will explain Kontsevich and Soibelman's construction of the SYZ fibration in the world of non-archimedean geometry, and its

From playlist Algebraic and Complex Geometry

Video thumbnail

Étale cohomology - October 29, 2020

Cup products, Kunneth, projection formula, cycle class maps (warning: my internet was unreliable today, so may be a bit choppy in parts).

From playlist Étale cohomology and the Weil conjectures

Video thumbnail

Introduction To Complete Segal Spaces by Rekha Santhanam

PROGRAM DUALITIES IN TOPOLOGY AND ALGEBRA (ONLINE) ORGANIZERS: Samik Basu (ISI Kolkata, India), Anita Naolekar (ISI Bangalore, India) and Rekha Santhanam (IIT Mumbai, India) DATE & TIME: 01 February 2021 to 13 February 2021 VENUE: Online Duality phenomena are ubiquitous in mathematics

From playlist Dualities in Topology and Algebra (Online)

Video thumbnail

Equivariant structures in mirror symmetry - James Pascaleff

James Pascaleff University of Illinois at Urbana-Champaign October 17, 2014 When a variety XX is equipped with the action of an algebraic group GG, it is natural to study the GG-equivariant vector bundles or coherent sheaves on XX. When XX furthermore has a mirror partner YY, one can ask

From playlist Mathematics

Video thumbnail

Functional Constraints on Organization and Compartmental Number by Madan Rao

PROGRAM STATISTICAL BIOLOGICAL PHYSICS: FROM SINGLE MOLECULE TO CELL ORGANIZERS: Debashish Chowdhury (IIT-Kanpur, India), Ambarish Kunwar (IIT-Bombay, India) and Prabal K Maiti (IISc, India) DATE: 11 October 2022 to 22 October 2022 VENUE: Ramanujan Lecture Hall 'Fluctuation-and-noise' a

From playlist STATISTICAL BIOLOGICAL PHYSICS: FROM SINGLE MOLECULE TO CELL (2022)

Video thumbnail

Algorithms Explained: Computational Complexity

An overview of computational complexity including the basics of big O notation and common time complexities with examples of each. Understanding computational complexity is vital to understanding algorithms and why certain constructions or implementations are better than others. Even if y

From playlist Algorithms Explained

Video thumbnail

Supersymmetric gauge theories (Lecture 4) by Shiraz Minwalla

Kavli Asian Winter School (KAWS) on Strings, Particles and Cosmology 2018 DATE:08 January 2018 to 18 January 2018 VENUE:Ramanujan Lecture Hall, ICTS Bangalore The Kavli Asian Winter School (KAWS) on Strings, Particles and Cosmology is a pan-Asian collaborative effort of high energy theori

From playlist Kavli Asian Winter School (KAWS) on Strings, Particles and Cosmology 2018

Related pages

AC (complexity) | Commutator | Euclidean algorithm | NL (complexity) | Boolean circuit | Decision problem | Big O notation | Gaussian elimination | Cobham's thesis | Majority function | Alternating Turing machine | Sylvester matrix | P-complete | L (complexity) | Addition | Matrix multiplication | Solvable group | Computational complexity theory | P (complexity) | Conjugacy class | Carry-lookahead adder | Binary tree