Prev: Solutions manual to Computer Networks Systems Approach 3ed by davie Peterson
Next: Need Fake A Level
From: cplxphil on 25 Nov 2008 11:38
On Nov 25, 8:02 am, Cenny Wenner <CWen...(a)gmail.com> wrote:
> On Nov 25, 4:19 am, cplxp...(a)gmail.com wrote:
>
>
>
> > On Nov 24, 3:07 pm, cplxp...(a)gmail.com wrote:
>
> > > On Nov 23, 5:36 am, Cenny Wenner <CWen...(a)gmail.com> wrote:
>
> > > > On Nov 23, 3:57 am, cplxp...(a)gmail.com wrote:
>
> > > > > Hello all,
>
> > > > > Does anyone know of a problem that is in NP^(NP^NP) that is not known
> > > > > to be in NP^NP?  (This could not be proven short of proving P != NP,
> > > > > since if P = NP the two classes mentioned are both equal to P.)
>
> > > > > I know from Sipser's textbook that NONMIN_FORMULA is in NP^NP but
> > > > > probably not in NP; but I couldn't come up with a problem that is in
> > > > > NP^(NP^NP) that's probably not in NP^NP.
>
> > > > > Also, if anyone knows of such a problem, is there a general method to
> > > > > find such problems for any number of iterations of adding NP oracle
> > > > > machines to the class?  In other words...is there a way to find a
> > > > > problem in NP^(NP^(NP^NP)), and a problem in NP^(NP^(NP^(NP^NP)))?
>
> > > > > -Phil
>
> > > >   You're looking for material on the polynomial hierarchy (PH), such
> > > > ashttp://en.wikipedia.org/wiki/Polynomial_hierarchyorhttp://www.wisdom..... NP^NP =
> > > > Sigma^P_2, a language on the second level of the PH, and NP^(NP^NP) =
> > > > Sigma^P_3, a language on the third level. Since these classes are
> > > > closed under Karp-reductions, if any complete problem of a higher
> > > > level is in a lower level, then all levels from the lower one and up
> > > > are are identical ("PH collapses to the lower level"). There's some
> > > > belief that this isn't the case.
> > > >   A canonical complete problem for Sigma^P_k is (Existential)
> > > > Quantified Satisfiability with k Alternations of Quantifiers (see
> > > > Papadimitriou's Computational Complexity or the section 'Problems in
> > > > the polynomial hierarchy' on Wikipedia). Sigma^P_0 = P, and a
> > > > canonical problem for this level is "given a well-formed formula in
> > > > conjunctive normal form, decide if it is true". For instance "Is
> > > > [(True or False or True) and (False or False or True)] true?") (0
> > > > quantifiers). For NP, you have satisfiability, i.e. given a formula in
> > > > CNF with variables, decide whether it is possible to set the variables
> > > > to true and false in such a way that the formula evaluates to true.
> > > > This could be written
> > > > Exists (x_1, ..., x_n) p(x_1, ..., x_n), with p expressible as a CNF.
> > > > (1 quantifier)
> > > > Likewise, for NP^(NP^NP), PH would collapse if one could show that the
> > > > truth of formulas looking like the following can be recognized in
> > > > NP^NP,
> > > > Exists (x_1, x_2, ..., x_k) forAll (x_{k+1}, ..., x_t) Exists (x_{t
> > > > +1}, ..., x_n) p(x_1, ..., x_n)
> > > > (3 quantifiers)
>
> > > Awesome, thank you.
> > > -Phil
>
> > May I ask a follow-up question?
>
> > Do you know where I can find information on what "alternations of
> > quantifiers" means?  I don't understand what that means.
>
> > Thanks,
> > Phil
>
>   'k alternations' simply means that you have k groups of the
> consecutive quantifiers of the same type. Note that k groups of
> quantifiers corresponds k-1 changes in quantifier types.
>
>   This example, which I gave above,
> Exists (x_1, x_2, ..., x_k) forAll (x_{k+1}, ..., x_t) Exists (x_{t
> +1}, ..., x_n) p(x_1, ..., x_n),
> can also be written as
> Exists x_1 Exists x_2 ... Exists x_k   forAll x_{k+1} ... forAll x_t
> Exists x_{t+1}, ..., Exists x_n   p(x_1, ..., x_n).
> You can always go in the other direction as well, i.e. you can replace
> a consecutive group of quantifiers of the same type with just one
> quantifier.
> In both cases, you have some number of existential quantifiers, then
> some number of universal quantifiers, then some number of existential
> quantifiers, and finally a CNF formula. Hence you have three groups of
> quantifiers and the first one is an existential quantifier. Any
> quantified formula that can be written in this way is an instances to
> (Existential) QSAT with 3 Alternations of Quantifiers.
>
>   If that didn't help, you could browse through some textbooks for a
> better explanation, or return to the original definition by Larry
> Stockmeyer: http://www.geocities.com/stockme...(a)sbcglobal.net/pth.pdf
> .
>   These notes on Oded Golrich's lectures are excellent as well, but
> I'm not sure that they mention QSAT_k:http://www.wisdom.weizmann.ac.il/~oded/cc99.html
> .

