1
$\begingroup$

obviously the "Finding an $n/2$ size clique in a directed/ non directed graph" is not $\sf NL$ but I'd really like to understand where does it fall in terms of the definition of the $\sf NL$ definition.

I have to have an input and witness tapes, both of them can be polynomial and a logarithmic size of work stripe. So why can't I just guess an $n/2$ clique, each time put 2 vertices on the work tape, check that they share an edge, and count them. The witness tape provides me each time two vertices from left to write, in total $O({\frac{n}{2}}^2)$. In order to count that I need $O(\log ({\frac{n}{2}}^2))$ which is logarithmic. so what's lacking or wrong with this attempt?

Improve this question
$\endgroup$
3
  • $\begingroup$ I'm getting a witness which suppose to be a clique, set of vertices. I go from the first one to all the rest, then from the second one to all the rest. Perhaps I can't go back to second? $\endgroup$
    – Joni
    Jan 27, 2013 at 8:10
  • $\begingroup$ I use the definition such that the witness does not have to be logarithmic space, The machine has 3 tapes: input, witness(Can be polynomial), only the space of the work tape counts. but important detail is that we can move only right way on the witness tape. $\endgroup$
    – Joni
    Jan 27, 2013 at 9:17
  • $\begingroup$ It doesn't need to be deterministically. I wabt to check them in linear space. $\endgroup$
    – Joni
    Jan 27, 2013 at 10:40

2 Answers 2

Reset to default
2
$\begingroup$

(Turning my comments into an answer.)

You have to deterministically verify that the $\mathcal{O}(n)$ vertices on your witness tape form a clique. Since you can only move to the right, you can only do linear amount of work for this set, however there are $\mathcal{O}(n^2)$ pairs of vertices in the clique, and you have to check every pair. Hence you cannot check every pair and thus not verify if it is a clique or not.

Note that this is not a proof that $\mathbf{Clique}$ is not in $\mathsf{NL}$, only that this algorithm (or idea) doesn't work.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Ok Thank you. so why Can't I put the witness $k$ times in a row, and check it that why? where doesn't it meet the conditions? $\endgroup$
    – Joni
    Jan 27, 2013 at 18:20
  • $\begingroup$ There is no $k$ in your original question, so do you mean any constant $c \in \mathbb{N}$, or $k=n$ or $k=n/2$? In any case, the unsatisfactory answer to your question now would be because that's not the definition of $\mathsf{NL}$. But to be able to fully appreciate why, you need to go into the details of the proof of why your definition (with witness) is equivalent to the original definition of $\mathsf{NL}$ (which is without witness). $\endgroup$
    – Pål GD
    Jan 27, 2013 at 19:03
  • 1
    $\begingroup$ The original definition of $\mathsf{NL}$ involves only a non-deterministic Turing machine with a log space working tape and a read-only input tape. It does not involve your definition of a right-move-only witness tape, however you can show those definitions to be equivalent. $\endgroup$
    – Pål GD
    Jan 27, 2013 at 19:08
0
$\begingroup$

Short answer: the wrong thing in your solution is that the definition you are using does not give an $\mathsf{NL}$ algorithm, it gives an $\mathsf{NP}$ algorithm.

Here is another way to explain the problem: in $\mathsf{NL}$ you can't really assume that you get a witness to verify which is of polynomial size (as we do in $\mathsf{NP}$). In fact if we take the polynomial size witness plus a log-space verifier we end up with $\mathsf{NP}$ not $\mathsf{NL}$ (and this is true even if we use weaker verifiers, as long as the witness is polynomial size and the class that verifier belongs to is capable of checking if a given string is an accepting computation of a given TM we end up with $\mathsf{NP}$).

So don't let the witness definition confuse you about $\mathsf{NL}$. An $\mathsf{NL}$ machine is a nondeterministic machine which makes nondeterministic decisions and uses only logarithmic space and we don't have a result that allows us to use a witness definition similar to the $\mathsf{NP}$ witness-verifier definition by just changing the verifier to be a log-space machine in place of a poly-time machine.

One can use a real-only read-once tape for a witness definition but that is not usually a good way of thinking about $\mathsf{NL}$. The witness verifier definition for $\mathsf{NP}$ is used because we end up with a very nice intuitive definition for $\mathsf{NP}$: verifying answers in polynomial time. We don't end up with a similarly nice definition for $\mathsf{NL}$.

ps: for completeness, it is consistent with the current state of knowledge that there is an $\mathsf{NL}$ algorithm for the problem. However, such an algorithm would imply $\mathsf{NL}=\mathsf{P}=\mathsf{NP}$ since the problem is complete for $\mathsf{NP}$. Therefore although it is not completely ruled out, it is considered a very unlikely possibility (and you would win a 1 million dollar prize if you had such an algorithm).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.