Hola,
¿eres nuevo aquí?

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

CGinsideNP

Financiado

Complexity Inside NP A Computational Geometry Perspective

Traditional complexity theory focuses on the dichotomy between P and NP-hard problems. Lately, it has become increasingly clear that this misses a major part of the picture. Results by the PI and others offer glimpses on a fasci... ver más

31/05/2023

Freie Universitaet...

1M€

Presupuesto del proyecto: 1M€

Líder del proyecto

FREIE UNIVERSITAET BERLIN No se ha especificado una descripción o un objeto social para esta compañía.

TRL 4-5

Ver 2 Participantes

Financiación concedida El organismo H2020 notifico la concesión del proyecto el día 2023-05-31

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

ERC-2017-STG: ERC Starting Grant

I+D

Cerrada hace 8 años

0% 100%

2 Participantes

Freie Universitaet Berlin

1.49M€ | Lider

COMERCIAL ELECTRONICA Y SEGU...

141.66K€ | Participante

Ú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: 68 meses Fecha Inicio: 2017-09-20
Fecha Fin: 2023-05-31

Líder del proyecto

FREIE UNIVERSITAET BERLIN

TRL 4-5

Presupuesto del proyecto 1M€

Descripción del proyecto Traditional complexity theory focuses on the dichotomy between P and NP-hard problems. Lately, it has become increasingly clear that this misses a major part of the picture. Results by the PI and others offer glimpses on a fascinating structure hiding inside NP: new computational problems that seem to lie between polynomial and NP-hard have been identified; new conditional lower bounds for problems with large polynomial running times have been found; long-held beliefs on the difficulty of problems in P have been overturned. Computational geometry plays a major role in these developments, providing some of the main questions and concepts. We propose to explore this fascinating landscape inside NP from the perspective of computational geometry, guided by three complementary questions: (A) What can we say about the complexity of search problems derived from existence theorems in discrete geometry? These problems offer a new perspective on complexity classes previously studied in algorithmic game theory (PPAD, PLS, CLS). Preliminary work indicates that they have the potential to answer long-standing open questions on these classes. (B) Can we provide meaningful conditional lower bounds on geometric problems for which we have only algorithms with large polynomial running time? Prompted by a question raised by the PI and collaborators, such lower bounds were developed for the Frechet distance. Are similar results possible for problems not related to distance measures? If so, this could dramatically extend the traditional theory based on 3SUM-hardness to a much more diverse and nuanced picture. (C) Can we find subquadratic decision trees and faster algorithms for 3SUM-hard problems? After recent results by Pettie and Gronlund on 3SUM and by the PI and collaborators on the Frechet distance, we have the potential to gain new insights on this large class of well-studied problems and to improve long-standing complexity bounds for them.

Conecta tu I+D

Entra hoy

Financiación

Empresas

CTIs/Universidades

Proyectos

Investigadores