logo
ProjectEnded

Complexity Inside NP - A Computational Geometry Perspective

Ended · Germany

Source: EU Funding & Tenders Portal

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 pro

Status
Closed
Location
Germany
Updated
22 Jul 2026
Source
EU Funding & Tenders Portal

ConstructChat

Ask ConstructChat about Complexity Inside NP - A Computational Geometry Perspective

Pick a question to edit it, or write your own.

First answer free · no account

I am a

Project Information FAQ

Project Information

3 Q
The project “Complexity Inside NP - A Computational Geometry Perspective” is an infrastructure initiative, located in Germany. Taiyo aggregates data on it from EU Funding & Tenders Portal.

Participants

Not available for this record.

Status

Original status

ended

Taiyo status

Closed

Taiyo last update

2026-07-22

Contact

Not available for this record.

Description

Description

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.

Location

Country

Germany

Source

Source

EU Funding & Tenders Portal

URL

More Details

Record type

Project

Article published date

2026-01-15

More on this project

Research

Free account

View all details

You are reading the public part. A free account opens the rest:

  • Every detail on this project
  • News and media coverage
  • Technical research
View all details

Free account · no card · lands you back on this project