Questions tagged [complexity-assumptions]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3
votes
1answer
251 views

ETH based lower bound for $k$-COLORING

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
0answers
99 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-...
34
votes
3answers
945 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 ...
2
votes
1answer
761 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 ...