Questions tagged [complexity-assumptions]
The complexity-assumptions tag has no usage guidance.
6
questions
5
votes
1
answer
288
views
Hardness assumption: an NP-complete problem whose ratio of hard instances do not tend to zero?
I am wondering about the following property $\text{(P)}$ of an $NP$-complete language $L$
$\begin{align}\exists M\text{ a polytime machine}\lim_{n\to\infty}P(\text{M solves a random instance of size $...
- 153
3
votes
1
answer
327
views
ETH based lower bound for $k$-COLORING of bounded degree graph
It is known that there is no $2^{o(n)}$-time algorithm for 3-COLORABILITY of graphs of maximum degree four, unless ETH fails [1]. Is a there a similar result for $k$-COLORABILITY assuming only ETH (...
- 1,633
2
votes
0
answers
103
views
Size of the constant $s_3$ in Exponential Time Hypothesis (ETH)
Exponential Time Hypothesis (ETH) says that there is a real number $s=s_3>0$ such that 3-SAT with $n$ variables and $m$ clauses cannot be solved in $2^{sn}(n+m)^{O(1)}$ time. The corollary "3-...
- 1,633
1
vote
0
answers
108
views
On proving the standard $p$-measure on $NP$ assumption?
In the answer here An Anthology of Complexity Assumptions an interesting assumption is made. The assumption is $p$-measure of $NP$ is not $0$. There are many non-trivial consequences that follow from ...
- 12.6k
35
votes
3
answers
997
views
An Anthology of Complexity Assumptions
In the paper The Random Oracle Hypothesis Is False, the authors (Chang, Chor, Goldreich, Hartmanis, Håstad, Ranjan, and Rohatgi) discuss the implications of the random-oracle hypothesis. They argue ...
3
votes
1
answer
989
views
Subexponential hardness assumption
Edited
I want to read more about subexponential hardness assumption, but I didn't find any good survey on this. I just took a look at Heavy-tailed distribution and Some properties of subexponential ...
- 654