Linked Questions
28 questions linked to/from Problems Between P and NPC
224
votes
60answers
91k views
Major unsolved problems in theoretical computer science?
Wikipedia only lists two problems under "unsolved problems in computer science":
P = NP?
The existence of one-way functions
What are other major problems that should be added to this list?
Rules:
...
33
votes
8answers
3k views
Problems with big open complexity gaps
This question is about problems for which there is a big open complexity gap between known lower bound and upper bound, but not because of open problems on complexity classes themselves.
To be more ...
31
votes
7answers
9k views
Should we consider $\mathsf{P} \neq \mathsf{NP}$ a law of nature?
Many experts believe that the $\mathsf{P} \neq \mathsf{NP}$ conjecture is true and use it in their results. My concern is that the complexity strongly depends on the $\mathsf{P} \neq \mathsf{NP}$ ...
27
votes
5answers
5k views
Is it a rule that discrete problems are NP-hard and continuous problems are not?
In my computer science education, I increasingly notice that most discrete problems are NP-complete (at least), whereas optimizing continuous problems is almost always easily achievable, usually ...
31
votes
6answers
2k views
Why are so few natural candidates for NP-intermediate status?
It is well known by Ladner's Theorem that if ${\mathsf P}\neq \mathsf {NP}$, then there exist infinitely many $\mathsf {NP}$-intermediate ($\mathsf{NPI}$) problems. There are also natural candidates ...
38
votes
2answers
4k views
Sum-of-square-roots-hard problems?
The sum of square roots problem asks, given two sequences $a_1, a_2, \dots, a_n$ and $b_1, b_2, \dots, b_n$ of positive integers, whether the sum $\sum_i \sqrt{a_i}$ less than, equal to, or greater ...
30
votes
2answers
2k views
Hierarchies in NP (under the assumption that P != NP)
Assuming that P != NP, I believe it has been shown that there are problems which are not in P and not NP-Complete. Graph Isomorphism is conjectured to be such a problem.
Is there any evidence of more ...
28
votes
3answers
1k views
Natural problems in $NP \cap coNP$ not in $UP \cap coUP$?
Are there any natural problems in $NP \cap coNP$ that are not (known to be/thought to be) in $UP \cap coUP$?
Obviously the big one everyone knows about in $NP \cap coNP$ is the decision version of ...
11
votes
3answers
829 views
Why are NPI problems not all of the same complexity?
How does one look at a problem and reason that it is likely NP-Intermediate as opposed to NP-Complete? It is often pretty simple to look at a problem and tell whether it is likely NP-Complete or not ...
42
votes
3answers
3k views
Consequences of a quasi-polynomial time algorithm for the graph isomorphism problem
The Graph Isomorphism problem (GI) is arguably
the best known candidate for an NP-intermediate problem.
The best known algorithm is sub-exponential algorithm
with run-time $2^{O(\sqrt{n \log n})}$. ...
13
votes
4answers
783 views
Reference for fundamental theorem on tree rotations
Two binary search trees are said to be linearly equivalent when they agree in their in-order traversals. The following theorem explains why tree rotations are so fundamental:
Let A and B be binary ...
14
votes
3answers
841 views
Is the 3-sphere recognition problem NP-complete?
It is known that determining whether or not a given triangulated 3-manifold is a 3-sphere
is in NP, via work by
Saul Schleimer in 2004: "Sphere recognition lies in NP"
arXiv:math/0407047v1 [math.GT].
...
7
votes
1answer
722 views
Algorithm for finding a 3-cycle cover
Given: An undirected, unweighted graph
Looking for: A disjoint vertex cycle cover where every cycle has at least 3 edges
Is there any algorithm that solves this problem, possibly with some ...
7
votes
2answers
834 views
“Any” Subset Sum. Is it hard?
Here is a variant of the classic partition problem: Given a list of integers can it be partitioned into $S_1$, $S_2$, and $S_3$, with $S_1$ and $S_2$ nonempty, so the sum of elements in $S_1$ equals ...
16
votes
1answer
408 views
Natural candidates for the hierarchy inside NPI
Let's assume that $\mathsf{P} \neq \mathsf{NP}$. $\mathsf{NPI}$ is the class of problems in $\mathsf{NP}$ which are neither in $\mathsf{P}$ nor in $\mathsf{NP}$-hard. You can find a list of problems ...