2 papers
cs.CC1998
Tally NP Sets and Easy Census Functions
Judy Goldsmith, Mitsunori Ogihara, Joerg Rothe
We study the question of whether every P set has an easy (i.e., polynomial-time computable) census function. We characterize this question in terms of unlikely collapses of languag…
cs.AI1998
The Computational Complexity of Probabilistic Planning
M. L. Littman, J. Goldsmith, M. Mundhenk
We examine the computational complexity of testing and finding small plans in probabilistic planning domains with both flat and propositional representations. The complexity of pla…