Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Improved Algorithm: Three-Color Parity Games

Description

This lecture presents an improved algorithm for solving three-color parity games, introducing the concept of progress measures and their acceleration. It covers the main properties of parity games, the complexity of computing winning states, and the progress measure algorithm with update rules. The gap theorem and time divergence in reachability games are discussed, along with the symbolic implementation of accelerated progress measures. Experimental results and conclusions on the practical speed-up provided by acceleration are highlighted, with future work focusing on extending the algorithm to general parity games.

Official source

Ontological neighbourhood

Theoretical computer science

Theory of computation: Computational complexity theory

Related concepts (32)

Computational complexity

In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) and memory storage requirements. The complexity of a problem is the complexity of the best algorithms that allow solving the problem. The study of the complexity of explicitly given algorithms is called analysis of algorithms, while the study of the complexity of problems is called computational complexity theory.

Progress

Progress is the movement towards a refined, improved, or otherwise desired state. In the context of progressivism, it refers to the proposition that advancements in technology, science, and social organization have resulted, and by extension will continue to result, in an improved human condition; the latter may happen as a result of direct human action, as in social enterprise or through activism, or as a natural part of sociocultural evolution.

Computational complexity theory

In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm. A problem is regarded as inherently difficult if its solution requires significant resources, whatever the algorithm used.

Complexity class

In computational complexity theory, a complexity class is a set of computational problems "of related resource-based complexity". The two most commonly analyzed resources are time and memory. In general, a complexity class is defined in terms of a type of computational problem, a model of computation, and a bounded resource like time or memory. In particular, most complexity classes consist of decision problems that are solvable with a Turing machine, and are differentiated by their time or space (memory) requirements.

Algorithm

In mathematics and computer science, an algorithm (ˈælɡərɪðəm) is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing calculations and data processing. More advanced algorithms can use conditionals to divert the code execution through various routes (referred to as automated decision-making) and deduce valid inferences (referred to as automated reasoning), achieving automation eventually.

Related lectures (48)

Solving Parity Games in Practice

Explores practical aspects of solving parity games, including winning strategies, algorithms, complexity, determinism, and heuristic approaches.

Complexity & Induction: Algorithms & Proofs

Covers worst-case complexity, algorithms, and proofs including mathematical induction and recursion.

Untitled

Coin Rendering: Part 1 MOOC: Information, Computation, Communication: Introduction to computational thinking

Covers coin rendering and the limitations of the greedy algorithm in finding optimal solutions.

Distinct Elements: Count and Hash Functions