NP trees and Carnap´s modal logic

We consider problems and complexity classes definable by interdependent queries to an oracle in NP. How the queries depend on each other is specified by a directed graph G. We first study the class of problems where G is a general dag and show that this class coincides with Δ₂^P. We then consider the class where G is a tree. Our main result states that this class is identical to P^NP [O(log n)], the class of problems solvable in polynomial time with a logarithmic number of queries to an oracle in NP. Using this result we show that the following problems are all P^NP[O(logn)] complete: validity-checking of formulas in Carnap´s modal logic, checking whether a formula is almost surely valid over finite structures in modal logics K, T, and S4, and checking whether a formula belongs to the stable set of beliefs generated by a propositional theory