Call a log-space reduction areduction that uses onlyO(logn) spacein addition to the input itself, and not countingthe produced result. In other words, there are three tapes: tape 1is read-only (the input), tape 2 is read-write (thework tape), and tape 3 is write-only (theoutput tape). Then we insist that tape 2use O(logn)space (tape 3 is unrestricted, but remember it is write-only). Sucha reduction is denoted ≤L. Show that3SAT ≤LCLIQUE.
