On Mon, 30 Dec 2002, Rich Neapolitan wrote: > I was wondering if anyone knew of a list of hard problems in AI, or if > anyone could just inform me of the ones of which they were aware.
Wouldn't it be a lot less work to just list all of the interesting problems in AI that are NOT NP-hard? :-) Here are two problems for your list: 1. Not only is it NP-hard to minimize the number of nonzero neural-network weights needed to correctly classify all members of a training set, even when restricted to a single-layer perceptron, but it is NP-hard to come within any constant factor of the minimum. 2. Not only is it NP-hard to find weights that minimize the number of misclassification errors in a neural network, even when restricted to a single-layer perceptron, but it is NP-hard to come within any constant factor of the minimum. If this is the kind of thing you're looking for, I can get the references for you.
