Linkage
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+)
Harvard penalizes members of gender-exclusive organizations (G+)
Matching reviewers to submissions still needs some human attention (G+)
"No, I am not pregnant": yet another example of everyday sexism in academia, mostly invisible to men
Australian government issues report calling for copyright and patent liberalisation (G+)
Binary search, now another Wikipedia good article
Origami robots that can perform surgery on your digestive system after you eat them (G+)
New uses for blockchain: ensuring the integrity of medical experiments (G+)
An amusing 10-minute talk about NP-completeness and its application to Sesame Street
Comments:
2016-05-21T00:37:37Z
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
https://hal.archives-ouvertes.fr/hal-01316353/document
Any suggestion will be welcome,
Thanks in advance,
Frank.