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

Concept

Boolean satisfiability problem

Related lectures (31)

Quantum Approximate Optimization Algorithm

Covers the Quantum Approximate Optimization Algorithm (QAOA) for solving combinatorial optimization problems using quantum computers and its application to Boolean Satisfiability (SAT) problems.

Propositional Resolution and SAT Solvers

Covers the transformation of formulas into conjunctive normal form and the efficiency of algorithms for checking satisfiability.

Propositional Logic: Inference Rules

Covers the interpretation of propositional logic and inference rules for implication, conjunction, and double negation.

Quantum Adiabatic Optimization: Combinatorial Problems

Explores Quantum Approximate Optimization Algorithm for solving combinatorial problems efficiently.

Graphical Models: Representing Probabilistic Distributions

Covers graphical models for probabilistic distributions using graphs, nodes, and edges.

Polynomials, Division, and Ideals

Explores polynomials, their operations, and the concept of ideals in polynomial rings.

Predicate Logic: Quantifiers, CNF, DNF

Covers Predicate Logic, focusing on Quantifiers, CNF, and DNF.

The Local Hamiltonian Problem

Covers the Local Hamiltonian Problem, focusing on QMA-Complete problems and the complexity of verifying quantum computations.

Solving Parity Games in Practice

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

Propositional Resolution

Explores completeness in propositional logic, resolution on clauses, conjunctive form, unit resolution, SAT solvers, and proof generation.

Untitled

Quantifier Elimination Steps for Presburger Arithmetic

Explores quantifier elimination steps for Presburger Arithmetic, emphasizing techniques to simplify and eliminate quantifiers efficiently.

Case Analysis Rule and Propositional Resolution

Covers the case analysis rule, propositional resolution, soundness, completeness, and resolution on clauses, with practical exercises included.

Automating First-Order Logic Proofs Using Resolution

Covers first-order logic syntax, semantics, Skolemization, resolution, and normal form transformations.

Introduction to SMT Solving

Introduces Satisfiability Modulo Theories (SMT) solving, covering propositional logic, uninterpreted functions, and quantifier instantiation.

Propositions Calculation

Covers the calculation of propositions in predicate logic with a focus on logical connectives.

Finite Systems Expressed with Formulas

Explores encoding finite systems with boolean functions, propositional logic, inductive invariants, and formal proof systems.

Finite Systems Expressed with Formulas

Explores finite transition systems, propositional logic, truth interpretation, satisfiability, and boolean function representation with circuits.

Open Problems

Explores a variety of open problems in graph theory and computational complexity, challenging students to analyze and solve complex issues.

Predicate Logic: More on Quantifiers

Explores quantifiers with finite domains, uniqueness quantifier, composite statements, variable binding, and validity in logic.

Related lectures (31)

Quantum Approximate Optimization Algorithm

Covers the Quantum Approximate Optimization Algorithm (QAOA) for solving combinatorial optimization problems using quantum computers and its application to Boolean Satisfiability (SAT) problems.

Propositional Resolution and SAT Solvers

Covers the transformation of formulas into conjunctive normal form and the efficiency of algorithms for checking satisfiability.

Propositional Logic: Inference Rules

Covers the interpretation of propositional logic and inference rules for implication, conjunction, and double negation.

Quantum Adiabatic Optimization: Combinatorial Problems

Explores Quantum Approximate Optimization Algorithm for solving combinatorial problems efficiently.

Graphical Models: Representing Probabilistic Distributions

Covers graphical models for probabilistic distributions using graphs, nodes, and edges.

Polynomials, Division, and Ideals

Explores polynomials, their operations, and the concept of ideals in polynomial rings.

Predicate Logic: Quantifiers, CNF, DNF

Covers Predicate Logic, focusing on Quantifiers, CNF, and DNF.

The Local Hamiltonian Problem

Covers the Local Hamiltonian Problem, focusing on QMA-Complete problems and the complexity of verifying quantum computations.

Solving Parity Games in Practice

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

Propositional Resolution

Explores completeness in propositional logic, resolution on clauses, conjunctive form, unit resolution, SAT solvers, and proof generation.

Untitled

Quantifier Elimination Steps for Presburger Arithmetic

Explores quantifier elimination steps for Presburger Arithmetic, emphasizing techniques to simplify and eliminate quantifiers efficiently.

Case Analysis Rule and Propositional Resolution

Covers the case analysis rule, propositional resolution, soundness, completeness, and resolution on clauses, with practical exercises included.

Automating First-Order Logic Proofs Using Resolution

Covers first-order logic syntax, semantics, Skolemization, resolution, and normal form transformations.

Introduction to SMT Solving

Introduces Satisfiability Modulo Theories (SMT) solving, covering propositional logic, uninterpreted functions, and quantifier instantiation.

Propositions Calculation

Covers the calculation of propositions in predicate logic with a focus on logical connectives.

Finite Systems Expressed with Formulas

Explores encoding finite systems with boolean functions, propositional logic, inductive invariants, and formal proof systems.

Finite Systems Expressed with Formulas

Explores finite transition systems, propositional logic, truth interpretation, satisfiability, and boolean function representation with circuits.

Open Problems

Explores a variety of open problems in graph theory and computational complexity, challenging students to analyze and solve complex issues.

Predicate Logic: More on Quantifiers

Explores quantifiers with finite domains, uniqueness quantifier, composite statements, variable binding, and validity in logic.