# Questions tagged [complexity-assumptions]

The tag has no usage guidance.

6 questions
Filter by
Sorted by
Tagged with
274 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
303 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,603
102 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,603
1 vote
105 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.5k