Talk:Decision problem

From Wikipedia, the free encyclopedia

WikiProject Mathematics
Mathematics Portal
This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating: Start Class Mid Priority  Field: Discrete mathematics
This article is within the scope of WikiProject Computer science, which aims to create a comprehensive computer science reference for Wikipedia. Visit the project page for more information and to join in on related discussions.
Start rated as start-Class on the assessment scale
Mid rated as mid-importance on the assessment scale

Since the definition of "decision problem" refers to the idea of "problem", I think we should have a page defining what that is.

Contents

[edit] Complete rewrite

I did a complete rewrite of the article. The main problems I tried to fix were

  1. article to verbose without using any well defined concepts
  2. 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)

[edit] Examples, Simpler Please

I thought Wikipedia is an encyclopedia, not an entry-portal to an article in the AMS. I's a pretty tough read for a non-specialist. A budding mathematician (e.g. interested undergrad or high-school math whiz or engineer/scientist not in the field) would be stumped. One place to start would be some relatively examples or a progression from an "easier read" into the deep stuff (or visa versa, but both). Ideas? wvbaileyWvbailey 17:14, 10 January 2006 (UTC)

[edit] Notes section

I am moving this from the main page for now.

It should be noted that a decision problem is always a set of related problems which is in some sense large enough. A single problem P is always trivially decidable by assigning the constant function f(P)≡0 or f(P)≡1 to it.
Nearly every problem can be cast as a decision problem by using reductions, often with little effect on the amount of time or space needed to solve the problem. Many traditional hard problems have been cast as decision problems because this makes them easier to study and to solve, and proving that these problems are hard suffices to show that more complex problems are hard as well.

The first paragraph makes no sense to me. The second seems to have a definition of problem different than decision problem, although the article gives no such definition.

I added a section explaining the equivalence of decision problems and function problems, which I think does an adequate job of replacing the above paragraphs. CMummert 00:11, 27 August 2006 (UTC)

[edit] Equivalence with function problem

I think that this section should be rewritten and grown a bit.

Every function problem can be turned into a decision problem; the decision problem is just the graph of the associated function. If this decision problem were effectively solvable then the function problem would be as well.

I am not sure what is the decision problem of the graph... Is it dec: f(x)=y?. Because that's not enough to solve f(x)? efficiently - set of values of f could be very large. If we had this decision problem then it could work: dec: f(x)<y? where < is lexicographical order. For polynomial-time classes length of f(x) is polynomial, and we can use binary search.

Solution to other decision problems can also easily allow to solve function problem (as with f:Hamiltonian path - dec:Hamiltonian graph, by removing edges; f:the shortest Salesman's route - dec:Salesman's route shorter than<k etc.) Maybe we could give some examples.

Effectively - I understand it is all in the perspective of polynomial-time classes and it means "within polynomial time"? With regard to wider not-necessairly-time classes, i suppose it's also true but effectively has different meaning then.

I am still not sure how to rewrite it. Any suggestions? --SalvNaut 23:43, 9 September 2006 (UTC)

I couldn't stand it and made some changes :) --SalvNaut 00:01, 10 September 2006 (UTC)
This article is not about polynomial time reductions. Here effectively means computably (not necessarily poly time). The graph of a function f is the set of pairs (x,y) such that f(x)=y. A search is required to solve a function problem assuming the graph is computable, but this is no big deal. I reverted to the old version because the new one was much less clear (what is True ?), and wasn't grammatically correct in several places. I added a caveat, though, that the reduction of function problems to decision problems does not respect poly time. CMummert 00:38, 10 September 2006 (UTC)
Thanks, that is much better - example is very good.
One more question regarding Definitions: Is it really so that provable is used in the same meaning as semidecidable? I understand it would encompass provability in FOL. For me, provable means something stronger (not necessairly FOL-provable). --SalvNaut 18:05, 10 September 2006 (UTC)
I have never seen the word provable used as a synonym for r.e. but I left it there in deference to whoever put it in. Probably some textbook or the other includes it. The usage makes sense because the set of provable statements of an effectively axiomatized first order theory is r.e. CMummert 22:40, 10 September 2006 (UTC)

[edit] Definition Conflict

The article on Recursive set states that any language which is not decidable/computable is undecidable. Here, a language that is not decidable may be either semidecidable or undecidable. Are these separate categories or the same? That is, is a recursively enumerable set considered to be a kind of uncomputable set? 67.180.32.231 08:08, 1 April 2007 (UTC)

Yes, a recursively enumerable set that is not recursive is both semidecidable and undecidable. CMummert · talk 12:24, 1 April 2007 (UTC)

[edit] Reference

Would someone be so kind as to refer me to the source for this result mentioned in the article? "However, this reduction is more liberal than the standard reduction used in computational complexity..." and so on, about the complexity of characteristic functions differing from standard complexity. I don't see it in Sipser, and I'd like to learn more. 128.32.192.124 01:04, 20 April 2007 (UTC)

The user who made that edit gave the following reference [1] and said to look at the appendix. I think that the article is just trying to point out that computational complexity tends to use many-one reductions rather than Turing reductions, but it could be worded more clearly. CMummert · talk 01:14, 20 April 2007 (UTC)
Thank you so much! I agree that it should probably simply be rewritten to state what you're saying, although for now I will add the reference. 67.180.4.242 22:15, 21 April 2007 (UTC)

[edit] Undecidable problem example?

Is it possible to give a simple example of a decision problem that is not decidable? I checked the referenced article that lists undecidable problems, but they all require too much brainpower to grasp to be useful as an example of the concept. I'm wondering if maybe there are trivial undecidable problems that aren't interesting, but at least demonstrate the concept. Bryan Henderson 15:45, 21 June 2007 (UTC)

