NP-complete problems cannot have efficient algorithms unless P = NP. Due to their importance in practice, however, it is useful to improve the known exponential-time algorithms for NP-complete problems. We survey some of the recent results on such improved exponential-time algorithms for the NP-complete problems satisfiability, graph colorability, and the ... more >>>
This paper surveys some of the work that was inspired by Wagner's general technique to prove completeness in the levels of the boolean hierarchy over NP and some related results. In particular, we show that it is DP-complete to decide whether or not a given graph can be colored with ... more >>>
We survey some results in quantum cryptography. After a brief
introduction to classical cryptography, we provide the physical and
mathematical background needed and present some fundamental protocols
from quantum cryptography, including quantum key distribution and
quantum bit commitment protocols.
We prove that the exact versions of the domatic number problem are complete
for the levels of the boolean hierarchy over NP. The domatic number
problem, which arises in the area of computer networks, is the problem of
partitioning a given graph into a maximum number ...
more >>>
