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
Project Information FAQ
Project Information
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 |
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
Free account · no card · lands you back on this project
More infrastructure projects in Germany
- Veja Mate Offshore Wind Farm Project
- Albatros Offshore Wind Farm North Sea Germany
- Hohe See Offshore Wind Farm North Sea Germany
- EnBW Baltic 2 Offshore Wind Farm
- Herdecke 400MW CCGT GasFired Power Plant Grenada
- Global Tech I Offshore Wind Farm
- Nordsee One Offshore Wind Project North Sea
- Westfalen Power Plant Units D and E Hamm
