some questions..

[Ran Ziv]

1) what is the best known approx factor for MAX 3SAT?!??! could
someone please at least answer that one, i'm totally confused about
that right now and it seems like something i should probably know by
now..


2) NL^NL = NL: True \ False \ Equivalent to an open problem?
I don't really have any clue about this one, to be honest.. I'm
leaning a bit towards it being *true* because of Immerman, then the
original machine can simulate the oracle, like NP = Sigma2 if NP=CoNP,
yet i'm really not sure, since besides the fact that the oracle can
"really solve" problems (unlike the 'normal' NL machine, which, if it
werent for Immerman's law, could only 'half-solve' problems in NL [i
mean that it would be able to accept inputs in the language but would
'quit' on inputs which are not]), the non-determinism might also give
extra power to the oracle, like Sigma2 might be greater than
'just' (NP U CoNP). Also, I remember thinking about problems in NL,
where I wanted to use a subprocedure of NL which i would need to write
poly input for, but i couldnt do it, because of the tape limitation -
with NL^NL, I could..


3) P = Space(n): True \ False \ Equivalent to an open problem?
Ok this feels kind of silly to ask, but i'm not entirely sure how to
prove this easy-looking question actually.. I think the answer is
*false*. There are problems you can solve in P which cannot be solve
in Space(n), like problems where you need to use more than a linear
part of the tape, and there are problems you can solve in Space(n) but
not in P, like problems which require 2^n time. It could be that
P=PSPACE, so Space(n) might be in P actually, but definitely not the
other way around. question is, how do i show an actual problem which
is in P but not in space(n)?


4) GAP-Coloring[3,4] - (min colors to color a graph, 3 being the yes
instance i guess..): I saw in some tests this is in NPC, and that its
the same as 3Col. I'm having some difficulties digesting that - I
would think the problem is in (NP U CoNP). We need to know whether
it's possible or *not possible* to 3-col the graph. we also need to be
able to solve (3Col)' (the conp problem), wouldn't we?


Thanks

[Adi Glucksam]

1) what is the best known approx factor for MAX 3SAT?!??! could
someone please at least answer that one, i'm totally confused about
that right now and it seems like something i should probably know by
now..

well, we know that every sentence p there exists an assigning such that provides at least 7/8 of the clauses. you can prove this using expectancy. other then that we didn't really learn any approximation solution. 

2) NL^NL = NL: True \ False \ Equivalent to an open problem?
I don't really have any clue about this one, to be honest.. I'm
leaning a bit towards it being *true* because of Immerman, then the
original machine can simulate the oracle, like NP = Sigma2 if NP=CoNP,
yet i'm really not sure, since besides the fact that the oracle can
"really solve" problems (unlike the 'normal' NL machine, which, if it
werent for Immerman's law, could only 'half-solve' problems in NL [i
mean that it would be able to accept inputs in the language but would
'quit' on inputs which are not]), the non-determinism might also give
extra power to the oracle, like Sigma2 might be greater than
'just' (NP U CoNP). Also, I remember thinking about problems in NL,
where I wanted to use a subprocedure of NL which i would need to write
poly input for, but i couldnt do it, because of the tape limitation -
with NL^NL, I could..

this is true if NL=NP, which means the polynomial hierarchy collapse.

the reason is that when you use an NL oracle, you have a polynomial witness, that you can only see once. but since we are in NL you could call the oracle at least O(n) times, hence you will be able to see the witness O(n) times. this way you could solve clique for instance & we know this problem is not in NL :)

it is true when we are talking about P^NP if NP=co-NP, because there you can look at your witness as many times as you want :)

3) P = Space(n): True \ False \ Equivalent to an open problem?
Ok this feels kind of silly to ask, but i'm not entirely sure how to
prove this easy-looking question actually.. I think the answer is
*false*. There are problems you can solve in P which cannot be solve
in Space(n), like problems where you need to use more than a linear
part of the tape, and there are problems you can solve in Space(n) but
not in P, like problems which require 2^n time. It could be that
P=PSPACE, so Space(n) might be in P actually, but definitely not the
other way around. question is, how do i show an actual problem which
is in P but not in space(n)?

It is really difficult to show that there is a problem in P that has no algorithm whatsoever in O(n) space.

the reason is everything you write, you could calculate again instead of writing it. it will take longer, but still polynomial time.

