CRACKNP | Finding Cracks in the Wall of NP-completeness

Summary
Assuming P does not equal NP, there are no polynomial time algorithms for any NP-complete problem. This however still leaves a huge gap between anything super-polynomial and the exponential run times of trivial exhaustive search. The study of exact (exponential time) algorithms that aims to breach this gap is as old as Theoretical Computer Science (TCS) itself: Already in the 1960's, researchers found elementary (for modern standards) algorithms that greatly improve exponential the run times. But over time, TCS seems to have hit a brick wall: Somewhat embarrassingly, as of 2018 the run times of these classic algorithms are still the best known for many classic problems.

This project aims to strike at the heart of this issue by designing the next generation of exact exponential time algorithms. To obtain these algorithms, we consider the most famous NP-complete problems such as Traveling Salesman, CNF-Sat and Knapsack, and we challenge ourselves to improve the classic currently best algorithms for them. These problems have served as a prototypical test bed for many algorithmic techniques with extensive applications, and thus their study provides an excellent road map towards our aim.
Moreover, in the last few years it was shown that these algorithms have consequences that reach much further than originally thought: In particular, they would have a major impact on research in polynomial time algorithms, circuit complexity and parameterized complexity.

Now is the right moment for this project, as recent work (partially by the PI) has given a first glimpse of a new algorithmic toolkit emerging: Advanced new tools to decompose solutions such as the representation method, the rank-based method and the polynomial method, are still barely exploited and studied in the field.
In this project we will combine these (and many more) tools in novel ways that transcend existing approaches, and make cracks in the wall of NP-completeness seem entirely within reach.
Unfold all
/
Fold all
More information & hyperlinks
Web resources: https://cordis.europa.eu/project/id/853234
Start date: 01-02-2020
End date: 31-01-2025
Total budget - Public funding: 1 499 632,00 Euro - 1 499 632,00 Euro
Cordis data

Original description

Assuming P does not equal NP, there are no polynomial time algorithms for any NP-complete problem. This however still leaves a huge gap between anything super-polynomial and the exponential run times of trivial exhaustive search. The study of exact (exponential time) algorithms that aims to breach this gap is as old as Theoretical Computer Science (TCS) itself: Already in the 1960's, researchers found elementary (for modern standards) algorithms that greatly improve exponential the run times. But over time, TCS seems to have hit a brick wall: Somewhat embarrassingly, as of 2018 the run times of these classic algorithms are still the best known for many classic problems.

This project aims to strike at the heart of this issue by designing the next generation of exact exponential time algorithms. To obtain these algorithms, we consider the most famous NP-complete problems such as Traveling Salesman, CNF-Sat and Knapsack, and we challenge ourselves to improve the classic currently best algorithms for them. These problems have served as a prototypical test bed for many algorithmic techniques with extensive applications, and thus their study provides an excellent road map towards our aim.
Moreover, in the last few years it was shown that these algorithms have consequences that reach much further than originally thought: In particular, they would have a major impact on research in polynomial time algorithms, circuit complexity and parameterized complexity.

Now is the right moment for this project, as recent work (partially by the PI) has given a first glimpse of a new algorithmic toolkit emerging: Advanced new tools to decompose solutions such as the representation method, the rank-based method and the polynomial method, are still barely exploited and studied in the field.
In this project we will combine these (and many more) tools in novel ways that transcend existing approaches, and make cracks in the wall of NP-completeness seem entirely within reach.

Status

SIGNED

Call topic

ERC-2019-STG

Update Date

27-04-2024
Images
No images available.
Geographical location(s)
Structured mapping
Unfold all
/
Fold all
Horizon 2020
H2020-EU.1. EXCELLENT SCIENCE
H2020-EU.1.1. EXCELLENT SCIENCE - European Research Council (ERC)
ERC-2019
ERC-2019-STG