Twelve speedy tricks for answering NP-complete problems

Speaker: Dr. Antonius Weinzierl, knowledge-based systems group at the Technical University of Vienna NP-complete problems often occur at the heart of important application domains like logistics, scheduling, or satisfiability checking. Today, no fast and correct algorithm is known for any NP-complete problem; in the worst-case, they all require exponential time. If satisfiability checking with 3 variables takes 1 second, exponential time then means that 13 variables require 1024 seconds, and 35 variables require 4 billion seconds or 126 years. Despite this, modern satisfiability checkers deal with 500.000 variables in less than 10 minutes. This talk reveals some key techniques that enable such performances. Antonius Weinzierl is a researcher at the Vienna University of Technology (TU Wien) where he received his PhD in 2014. His current research focus is on logic programming where satisfiability checking techniques are used intensely. In 2009 he started his work at TU Wien investigating inconsistency management for knowledge-exchange systems. In 2009 he received his diploma degree in computer science from LMU Munich. Recorded at the Big Techday 8 / http://www.bigtechday.com of TNG Technology Consulting / http://www.tngtech.com on June 12th, 2015 in Munich / Germany