Hola,
¿eres nuevo aquí?

Registrate y conecta tu empresa con financiación pública, partners y proyectos.

CRACKNP

Financiado

Finding Cracks in the Wall of NP completeness

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.... ver más

31/01/2025

1M€

Presupuesto del proyecto: 1M€

Líder del proyecto

UNIVERSITEIT UTRECHT No se ha especificado una descripción o un objeto social para esta compañía.

TRL 4-5

Ver 3 Participantes

Financiación concedida El organismo H2020 notifico la concesión del proyecto el día 2019-09-30

Línea de financiación objetivo El proyecto se financió a través de la siguiente ayuda:

ERC-2019-STG: ERC Starting Grant

I+D

Cerrada hace 6 años

0% 100%

3 Participantes

1.50M€ | Lider

TALLERES MOVIGI

TU/e

N.D. | Participante

Proyectos interesantes

PACKENUM PArameterized Complexity and Kernelization for ENUMeration 141K€ Cerrado

ALGOCom Novel Algorithmic Techniques through the Lens of Combinatori... 1M€ Cerrado

CoCoSym Symmetry in Computational Complexity 1M€ Cerrado

PARAPATH Parameterized Complexity Through the Lens of Path Problems 1M€ Cerrado

RTI2018-095609-B-I00 SATISFACTIBILIDAD PARA PROGRAMACION DE TAREAS, PLANIFICACION... 22K€ Cerrado

Algacom Algorithms and Game Comonads 166K€ Cerrado

Últimas noticias

27-11-2024: Videojuegos y creaci... Se abre la línea de ayuda pública: Ayudas para la promoción del sector del videojuego, del pódcast y otras formas de creación digital

27-11-2024: DGIPYME En las últimas 48 horas el Organismo DGIPYME ha otorgado 1 concesiones

27-11-2024: FUNDACION-EOI En las últimas 48 horas el Organismo FUNDACION EOI ha otorgado 2 concesiones

Duración del proyecto: 64 meses Fecha Inicio: 2019-09-30
Fecha Fin: 2025-01-31

Líder del proyecto

UNIVERSITEIT UTRECHT

TRL 4-5

Presupuesto del proyecto 1M€

Descripción del proyecto 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.

Conecta tu I+D

Entra hoy

Financiación

Empresas

CTIs/Universidades

Proyectos

Investigadores