general questions

[Omer Eyal]

1. what is the key property that separates L for NL? what can't a
machine in L do, that an NL machine can
yes STCONN is NL complete. but we have not proved that L != NL. so if
i have a choice to decide if a problem is in L or NL, on what basis do
i tell them apart? where's the logic in this division?

2. we defined BPP using the 2/3 and 1/3 probabilities. but what
happens if i get a machine which accepts let's say on 1/2 probability
when x is in the language, and 1/3 when x is not in the language? is
that also in BPP by amplification or is it "just" a probabilistic
machine, but not in BPP

3. i didn't understand the reduction GAP-E3SAT[a,b] to GAP-3CSGv[a,b].
i understand it is done via the E3SAT to CLIQUE reduction. but how
come 3 colors? i would expect 8 colors, for each combination of the
clauses' literals. and furthermore, CSGv demands that the graph will
be full, but the E3SAT to CLIQUE reduction removes edges within
clauses and between inconsistent literals. so how does it work?

4. is there a reduction GAP-VC[a,b] to GAP-IS[1-b,1-a], and if not,
then why not? i understand that IS cannot be approximated with any
constant because of the GAP-K^dCSGV amplification, but that's a
different gap, and so, a different problem


i would prefer a formal teacher to reply on these questions, as i am
never sure who to believe when a student answers them. it just makes
more of a mess when wrong or incomplete answers are given by confused
students (like myself)

[Omer Eyal]

furthermore, one more thing i don't understand
why is STCONN NL complete? the number of states a machine can have is
potentially infinite, as each state might send it to another state
with the same things written, but it will not be the same state. let
me try to explain, like, there can be a series of states s1,...,sk,
where the conditions are the same in the machine, but because they
resulted from a different series of computations they form a different
method of computation.
ok. example. suppose we have the states a1,...,an which are all
different, and s1,...,sk which are the same
then the machine might do something like this:
a1,a2,s1,a3,a4,a5,s2,a4,a6...
what i am saying is that a state in itself might form as a kind of
"memory", that it remembers the series that came before it, and act
accordingly. it's kind of an implicit memory. well, maybe i got
something wrong

[odedr]

> 1. what is the key property that separates L for NL? what can't a
> machine in L do, that an NL machine can
> yes STCONN is NL complete. but we have not proved that L != NL. so if
> i have a choice to decide if a problem is in L or NL, on what basis do
> i tell them apart? where's the logic in this division?

It is not known whether L = NL or not. Some people think it's equal,
some don't.

In any case, if I give you a problem and ask you if it's in L or NL
then there are 2 options:
either you show the problem is in L,
or you show that the problem is NL-complete (in which case you can be
sure it is not known to be in L)

We will not ask you for problems that are not known to be in L nor to
be NL-complete (this won't be fair).

> 2. we defined BPP using the 2/3 and 1/3 probabilities.  but what
> happens if i get a machine which accepts let's say on 1/2 probability
> when x is in the language, and 1/3 when x is not in the language? is
> that also in BPP by amplification or is it "just" a probabilistic
> machine, but not in BPP

If you have a machine that accepts with probabilities, say, >=1/2 and
<=1/3,
then you can amplify it (by calling it several say 100 times and
answering
yes if more than 5/12 of the answers are YES). The resulting machine
is
in the standard BPP class.

So the short answer: for any two constants 0<a<b<1, the class BPP[a,b]
=BPP[1/3,2/3].

> 3. i didn't understand the reduction GAP-E3SAT[a,b] to GAP-3CSGv[a,b].
> i understand it is done via the E3SAT to CLIQUE reduction. but how
> come 3 colors? i would expect 8 colors, for each combination of the
> clauses' literals. and furthermore, CSGv demands that the graph will
> be full, but the E3SAT to CLIQUE reduction removes edges within
> clauses and between inconsistent literals. so how does it work?

I'm not too familiar with this part of the course, so the following
might be wrong:
You can do this reduction with 3 colors (what I would call
assignments) by
assigning for each clause which of its three variables made it
satisfiable.
I think that I showed exactly such a reduction in class (remember, we
had a triple assigned to each clause).

I am not sure what you're saying about "full graph". Maybe you mean
"complete graph".
But still, I don't know what you are referring to. I don't remember
anywhere that the
graph needs to be complete.

> 4. is there a reduction GAP-VC[a,b] to GAP-IS[1-b,1-a], and if not,
> then why not? i understand that IS cannot be approximated with any
> constant because of the GAP-K^dCSGV amplification, but that's a
> different gap, and so, a different problem

Of course there is such a reduction: it's the identity reduction!
A graph has a vertex cover of size <=\alpha*n if and only if it
has an independent set of size >=(1-\alpha)*n.

-- Oded