Linked Questions
29 questions linked to/from Problems Between P and NPC
230
votes
60
answers
96k
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:
...
37
votes
8
answers
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 ...
- 8,473
32
votes
7
answers
10k
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}$ ...
- 4,828
28
votes
5
answers
6k
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 ...
- 391
33
votes
6
answers
3k
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 ...
- 11.2k
40
votes
2
answers
6k
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 ...
- 22.9k
30
votes
2
answers
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 ...
- 1,855
28
votes
3
answers
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 ...
- 36.4k
12
votes
3
answers
965
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 ...
- 457
43
votes
3
answers
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})}$. ...
- 20.8k
13
votes
4
answers
849
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 ...
- 2,161
14
votes
3
answers
948
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].
...
- 3,703
7
votes
1
answer
1k
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 ...
- 79
7
votes
2
answers
887
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 ...
- 513
16
votes
1
answer
540
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 ...
- 20.8k