Theorems in computational complexity theory

Blum's speedup theorem

In computational complexity theory, Blum's speedup theorem, first stated by Manuel Blum in 1967, is a fundamental theorem about the complexity of computable functions. Each computable function has an infinite number of different program representations in a given programming language. In the theory of algorithms one often strives to find a program with the smallest complexity for a given computable function and a given complexity measure (such a program could be called optimal). Blum's speedup theorem shows that for any complexity measure, there exists a computable function, such that there is no optimal program computing it, because every program has a program of lower complexity. This also rules out the idea there is a way to assign to arbitrary functions their computational complexity, meaning the assignment to any f of the complexity of an optimal program for f. This does of course not exclude the possibility of finding the complexity of an optimal program for certain specific functions. (Wikipedia).

Video thumbnail

The most powerful (and useless) algorithm

0:00 Intro 2:44 The Algorithm 6:38 Why it works 9:28 Code 10:41 Final Thoughts Our implementation of Universal Search: https://github.com/polylog-cs/universal-search/blob/main/code/universal_search.py Impromptu https://impromptu.fun/ More about universal search: -- To prove that the un

From playlist Algorithms

Video thumbnail

Time Dilation is not what you think it is.

When you think of time dilation in the context of Special Relativity, it's often taught as if you see things in slow motion. But that's wrong! This video covers why it is wrong as what you would see if an object was moving at relativistic speeds. I have produced a ONE MINUTE VERSION for

From playlist Nature of Light

Video thumbnail

3 Things 'Faster Than Light'

These 3 things go "faster" than the speed of light. How's that even possible? Subscribe: http://www.youtube.com/channel/UCj1gf... ↓Want more info?↓ More about the experiment: Marissa Giustina’s research: http://arxiv.org/abs/1511.03190 Advanced scientific note about Doppler: If there is

From playlist What the Physics?!

Video thumbnail

Special Relativity and Time Dilation (The Gamma Factor)

If you know the Pythagorean Theorem, you'll understand the math that describes how time slows down at high velocities.

From playlist Special Relativity - A Gentle Introduction

Video thumbnail

Lec 13 | MIT 6.172 Performance Engineering of Software Systems, Fall 2010

Lecture 13: Parallelism and Performance Instructor: Charles Leiserson View the complete course: http://ocw.mit.edu/6-172F10 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.172 Performance Engineering of Software Systems

Video thumbnail

Lec 15 | MIT 6.189 Multicore Programming Primer, IAP 2007

Lecture 15: Cilk (Courtesy of Bradley Kuszmaul and Charles Leiserson. Used with permission.) License: Creative Commons BY-NC-SA More information at http://ocw.mit.edu/terms More courses at http://ocw.mit.edu Subtitles are provided through the generous assistance of Rohan Pai.

From playlist MIT 6.189 Multicore Programming Primer, January (IAP) 2007

Video thumbnail

Split Complex Numbers and the Lorentz Boost

In this video, we are going to play around a bit with some equations of special relativity called the Lorentz Boost, which is the correct way to do a coordinate transformation at any speed. This particular transformation is important because it preserves the speed of light in all frames. W

From playlist Math

Video thumbnail

Lec 22 | MIT 6.046J / 18.410J Introduction to Algorithms (SMA 5503), Fall 2005

Lecture 22: Advanced Topics View the complete course at: http://ocw.mit.edu/6-046JF05 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.046J / 18.410J Introduction to Algorithms (SMA 5503),

Video thumbnail

Show Me Some Science! Speed Of Sound

Sound is a wave which travels through the air at about 330 m/s. The Little Shop of Physics Crew dances to the music together. When spread out along the track, it takes about a third of a second for the sound to travel from the first person to the last. The crew is blindfolded, so there are

From playlist Show Me Some Science!

Video thumbnail

Impulse-MOMENTUM Theorem!!

The Impulse MOMENTUM Theorem Explained In 36 Seconds!!! #Physics #Engineering #College #Math #NicholasGKK #Shorts

From playlist General Mechanics

Video thumbnail

NYC Tech Talk Series: How Google Backs Up the Internet

Google Tech Talk October 22, 2013 (more info below) Presented by Raymond Blum ABSTRACT Systems like GMail and Picasa keep massive amounts of data in the cloud, all of which has to be constantly backed up to prepare for the inevitable. Typical backup and recovery techniques don't scale, s

From playlist Google NYC Tech Talks

Video thumbnail

Special Relativistic Time Dilation

Here, Think Like a Physicist takes a diversion from its usual fare to give a discussion on the phenomenon of time dilation in special relativity. We give an overview of what the phenomenon is, and then discuss the relativity of simultaneity at length, as this is necessary for understandi

From playlist Summer of Math Exposition Youtube Videos

Video thumbnail

NIPS 2011 Big Learning - Algorithms, Systems, & Tools Workshop: Graphlab 2...

Big Learning Workshop: Algorithms, Systems, and Tools for Learning at Scale at NIPS 2011 Invited Talk: Graphlab 2: The Challenges of Large Scale Computation on Natural Graphs by Carlos Guestrin Carlos Guestrin is an Assistant Professor at Carnegie Mellon's Computer Science and Machine

From playlist NIPS 2011 Big Learning: Algorithms, System & Tools Workshop

Video thumbnail

The Search for Randomness | Jean Bourgain

March 25, 2009 Jean Bourgain, IBM von Neumann Professor, School of Mathematics, Institute for Advanced Study http://www.ias.edu/people/faculty-and-emeriti/bourgain Although the concept of randomness is ubiquitous, it turns out to be difficult to generate a truly random sequence of events

From playlist Mathematics

Video thumbnail

17. The Popular Front

France Since 1871 (HIST 276) A plethora of Far Right and fascist organizations emerged in the wake of World War I. Economic depression, nationalism, anti-Semitism and xenophobia all played a part in this upsurge. On the left, the tension between communist revolutionaries and socialist r

From playlist France Since 1871 with John Merriman

Video thumbnail

Moving Faster Than The Speed Of Light? Special Relativity Velocity Addition Formula

If train A is moving towards train B, and each train moves at 75% the speed of light (relative to the ground), will an observer on train A think that train B is moving at 150% the speed of light? But nothing moves faster than the speed of light, so what is going on? This video presents a f

From playlist Math Puzzles, Riddles And Brain Teasers

Video thumbnail

Determining Velocity, Speed, and Acceleration Using a Vector Valued Function

This video explains how to determine the velocity, speed, and acceleration given a vector valued function. http://mathispower4u.yolasite.com/

From playlist Vector Valued Function

Video thumbnail

Lenore Blum - Alan Turing and the other theory of computing and can a machine be conscious?

Abstract Most logicians and theoretical computer scientists are familiar with Alan Turing’s 1936 seminal paper setting the stage for the foundational (discrete) theory of computation. Most however remain unaware of Turing’s 1948 seminal paper which introduces the notion of condition, sett

From playlist Turing Lectures

Video thumbnail

26: Divergence Theorem - Valuable Vector Calculus

Video explaining the definition of divergence: https://youtu.be/UEU9dLgmBH4 Video on surface integrals: https://youtu.be/hVBoEEJlNuI The divergence theorem, also called Gauss's theorem, is a natural consequence of the definition of divergence. In this video, we'll see an intuitive explana

From playlist Valuable Vector Calculus

Related pages

Gödel's speed-up theorem | Computational complexity theory | Computable function | Almost all | Algorithm