2
votes
How to intuitively express the hardness of Minicrypt and Cryptomania?
The existence of (trapdoor) OWF implies that there are NP relations that are hard on average. But the difference of both worlds is no longer about the hardness of NP. It is much more about the ...
- 990
2
votes
Accepted
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}$ ...
- 11.4k
1
vote
Accepted
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