Prev: Solutions manual to Computer Networks Systems Approach 3ed by davie Peterson
Next: Need Fake A Level
From: cplxphil on 22 Nov 2008 21:57

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

From: Cenny Wenner on 23 Nov 2008 05:36
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
as http://en.wikipedia.org/wiki/Polynomial_hierarchy or
http://www.wisdom.weizmann.ac.il/~oded/PS/CC/l9.ps . 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)
From: cplxphil on 24 Nov 2008 15:07
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.weizmann.ac.il/~oded/PS/CC/l9.ps. 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

From: cplxphil on 24 Nov 2008 22:19
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
From: Cenny Wenner on 25 Nov 2008 08:02
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/stockmeyer(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
..
 |  Next  |  Last
Pages: 1 2
Prev: Solutions manual to Computer Networks Systems Approach 3ed by davie Peterson
Next: Need Fake A Level