2 votes

Hardness assumption: an NP-complete problem whose ratio of hard instances do not tend to zero?

Let us define the distance function of two languages $L, L'$ as $$ dist(n)= |L\Delta L'|_n$$ which means the number of $n$-bit strings in the symmetric difference $L\Delta L'$. If property ${\text P}$ ...
Andras Farago's user avatar
1 vote

ETH based lower bound for $k$-COLORING of bounded degree graph

The result mentioned in the question can be obtained by a chain of two standard reductions. The simplest reduction for $k$-COLORABILITY $\leq_p$ $(k+1)$-COLORABILITY (namely, adding a universal vertex)...

Only top scored, non community-wiki answers of a minimum length are eligible