Timeline for What is the difference between an algorithm, a language and a problem?
Current License: CC BY-SA 4.0
22 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Nov 25, 2021 at 4:24 | history | suggested | ygeMason | CC BY-SA 4.0 |
make it slightly simpler to read x2
|
| Nov 25, 2021 at 4:12 | review | Suggested edits | |||
| S Nov 25, 2021 at 4:24 | |||||
| S Oct 5, 2021 at 17:30 | history | suggested | Charlie Tian | CC BY-SA 4.0 |
Clarify that the formalization of problems in binary outputs is only for decision problems (in the same sentence)
|
| Oct 5, 2021 at 10:51 | review | Suggested edits | |||
| S Oct 5, 2021 at 17:30 | |||||
| Sep 4, 2017 at 12:01 | comment | added | YOUSEFY | a problem is given some inputs with description and properties how to answer it. Now if we say $x \in L$, (where x is the input and L is the language that has special encoding of the problem) then we say the definition is fine. Suppose that we do not know about x and we want to know whether it is a subset of this language or not. Then we use "algorithm" to see. Suppose Algorithm A is able to test whether x is subset of L or not. Then, we are able to say: If A[x] accepts, then $x \in L$ and if A[x] rejects, then $x \notin L$. | |
| Sep 4, 2017 at 11:52 | comment | added | YOUSEFY | @jmite Also, another note: instead of saying "... all complexity classes. [...] contain problems, not algorithms", we should say " ... all complexity classes. [...] contain languages". So, complexity class has a language [not algorithms and not problems]. The reason behind this is that x the input of the algorithm is subset of the alphabet. So, if $x \in P$, (where x is input and P is the problem) since x is input so it is subset from the alphabet. But P has no meaning here! there is a definition of problem. We have definition of problem in optimization that says: .... | |
| Sep 4, 2017 at 11:31 | comment | added | YOUSEFY | @jmite Thank you for your answer. I also want to add that instead of saying "if there exists some algorithm solving that problem with a given time complexity" we say "if there exists at least one algorithm solving that problem with a given time complexity". Because for example it is enough to show one polynomial algorithm for solving a decision NP-complete problem to be in P. | |
| Mar 31, 2017 at 7:03 | comment | added | Joey Eremondi | @gnasher729 there's a theorem that says it can be defined in terms of verifying, but it's actual definition is in terms of time complexity for Non deterministic machines, thus the name NP: nondeterministic polynomial | |
| Mar 30, 2017 at 18:26 | comment | added | gnasher729 | NP isn't really about the time complexity of solving a problem; it says (roughly) that a solution can be verified in polynomial time. NP and co-NP are very different, but take exactly the same time to solve. | |
| Jun 14, 2016 at 23:24 | vote | accept | Joey Eremondi | ||
| Jan 3, 2016 at 6:35 | comment | added | Joey Eremondi | Thanks @CaptainCodeman! Though I did set myself up for it by asking it as a reference question :P | |
| Jan 2, 2016 at 21:44 | comment | added | CaptainCodeman | Dude, this is the greatest answer I've ever seen. You just summarized all of computer science in 1 page. | |
| S Dec 8, 2014 at 8:07 | history | suggested | Cosmo Harrigan | CC BY-SA 3.0 |
Fix the enumeration formatting; it was incorrectly labelled 1, 1, 2 instead of 1, 2, 3
|
| Dec 8, 2014 at 2:29 | review | Suggested edits | |||
| S Dec 8, 2014 at 8:07 | |||||
| Mar 20, 2014 at 3:09 | comment | added | Joey Eremondi | Says who? That kind of thinking is part of why people had so much trouble formalizing and algorithm before the intention of the Turing Machine. The Church-Turing Thesis says that an algorithm IS a turing machine and vice versa, and not all turing machines halt. | |
| Mar 19, 2014 at 15:27 | comment | added | Tanmoy Banerjee | A language can be infinite but an algorithm MUST halt in a finite number of steps. | |
| Aug 18, 2013 at 9:43 | comment | added | Kaveh | I think it would be good to mention that there are other kinds of computational problems (e.g. search problems). | |
| Aug 11, 2013 at 17:08 | history | edited | Joey Eremondi | CC BY-SA 3.0 |
deleted 2 characters in body
|
| Aug 10, 2013 at 12:18 | history | edited | Juho | CC BY-SA 3.0 |
added 82 characters in body
|
| Aug 10, 2013 at 4:26 | history | edited | Joey Eremondi | CC BY-SA 3.0 |
Fixed half-sentence, clarified that don't need all languages binary
|
| Aug 8, 2013 at 6:16 | comment | added | Joey Eremondi | Please feel free to edit this answer as you see fit. | |
| Aug 8, 2013 at 6:10 | history | answered | Joey Eremondi | CC BY-SA 3.0 |