That was a fairly clear explanation, I think I understand it. Thank
you.

Here's something I'm puzzled by, though. If that's the way it works,
why can't we say that PH = PSPACE? Here's my argument....

It's already known that PH < PSPACE (I'm using < to mean "is a subset
of"), correct? Then all we need to do is show that PSPACE < PH.

Consider the following family of complexity classes: NP; NP^(NP); NP^
(NP^(NP)); NP^(NP^(NP^(NP))); ...

Each of the above classes is in PH. Each class has, as its complete
problem, one of the languages you mentioned...NP is instances of SAT
with one quantifier alternation permitted, NP^NP is SAT with 2
quantifier alternations permitted, and so on. Shouldn't this mean
that a complete problem for the union of all the above classes would
be instances of SAT with any number of quantifier alternations
allowed? And isn't that the same problem as TQBF, which is PSPACE-
complete?

Is there a mistake in my reasoning?

-Phil

From: tchow on 25 Nov 2008 12:00
In article <ceaaf8ca-1f53-469b-be10-38643ca67f8b(a)y18g2000yqn.googlegroups.com>,
<cplxphil(a)gmail.com> wrote:
>Here's something I'm puzzled by, though. If that's the way it works,
>why can't we say that PH = PSPACE? Here's my argument....

This is a common confusion.

Since PH is the union of its levels, any problem in PH must belong to
some *specific* level. Although there is no a priori bound on how high
that level can be, it still has to be at level k for *some* finite k.

And TQBF isn't at level k for any fixed k. (Or at least, there's no
obvious proof that it is.)

In general if you have a sequence of complexity classes C_1, C_2, C_3, ...
and a sequence of languages L_1, L_2, L_3, ... such that L_i is in C_i
for all i, it doesn't follow that the union of the L_i is in the union
of the C_i.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
From: cplxphil on 25 Nov 2008 15:06
On Nov 25, 12:00 pm, tc...(a)lsa.umich.edu wrote:
> In article <ceaaf8ca-1f53-469b-be10-38643ca67...(a)y18g2000yqn.googlegroups..com>,
>
>  <cplxp...(a)gmail.com> wrote:
> >Here's something I'm puzzled by, though.  If that's the way it works,
> >why can't we say that PH = PSPACE?  Here's my argument....
>
> This is a common confusion.
>
> Since PH is the union of its levels, any problem in PH must belong to
> some *specific* level.  Although there is no a priori bound on how high
> that level can be, it still has to be at level k for *some* finite k.
>
> And TQBF isn't at level k for any fixed k.  (Or at least, there's no
> obvious proof that it is.)
>
> In general if you have a sequence of complexity classes C_1, C_2, C_3, ....
> and a sequence of languages L_1, L_2, L_3, ... such that L_i is in C_i
> for all i, it doesn't follow that the union of the L_i is in the union
> of the C_i.
> --
> Tim Chow       tchow-at-alum-dot-mit-dot-edu
> The range of our projectiles---even ... the artillery---however great, will
> never exceed four of those miles of which as many thousand separate us from
> the center of the earth.  ---Galileo, Dialogues Concerning Two New Sciences


Oh, ok. Thanks for clarifying.

-Phil

First  |  Prev  | 
Pages: 1 2
Prev: Solutions manual to Computer Networks Systems Approach 3ed by davie Peterson
Next: Need Fake A Level