Talk:Search problem

This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Mathematics Low‑priority This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics articles Low This article has been rated as Low-priority on the project's priority scale. Computer science Mid‑importance This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science articles Mid This article has been rated as Mid-importance on the project's importance scale. Things you can help WikiProject Computer science with: Here are some tasks awaiting attention: Article requests : Requested articles/Applied arts and sciences/Computer science, computing, and Internet Cleanup : Computer science articles needing attention Computer science articles needing expert attention Copyedit : Computing Expand : Computer science Infobox : Computer science articles without infoboxes Maintain : Timeline of computing 2020–present Photo : Find pictures for the biographies of computer scientists (see List of computer scientists) Computing articles needing images Stubs : Computer science stubs Unreferenced : WikiProject Computer science/Unreferenced BLPs Project-related : Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

This is explained really difficult. Isn't "finding a value in a list" also a search problem? I would add it myself, but I have no time now. 131.155.73.81 (talk) 12:05, 10 November 2010 (UTC)[reply]

The article has incomplete symbols which make it difficult to understand. First sentence "such that field(R) ⊆ Γ+" What set does tau represent? ${\displaystyle L(R)=\{x\mid \exists yR(x,y)\}.\,}$ L(R) = x such that there exists y <what?> R(x,y) EaswarH 02:44, 14 December 2011 (UTC)

The three references are identical. This should be corrected.Shuroo (talk) 19:54, 15 December 2013 (UTC)[reply]

This article appears to be a poor mash-up of the PlanetMath article and Brown's lecture notes. It is even hard to tell that they are talking about the same thing. There are texts about this subject. We can certainly do better than this.--Bill Cherowitzo (talk) 03:50, 19 June 2016 (UTC)[reply]

On 14 Mar 2019, I inserted a deletion request with the following concern: "The article is poorly written (see issues box below). More important, its lead is about the function problem in computational complexity theory while its rest seems to be about a particular kind of graph traversal or search algorithm. If there is any valuable text here, it should be integrated into one of these. After deletion, search problem could be made a redirect to function problem, or a disambiguation page listing all three articles mentioned."

On 22 Mar, Explicit deleted the page: "Expired PROD".

On 9 June 2019, Shyam Has Your Anomaly Mitigated requested on Wikipedia:Requests for undeletion to restore the page: "None of the relevant pages mentioned in the deletion log were updated. There are between 16, and 38, pages that still link to Search problem. There 84 pages that contain "search problem". There is also Linear search problem. If we can have Optimization problem, then we should also have Search problem. This should at least be discussed."

On the same day, Graeme Bartlett restored the page.

I still have the same problems with the page as expressed in my deletion request. The reply from Shyam doesn't address the page contents, but merely the number of references to the page. So I repeat my above suggestion, and hope for a discussion on the page contents this time. - Jochen Burghardt (talk) 09:45, 9 June 2019 (UTC)[reply]

Using the IPO model, and linguistics (description versus prescription); function problems are about already having an Output prescription for every Input of a given Process, while search problems are about having a description of the Output, and a given Input, without knowledge of any Process (where the Process becomes the Output, the Output becomes the Input, and the Input becomes the Process; although, the Output is incomplete Input, as it is merely a description, which only becomes a prescription when the satisfiable Process is totally checked). -- Shyam Has Your Anomaly Mitigated (talk) 12:41, 9 June 2019 (UTC)[reply]

The Sussman anomaly from Blocks world described as a search problem: Output = stack the blocks alphabetically; Input = [B on the table, C atop A, A on the table]; Process = ¿list of possible computational instructions; where there can be more than one solution, and finding all of them can turn into an optimisation problem, but there can also be no possible solution?; (The Process is computed based on the facts & rules of blocks world.) -- Shyam Has Your Anomaly Mitigated (talk) 13:14, 9 June 2019 (UTC)[reply]

You know what you have. You know what you want. What do you need to get from what you have to what you want? -- Shyam Has Your Anomaly Mitigated (talk) 14:35, 9 June 2019 (UTC)[reply]

@Shyam Has Your Anomaly Mitigated: Sorry, I don't understand your point(s). Is there any connection of your text to the lead? Or to the remainder of the article? Or do you argue in favor of a third meaning of "search problem", used in software engineering? What is the relation of your programming paradigms box to this article? - Your link "totally" goes to a DAB page, which meaning did you have in mind? Your link "satisfiable" goes to a page about mathematical logic / model theory; I don't see any connection to a "process". - Jochen Burghardt (talk) 20:29, 9 June 2019 (UTC)[reply]

@Jochen Burghardt: I don't understand the WP:TECHNICAL lead, but the rest of the article seems relevant. The lead divagates from PlanetMath; using ${\displaystyle T}$ to compute ${\displaystyle R}$ instead of ${\displaystyle f}$, which makes more sense. I haven't read any further into the lead, since it's anomalous so early on. PlanetMath is WP:USERGENERATED; "Math for the people, by the people.". -- Shyam Has Your Anomaly Mitigated (talk) 23:37, 9 June 2019 (UTC)[reply]

I got so carried away, I forgot the rest of your discussion! My earlier response was about your claim that search problems are function problems. Declarative programming is about describing what a problem is, so the computer can compute how to solve it. I was referring to totality checking; "The mathematical concept of a function being total vs. partial". And satisfiability in the logical sense; "A formula is satisfiable if it is possible to find an interpretation (model) that makes the formula true.". -- Shyam Has Your Anomaly Mitigated (talk) 23:50, 9 June 2019 (UTC)[reply]

The process is from the IPO model. -- Shyam Has Your Anomaly Mitigated (talk) 00:12, 10 June 2019 (UTC)[reply]

