We study several properties of sets that are complete for NP.
We prove that if $L$ is an NP-complete set and $S \not\supseteq L$ is a p-selective sparse set, then $L - S$ is many-one-hard for NP. We demonstrate existence of a sparse set $S \in \mathrm{DTIME}(2^{2^{n}})$
such ... more >>>

We study the diagonalization in the context of proof
complexity. We prove that at least one of the
following three conjectures is true:

1. There is a boolean function computable in E
that has circuit complexity $2^{\Omega(n)}$.

2. NP is not closed under the complement.

3. There is no ... more >>>

Recently Schuler \cite{Sch03} presented a randomized algorithm that
solves SAT in expected time at most $2^{n(1-1/\log_2(2m))}$ up to a
polynomial factor, where $n$ and $m$ are, respectively, the number of
variables and the number of clauses in the input formula. This bound
is the best known ... more >>>