CCCG is in Vancouver this year; submission deadline is this Tuesday, May 17
Apple's cloud music storage can wipe your local copies and replace them with ersatz substitutes (G+)
"No, I am not pregnant": yet another example of everyday sexism in academia, mostly invisible to men
Binary search, now another Wikipedia good article
A major complexity class is NL. NL is the class of languages that are decidable on a nondeterministic logspace machine. A logspace machine is a Turing machine with a read-only input tape, a write-only output tape, and a read/write work tapes. The work tapes may contain at most \( O(\log n) \) symbols. In addition, Sanjeev Arora described in his book "Computational complexity: A modern approach" the certificate-based definition for NL.
The certificate-based definition of NL assumes that a deterministic logspace machine verifies the elements in a NL language using another separated read-only tape for the certificate. On each step of the machine the machine's head on that tape can either stay in place or move to the right. In particular, it cannot reread any bit to the left of where the head currently is. For that reason this kind of special tape is called ``read once".
CLIQUE is a well-known NP-complete problem. We show that a certificate u which represents a clique V' of size k on a graph G can be verified by a deterministic logspace machine M using an additional special read-once input tape, and thereby CLIQUE will be in NL as a direct consequence of this previous definition. If any single NP-complete problem can be solved in polynomial time, then every NP problem has a polynomial time algorithm. However, every problem in NL is in P too. Consequently, we can conclude that P = NP.
You can understand more this idea and debug my verifier algorithm in
Any suggestion will be welcome,
Thanks in advance,