NP with oracle machines
in [Theory]
|
From: cplxphil on 5 Jul 2008 10:02 Hello, I have a question pertaining to the complexity class NP and oracle machines. Suppose you are dealing with the class NP relative to a particular oracle machine, say one for SAT or TQBF. If you wanted to actually physically compute membership to a language that belongs to this complexity class, what would you have to do? For example, if I am dealing with a language/decision problem that is simply in NP, I could map the instance of the decision problem to an instance of SAT, and then try to calculate the solution in exponential time. But if I am dealing with a language in NP^TQBF, I don't know how you would actually compute whether or not an instance is in the language or not. Could you still end up working with an instance of SAT? Would you have an instance of SAT and then end up needing to calculate a single instance of TQBF? Anyone know the answer to this? (Did I make the question clear?) -Phil
From: Zhu Guohun on 5 Jul 2008 23:15 On 7ÔÂ5ÈÕ, ÏÂÎç10ʱ02·Ö, cplxp...(a)gmail.com wrote: > Hello, > > I have a question pertaining to the complexity class NP and oracle > machines. > > Suppose you are dealing with the class NP relative to a particular > oracle machine, say one for SAT or TQBF. If you wanted to actually > physically compute membership to a language that belongs to this > complexity class, what would you have to do? > > For example, if I am dealing with a language/decision problem that is > simply in NP, I could map the instance of the decision problem to an > instance of SAT, and then try to calculate the solution in exponential > time. > > But if I am dealing with a language in NP^TQBF, I don't know how you > would actually compute whether or not an instance is in the language > or not. Could you still end up working with an instance of SAT? > Would you have an instance of SAT and then end up needing to calculate > a single instance of TQBF? > > Anyone know the answer to this? (Did I make the question clear?) > > -Phil I am not very understand some symbol of your topic, such as NP^TQBF If your think P=NP, then the answer is clearly that your can find a simple instance of SAT to your question. If your think P<>NP, then the answer is aslo clearly that your can find a instance among the hierarchy NP problem. ------------------------ Zhu
From: PhilipJWhite on 6 Jul 2008 11:03 On Jul 5, 11:15 pm, Zhu Guohun <ccgh...(a)hrt.dis.titech.ac.jp> wrote: > On 7ÔÂ5ÈÕ, ÏÂÎç10ʱ02·Ö, cplxp...(a)gmail.com wrote: > > > > > Hello, > > > I have a question pertaining to the complexity class NP and oracle > > machines. > > > Suppose you are dealing with the class NP relative to a particular > > oracle machine, say one for SAT or TQBF. If you wanted to actually > > physically compute membership to a language that belongs to this > > complexity class, what would you have to do? > > > For example, if I am dealing with a language/decision problem that is > > simply in NP, I could map the instance of the decision problem to an > > instance of SAT, and then try to calculate the solution in exponential > > time. > > > But if I am dealing with a language in NP^TQBF, I don't know how you > > would actually compute whether or not an instance is in the language > > or not. Could you still end up working with an instance of SAT? > > Would you have an instance of SAT and then end up needing to calculate > > a single instance of TQBF? > > > Anyone know the answer to this? (Did I make the question clear?) > > > -Phil > > I am not very understand some symbol of your topic, such as NP^TQBF > > If your think P=NP, then the answer is clearly that your can find a > simple instance of SAT to your question. > > If your think P<>NP, then the answer is aslo clearly that your can > find a instance among the hierarchy NP problem. > > ------------------------ > Zhu NP^TQBF means, NP with an oracle machine for TQBF. I am interested in how to actually physically compute the answer to the problem.
From: cplxphil on 6 Jul 2008 11:07 On Jul 5, 11:15 pm, Zhu Guohun <ccgh...(a)hrt.dis.titech.ac.jp> wrote: > On 7ÔÂ5ÈÕ, ÏÂÎç10ʱ02·Ö, cplxp...(a)gmail.com wrote: > > > > > Hello, > > > I have a question pertaining to the complexity class NP and oracle > > machines. > > > Suppose you are dealing with the class NP relative to a particular > > oracle machine, say one for SAT or TQBF. If you wanted to actually > > physically compute membership to a language that belongs to this > > complexity class, what would you have to do? > > > For example, if I am dealing with a language/decision problem that is > > simply in NP, I could map the instance of the decision problem to an > > instance of SAT, and then try to calculate the solution in exponential > > time. > > > But if I am dealing with a language in NP^TQBF, I don't know how you > > would actually compute whether or not an instance is in the language > > or not. Could you still end up working with an instance of SAT? > > Would you have an instance of SAT and then end up needing to calculate > > a single instance of TQBF? > > > Anyone know the answer to this? (Did I make the question clear?) > > > -Phil > > I am not very understand some symbol of your topic, such as NP^TQBF > > If your think P=NP, then the answer is clearly that your can find a > simple instance of SAT to your question. > > If your think P<>NP, then the answer is aslo clearly that your can > find a instance among the hierarchy NP problem. > > ------------------------ > Zhu NP^TQBF means, NP with an oracle machine for TQBF. I am interested in how to actually physically compute the answer to the problem.
From: Zhu Guohun on 7 Jul 2008 11:21
On 7ÔÂ6ÈÕ, ÏÂÎç11ʱ07·Ö, cplxp...(a)gmail.com wrote: > On Jul 5, 11:15 pm, Zhu Guohun <ccgh...(a)hrt.dis.titech.ac.jp> wrote: > > > > > > > On 7ÔÂ5ÈÕ, ÏÂÎç10ʱ02·Ö, cplxp...(a)gmail.com wrote: > > > > Hello, > > > > I have a question pertaining to the complexity class NP and oracle > > > machines. > > > > Suppose you are dealing with the class NP relative to a particular > > > oracle machine, say one for SAT or TQBF. If you wanted to actually > > > physically compute membership to a language that belongs to this > > > complexity class, what would you have to do? > > > > For example, if I am dealing with a language/decision problem that is > > > simply in NP, I could map the instance of the decision problem to an > > > instance of SAT, and then try to calculate the solution in exponential > > > time. > > > > But if I am dealing with a language in NP^TQBF, I don't know how you > > > would actually compute whether or not an instance is in the language > > > or not. Could you still end up working with an instance of SAT? > > > Would you have an instance of SAT and then end up needing to calculate > > > a single instance of TQBF? > > > > Anyone know the answer to this? (Did I make the question clear?) > > > > -Phil > > > I am not very understand some symbol of your topic, such as NP^TQBF > > > If your think P=NP, then the answer is clearly that your can find a > > simple instance of SAT to your question. > > > If your think P<>NP, then the answer is aslo clearly that your can > > find a instance among the hierarchy NP problem. > > > ------------------------ > > Zhu > > NP^TQBF means, NP with an oracle machine for TQBF. I am interested in > how to actually physically compute the answer to the problem.- Òþ²Ø±»ÒýÓÃÎÄ×Ö - > > - ÏÔʾÒýÓõÄÎÄ×Ö - the actually physically compute depend on the NP problem instead of TQBF, because the oracle matchine for TQBF in your question is only a blackbox. ------------------- Zhu |