A popular one for just this purpose are tiling problems, such as those described by Wang tiles. Reference here. Dcoetzee 01:23, 22 June 2007 (UTC)

[edit] Merge from Undecidable problem

It has been proposed to merge Undecidable problem into here, but I do not see the point. Decision problems can also be classed into tractable/untractable etc. (rather than decidable/undecidable). Recursive language would be a better target for merge. Tizio 12:41, 8 February 2008 (UTC)

  • Doesn't really matter to me. This is just where I saw stuff on undecidable problems, so I chose here. --UsaSatsui (talk) 18:06, 8 February 2008 (UTC)
  • I would say no to a merge; as a non-expert I'm finding the subject confusing enough as it is, without jumbling it up even more. (I've recorded there that I'd be against deletion also) Moonraker12 (talk) 13:30, 12 February 2008 (UTC)
    • They are literally and exactly the same topic. The issue here is simply that no redirect existed and a new author created the undecidable problem article instead of expanding and clarifying this one. There is also List of undecidable problems. — Carl (CBM · talk) 14:45, 12 February 2008 (UTC)
      • They are not the same topic. At least, not literally and not exactly. Decision problems can also be divided into tractable/untractable; the relation between decisions problems and function problems is not specific to decidability. I agree that a better division of material could be operated. Tizio 16:32, 12 February 2008 (UTC)
        • I appreciate your concern about computational complexity. Perhaps I should have said that an undecidable problem is a kind of decision problem rather than the same as a decision problem. The recursive language article is another issue entirely. — Carl (CBM · talk) 16:42, 12 February 2008 (UTC)
          • Yes, that's precisely my point. While it's possible to have "undecidable problem" included here, I'd rather see something moved from here to there. Tizio 16:53, 12 February 2008 (UTC)
            • What do you think of the slight rearrangement of this article I tried this afternoon? — Carl (CBM · talk) 17:44, 12 February 2008 (UTC)
              • Excellent!!! Your change really clarifies the difference between the definition of decision problems and its possible classifications. Tizio 18:07, 13 February 2008 (UTC)
                • I see you’ve created sections on Decideability and Complete Problems, with links to main articles. That seems a better arrangement; would that be the outcome of the merger proposal? It seems better than bringing that stuff over to here. On the same note, is there a case for merging "List of UP" into "UP"? Or trimming those sections of "UP" and linking to "List"? Moonraker12 (talk) 18:23, 14 February 2008 (UTC)
  • No, they're not the same thing - a decision problem is a problem with a yes/no answer, and is a basic object studied in complexity and computability theory. It's not the same thing as a decidable problem, which is an effectively computable problem as studied in computability theory. Unless you plan to enumerate and explain the many possible classifications for decision problems here, a merge is inappropriate - better would be to briefly mention some classifications and link to relevant articles on decidability and undecidable problems. Dcoetzee 09:55, 14 February 2008 (UTC)
Actually, I just realized that Decidable problem and Undecidable problem redirect to distinct articles. There's a lot of nonsense in the organization of these articles because different classes of mathematicians have historically used different terminologies to refer to the same object.
If we keep all these articles without going through a few merges, a lot of work will have to be done twice to improve and expand the content. We can always keep the redirects in the relevant categories, which should make everyone happy. Pichpich (talk) 20:16, 20 February 2008 (UTC)
I would be fine with some merges provided the article titles are neutral - Recursive languages and sets, Computable sets and languages, or something like that. Computable function seems fine; recursive function is a disambiguation page. It would be worth announcing merges at both the computer science and mathematics wikiprojects (I'm affiliated with the latter). — Carl (CBM · talk) 22:16, 20 February 2008 (UTC)
Yup, probably important to manage susceptibilities by picking a neutral, if slightly awkward title and by letting everybody know. Perhaps it is best to construct both Recursive languages and sets and Computable sets and languages first (I mean without redirecting the other pages to it) and then gather opinions about whether this makes more sense. I'm willing to give a hand. My background is theoretical CS so if math people want to help out, that would be great. Pichpich (talk) 22:22, 20 February 2008 (UTC)
Experiment now under way. I've created Recursive languages and sets. Let's see if we can find a smart way to do this. Pichpich (talk) 22:29, 20 February 2008 (UTC)

Side note: another absurd content fork is Word problem (computability). For one thing that terminology has almost entirely gone out of style and is almost solely used either in its group theoretical sense (word problem for groups) or its generalization to monoids, quasigroups or magmas. As mentioned earlier, all modern textbooks have (wisely) decided to identify a formal language with its associated decision problem. So Word problem (computability) should be merged back to Decision problem. Pichpich (talk) 22:44, 20 February 2008 (UTC)

Ick. I thought that article was the one about the word problem for groups, from the title. If there is a merge afoot, that article should definitely be included. — Carl (CBM · talk) 23:17, 20 February 2008 (UTC)

Since Recursive languages and sets actually contains sections about undecidable problems, I believe it should be rather named Decidability or something like that. An equivalent solution is to have this article only discuss decidable problems while keeping undecidable ones in a separate article. Tizio 10:09, 21 February 2008 (UTC)

It would need to be Decidability (computability) or something like that, because there is already Decidability (logic) on a different subject; Decidability redirects to a disambig page. But I like Decidability (computability), because it's punchy and neutral. — Carl (CBM · talk) 13:35, 21 February 2008 (UTC)
Actually, Decidability (logic) is about the decidablity of the problem of whether a logical formula is in a given set (e.g., whether a first-order formula is satisfiable); it's the application of the concept of decidability to logical decision problems. A summary of it could be included (with a link, as per Wikipedia:Summary style), in a section of Decidability. Tizio 15:08, 21 February 2008 (UTC)
Yes, that's a good idea. — Carl (CBM · talk) 16:38, 21 February 2008 (UTC)