Toggle light / dark theme

Is it possible to invent a computer that computes anything in a flash? Or could some problems stump even the most powerful of computers? How complex is too complex for computation? The question of how hard a problem is to solve lies at the heart of an important field of computer science called computational complexity. Computational complexity theorists want to know which problems are practically solvable using clever algorithms and which problems are truly difficult, maybe even virtually impossible, for computers to crack. This hardness is central to what’s called the P versus NP problem, one of the most difficult and important questions in all of math and science.

This video covers a wide range of topics including: the history of computer science, how transistor-based electronic computers solve problems using Boolean logical operations and algorithms, what is a Turing Machine, the different classes of problems, circuit complexity, and the emerging field of meta-complexity, where researchers study the self-referential nature of complexity questions.

Featuring computer scientist Scott Aaronson (full disclosure, he is also member of the Quanta Magazine Board). Check out his blog: https://scottaaronson.blog/

Read the companion article about meta-complexity at Quanta Magazine: https://www.quantamagazine.org/complexity-theorys-50-year-jo…-20230817/

00:00 Introduction to the P vs NP problem.
02:16 Intro to Computational Complexity.
02:30 How do computers solve problems?
03:02 Alan Turing and Turing Machines.
04:05 George Boole and Boolean Algebra.
05:21 Claude Shannon and the invention of transistors.
06:22 John Von Neumann and the invention of the Universal Electronic Computer.
07:05 Algorithms and their limits.
08:22 Discovery of different classes of computational problems.
08:56 Polynomial P problems explained.
09:56 Exponential NP Problems explained.
11:36 Implications if P = NP
12:48 Discovery of NP Complete problems.
13:45 Knapsack Problem and Traveling Salesman problem.
14:24 Boolean Satisfiability Problem (SAT) defined.
15:32 Circuit Complexity Theory.
16:55 Natural Proofs Barrier.
17:36 Meta-complexity.
18:12 Minimum Circuit Size Problem (MCSP)

- VISIT our Website: https://www.quantamagazine.org.

😀 Amazing breakthrough face_with_colon_three


A group of Spanish researchers have developed a brain-computer interface based on electroencephalograms that allowed a group of 22 users to play a simple multiplayer game. The interface was 94% accurate in translating players’ thoughts into game moves, with each move taking just over 5 seconds. The study was published in Frontiers in Human Neuroscience.

A brain-computer interface is a technology that enables direct communication between the human brain and external devices, such as computers or prosthetic limbs. Brain-computer interfaces work by detecting and interpreting neural signals, typically through electrodes placed on the user’s head. These signals are then translated into actionable commands, allowing individuals to control computers, devices, or applications using their thoughts.

Brain-computer interfaces offer significant potential in medicine, from helping paralyzed individuals regain environmental control to treating neurological disorders. However, their broader adoption is hindered by challenges in accuracy and the extended time required to interpret brain signals.

Introduction and objective: Video games are crucial to the entertainment industry, nonetheless they can be challenging to access for those with severe motor disabilities. Brain-computer interfaces (BCI) systems have the potential to help these individuals by allowing them to control video games using their brain signals. Furthermore, multiplayer BCI-based video games may provide valuable insights into how competitiveness or motivation affects the control of these interfaces. Despite the recent advancement in the development of code-modulated visual evoked potentials (c-VEPs) as control signals for high-performance BCIs, to the best of our knowledge, no studies have been conducted to develop a BCI-driven video game utilizing c-VEPs. However, c-VEPs could enhance user experience as an alternative method. Thus, the main goal of this work was to design, develop, and evaluate a version of the well-known ‘Connect 4’ video game using a c-VEP-based BCI, allowing 2 users to compete by aligning 4 same-colored coins vertically, horizontally or diagonally.

Methods: The proposed application consists of a multiplayer video game controlled by a real-time BCI system processing 2 electroencephalograms (EEGs) sequentially. To detect user intention, columns in which the coin can be placed was encoded with shifted versions of a pseudorandom binary code, following a traditional circular shifting c-VEP paradigm. To analyze the usability of our application, the experimental protocol comprised an evaluation session by 22 healthy users. Firstly, each user had to perform individual tasks. Afterward, users were matched and the application was used in competitive mode. This was done to assess the accuracy and speed of selection. On the other hand, qualitative data on satisfaction and usability were collected through questionnaires.

Results: The average accuracy achieved was 93.74% ± 1.71%, using 5.25 seconds per selection. The questionnaires showed that users felt a minimal workload. Likewise, high satisfaction values were obtained, highlighting that the application was intuitive and responds quickly and smoothly.

How do we go from 100 to 200 to 1000? PASQAL, a quantum computing startup, is using LASERS. They’ve demonstrated 100 and 200 qubit systems, now they’re talking about making 1000. Here’s the mockup of their system.

———————-
Need POTATO merch? There’s a chip for that!
http://merch.techtechpotato.com.

http://more-moore.com : Sign up to the More Than Moore Newsletter.
https://www.patreon.com/TechTechPotato : Patreon gets you access to the TTP Discord server!

Follow Ian on Twitter at http://twitter.com/IanCutress.
Follow TechTechPotato on Twitter at http://twitter.com/TechTechPotato.

If you’re in the market for something from Amazon, please use the following links. TTP may receive a commission if you purchase anything through these links.
Amazon USA : https://geni.us/AmazonUS-TTP
Amazon UK : https://geni.us/AmazonUK-TTP
Amazon CAN : https://geni.us/AmazonCAN-TTP
Amazon GER : https://geni.us/AmazonDE-TTP
Amazon Other : https://geni.us/TTPAmazonOther.

Ending music: https://www.youtube.com/watch?v=2N0tmgau5E4
———————-
Welcome to the TechTechPotato © Dr. Ian Cutress.
Ramblings about things related to Technology from an analyst for More Than Moore.

Building a plane while flying it isn’t typically a goal for most, but for a team of Harvard-led physicists that general idea might be a key to finally building large-scale quantum computers.

Described in a new paper in Nature, the research team, which includes collaborators from QuEra Computing, MIT, and the University of Innsbruck, developed a new approach for processing quantum information that allows them to dynamically change the layout of atoms in their system by moving and connecting them with each other in the midst of computation.

This ability to shuffle the qubits (the fundamental building blocks of quantum computers and the source of their massive processing power) during the computation process while preserving their quantum state dramatically expands processing capabilities and allows for self-correction of errors. Clearing this hurdle marks a major step toward building large-scale machines that leverage the bizarre characteristics of quantum mechanics and promise to bring about real-world breakthroughs in material science, communication technologies, finance, and many other fields.