We investigate the hardness of approximating the longest path and
the longest cycle in directed graphs on $n$ vertices. We show that
neither of these two problems can be polynomial time approximated
within $n^{1-\epsilon}$ for any $\epsilon>0$ unless
$\text{P}=\text{NP}$. In particular, the result holds for
more >>>

Both average-case complexity and the study of the approximability properties of NP-optimization problems are well established and active fields of research. By applying the notion of average-case complexity to approximation problems we provide a formal framework that allows the classification of NP-optimization problems according to their average-case approximability. Thus, known ... more >>>

Abstract. It is known that random k-SAT formulas with at least
(2^k*ln2)*n random clauses are unsatisfiable with high probability. This
result is simply obtained by bounding the expected number of satisfy-
ing assignments of a random k-SAT instance by an expression tending
to 0 when n, the number of variables ... more >>>