Talk:Decision problem
From Academic Kids
Since the definition of "decision problem" refers to the idea of "problem", I think we should have a page defining what that is.
Complete rewrite
I did a complete rewrite of the article. The main problems I tried to fix were
- article to verbose without using any well defined concepts
- mixed word problem (computability) with general concept of decision problem, which I think should be separate
MathMartin 13:46, 19 Nov 2004 (UTC)
- I like the brevity, but it seems to focus strongly on computability theory, particularly in the examples section. I'll add some example problems important in complexity theory and make a note that the list is only a few important examples. Deco 18:55, 19 Nov 2004 (UTC)
I've edited again because there is a difference between computability and decidability. I've also created a similar looking computation problem stub. The class of decidable problems is reducible to the class of computable functions.
We should add interesting classes of questions that are decidable. I.e., subsets of the predicate calculus that are decidable (i.e. monadic predicate logic, all valid formulas, etc.), the propositional calculus, trivially any finite set (not so interesting I suppose), and so on. Nortexoid 02:02, 23 Nov 2004 (UTC)