@Shyam Has Your Anomaly Mitigated: Thanks for your explanantions. In fact, the lead is about something completely different. I stated this already in the deletion proposal. By now, I have learned that this proposal wasn't adequate; spltting the article into two, e.g. "Search problem (complexity)" for the lead, and "Search problem (programming)" for the rest would be better. - What do you think of this? - Jochen Burghardt (talk) 16:23, 12 June 2019 (UTC)[reply]

@Jochen Burghardt: I sectioned off the lead; unless you can explain the differences, I consider them to be the same (I fixed the mistake from when it was copied from PlanetMath, and this now follows the rest of the article). -- Shyam Has Your Anomaly Mitigated (talk) 18:39, 12 June 2019 (UTC)[reply]

Sorry, but that doesn't make sense. The meaning of "search problem" in computational complexity is different from what you described in the new lead. - Jochen Burghardt (talk) 19:14, 12 June 2019 (UTC)[reply]

Where are you getting your information from? The complexity text in the article comes from PlanetMath, which says ${\displaystyle T}$ computes ${\displaystyle f}$, and ${\displaystyle y=f(x)}$. -- Shyam Has Your Anomaly Mitigated (talk) 19:19, 12 June 2019 (UTC)[reply]

In the current lead, i.e. in complexity theory, search problems (also called function problems) are distinguished from decision problems. The latter are asking for algorithms with "yes"/"no" answer only, while the former are more general in that they ask for algorithms with an arbitrary output set. So the term "search" is used as opposite of "decision" in this field. For example, the problem of computing the sum of two natural numbers is a search problem. (This is compatible with the current lead, the planetMath article, and your above remark of 12 Jun.) —

In contrast, in the current article body, search problems are problems related to some state graphs, which is something quite different. For example, consider some two-person strategy game that doesn't allow a draw. Given some game state (e.g. board position), finding the best move can be considered a search problem (in the state graph sense) in a natural way. Similarly for the problem to decide whether the state is a win- or a loose state; however, in the complexity terminology, this is a decision problem. On the other hand, computing sums can hardly be related to a state graph search. —

If I understood you right, you intend to introduce a third meaning of search problem, used in programming, meaning the task to find an algorithm to compute some output from some input such that they satisfy some given relation. This describes just the task of programming itself, so every programming task would be a search problem in you sense, wouldn't it? —

In the lead you suggested on 12 Jun, I don't understand the difference between "finding a function" and "implementing a function". —

As a side remark, I still don't know what to make of your above "IPO/linguistics" paragraph. I don't see how a process can be satisfiable or not. A process is not a formula. Moreover, termination analysis applies to programs, not to their execution runs (a.k.a. as processes). - Jochen Burghardt (talk) 10:02, 14 June 2019 (UTC)[reply]

Besides the aforementioned mistake in the current lead, these are unquoted:

• In computational complexity theory and computability theory, a search problem is a type of computational problem represented by a binary relation.
• Intuitively, the problem consists in finding structure "y" in object "x". An algorithm is said to solve the problem if at least one corresponding structure exists, and then one occurrence of this structure is made output; otherwise, the algorithm stops with an appropriate output ("Item not found" or any message of the like).
• Such problems occur very frequently in graph theory, for example, where searching graphs for structures such as particular matching, cliques, independent set, etc. are subjects of interest.

Graph theory is used to formalise programming. Just as Binary trees represent S-expressions; the concept is shared, instead of being split. Mathematics is used to describe life, the universe, and everything; there is no separation between the mathematical concept of counting, and the concept of counting sheep to fall asleep, because counting is counting.

The article does not include any citation that supports your claim that search problems are function problems in any way; the only mention is in their respective "See also" sections. We might as well merge Entscheidungsproblem with Decision problem.

In fact, Function problem has no footnotes! According to the template at the foot of the page.

Both these articles lack proper citations, which is indicative of amateur authorship.

I hope your knowledge of these concepts does not solely depend on Wikipedia alone; you can't learn this kind of stuff from Wikipedia.

There are others who agree that search problems are not function problems; even the Wikipedia page on Computational problem they link to has no footnotes!

This, and that, also supports the notion that search problems are not function problems.

The fifth page of this says function problems are a specialisation of search problems; so if anything, function problems should be merged into search problems.

Of course, any decision problem can be viewed as a function problem, and any function problem can be viewed as a search problem. However, the reverse of either of these statements does not hold in general.

Here we are following the standard naming convention, even though the term "function problem" is misleading for the reason pointed out earlier.

Here is the mathematics of a function problem as a search problem.

By "finding a function", I mean Metaprogramming, where you implement a more general ${\displaystyle f_{0}}$ that finds, and implements, any ${\displaystyle f_{1}}$; instead of you implementing a specific ${\displaystyle f_{1}}$.

You should learn Prolog to understand satisfiability in a programmatic sense.

Curry–Howard correspondence; with regards to formulas, and processes.

Processes are programs.

-- Shyam Has Your Anomaly Mitigated (talk) 12:04, 14 June 2019 (UTC)[reply]

I'm tired of this lengthy discussion; as far as I'm concerned, proceed editing this article as you like. - Jochen Burghardt (talk) 20:08, 15 June 2019 (UTC)[reply]

It's probably not worth the effort, since it'll just get deleted again anyway; it's just too easy to delete stuff around here, and I couldn't explain it to you, therefore I couldn't explain it to anyone else who doesn't already know what I'm talking about, and trying to find trivially accessible references outside of textbooks is labourious; as far as I'm concerned, proceed deleting this article as you like. -- Shyam Has Your Anomaly Mitigated (talk) 20:28, 15 June 2019 (UTC)[reply]