This paper introduces nondeterminism into logic programs with negation
by associating functional dependencies with some predicates, and deve
lops the well-founded choice semantics. Each program has at least one
well-founded choice model. The well-founded choice semantics extends t
he well-founded semantics with nondeterminism, while maintaining the r
obustness and polynomial time data complexity of the well-founded sema
ntics. It generalizes the stable model semantics of Datalog with choic
e to logic programs with negation, and yet avoids the problem of NP-co
mpleteness of the existence of stable models in general. Although mode
l-theoretic in nature, the well-founded choice semantics expresses pre
cisely nondeterministic polynomial-time queries (NDB-PTIME). We presen
t a nondeterministic fixpoint semantics that is sound and complete wit
h respect to the well-founded choice semantics.