Questions tagged [complexity-assumptions]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
5 votes
1 answer

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

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 (...
2 votes
0 answers

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 vote
0 answers

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

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

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 ...