you could show a log-space reduction from each L in P & use the face that HAM_PATH only takes O(logn) Nspace-->O(log^2n) space with is less then O(n) for n big enough.

use the configuration graph but don't create it, every time we want to see the k'th note, we shall calculate it.

as we said about the reduction to TQBF this reduction is a log-space reduction (for the same reason),

so I think it's an open question. let me know if you think otherwise & why.

  

4) GAP-Coloring[3,4] - (min colors to color a graph, 3 being the yes
instance i guess..): I saw in some tests this is in NPC, and that its
the same as 3Col. I'm having some difficulties digesting that - I
would think the problem is in (NP U CoNP). We need to know whether
it's possible or *not possible* to 3-col the graph. we also need to be
able to solve (3Col)' (the conp problem), wouldn't we?

Think about it this way- if you could solve 3COL you could solve this, since you can send this to 3col if you get a positive answer then it is in Y otherwise it's in NO. The other way round- if you have a solution for this, you could send each graph to this algorithm. if you got a positive answer, it means you can color this graph with <=3 colors, hence return true. otherwise, if you got No, it means you need at least 4 colors, hence return false.

Thanks

you're welcome. let me know if you think something is not right :)

[Ido Ben Eliezer]

In fact, P!=Space(n). It is easy to show that if Space(n) is contained in P, then Space(n^2) is also contained in P (by padding). But then we get Space(n)=P=Space(n^2) and this is impossible by space hierarchy.

 

Ido

[Adi Glucksam]

so is this false since we proved that space(n^2) != space (n^3)

Adi Glucksam

[Ran Ziv]

Ido - thanks for your answer, I'd appreciate it if you could also
answer the rest of the questions in the original post

-

Adi - about your first answer, I didn't understand which of the
machines will supposingly be able to see the witness O(n) times - the
'base' machine or the oracle machine? the oracle machine should be a
'fixed' machine, meaning you can call it O(n) times, but it will
execute the same operation each time, and each time its witness will
be read-once.. so im not entirely sure that actually solves it..
Unless I misunderstood your answer :)

about the other answer, well, we got our answer from Ido, but I just
wanted to comment that I don't think HAM_PATH only takes up O(logn)
NSPACE - in that case, we would know NP C Space(Log^2(n)), which im
pretty sure is false..

On Jul 25, 11:20 am, Adi Glucksam <adigluck...@gmail.com> wrote:
> so is this false since we proved that space(n^2) != space (n^3)
>
> Adi Glucksam
>

> On Sun, Jul 25, 2010 at 12:17 PM, Ido Ben Eliezer <idob...@gmail.com> wrote:
>
>
>
> > In fact, P!=Space(n). It is easy to show that if Space(n) is contained in
> > P, then Space(n^2) is also contained in P (by padding). But then we get
> > Space(n)=P=Space(n^2) and this is impossible by space hierarchy.
>
> > Ido
>

> >> you're welcome. let me know if you think something is not right :)- Hide quoted text -
>
> - Show quoted text -

[Ido Ben Eliezer]

1. Indeed, 8/7 is the best approximation for Max-E3SAT (and this is tight by the PCP theorem).

 

2. Basically, it's a bit difficult to define oracles with log-space machine, because it is not well-defined how much space you may use on the oracle tape. However, indeed you can simulate a sort of NL-oracle using Immerman.

 

4. No, the gap-Col[3,4] problem is the following: Is the chromatic number at most 3 or at least 4. In other words, it is equivalent to the 3-colorability problem.

[Ran Ziv]

thanks for the answers!
I was actually refering to the normal 3SAT problem and not E3SAT, but
I guess it's not needed for the test..
(I know there's an obvious 2 approx for 3SAT, i was just wondering if
one can do better..)

On Jul 25, 11:49 am, Ido Ben Eliezer <idob...@gmail.com> wrote:
> 1. Indeed, 8/7 is the best approximation for Max-E3SAT (and this is tight by
> the PCP theorem).
>
> 2. Basically, it's a bit difficult to define oracles with log-space machine,
> because it is not well-defined how much space you may use on the oracle
> tape. However, indeed you can simulate a sort of NL-oracle using Immerman.
>
> 4. No, the gap-Col[3,4] problem is the following: Is the chromatic number at
> most 3 or at least 4. In other words, it is equivalent to the 3-colorability
> problem.
>