Content deleted Content added
Added a comment concerning Gödel's Incompleteness Theorem |
Duckmather (talk | contribs) rate as mid for math |
||
| (26 intermediate revisions by 16 users not shown) | |||
Line 1:
{{Skip to talk}}
{{Talk header}}
{{WikiProject Computer science|class=c|importance=Top}}▼
{{WikiProject Systems|class=c|importance=mid}}▼
{{WikiProject Computing|class=c|importance=Mid}}}}▼
▲{{ArticleHistory|action1=RBP
|action1date=12:29, 19 January 2004
|action1link=
|action1result=kept
|action1oldid=2615306
Line 15 ⟶ 9:
|action2=FAR
|action2date=05:10, 11 Aug 2004
|action2link=Wikipedia:Featured article
|action2result=demoted
|action2oldid=5347739
Line 26 ⟶ 20:
|currentstatus=FFA
}}
{{WikiProject banner shell|class=B|vital=yes|1=
{{
}}
==older entries==
Line 51 ⟶ 49:
*Support removal. The weird thing is that I don't even see this article on [[Wikipedia:Featured article candidates/Featured log]]. When the WP:FA page was new, a lot of people added articles themselves, as the candidate process was kind of unclear. - [[User:DropDeadGorgias|DropDeadGorgias]] [[User_talk:DropDeadGorgias|(talk)]] 17:02, Jul 26, 2004 (UTC)
* Support removal; this is nowhere near comprehensive. [[User:Matt Crypto|— Matt]] 17:32, 27 Jul 2004 (UTC)
* Remove posthaste. The "notable researchers" section is particularly disturbing; you can hardly do such a list justice, certainly not with only a dozen names. [[User:Sj|+sj]][[User Talk:Sj|<
=="Invitation" to work on questionable off-topic article==
Line 194 ⟶ 192:
::::Thank you very much! Now, only ''asymptotic complexity'' has to be explained (please! :). --[[User:Abdull|Abdull]] ([[User talk:Abdull|talk]]) 14:47, 30 July 2008 (UTC)
:::::That's just a bad redirect. :-) Asymptotic complexity is nothing but complexity metrics described using asymptotic notation. For now I redirected it to [[Big O notation]]. [[User:Dcoetzee|Dcoetzee]] 17:32, 31 July 2008 (UTC)
:::::: [[Asymptotic complexity]] now redirects here again. This article is good, but it doesn't contain the word "asymptotic" at all. The [[Big O notation]] might be a better redirect. [[User:Werediver|Werediver]] ([[User talk:Werediver|talk]]) 14:44, 9 June 2021 (UTC)
::::::: Now, {{noredirect|Asymptotic complexity}} is a redirect to [[Computational complexity#Asymptotic complexity]]. [[User:D.Lazard|D.Lazard]] ([[User talk:D.Lazard|talk]]) 14:58, 9 June 2021 (UTC)
::::::: As [[Context of computational complexity]] is a content fork of [[Computational complexity]], and is a unplausible research term, I have redirected it to [[Computational complexity]]. Also, I have redirected {{noredirect|Bit complexity}} to the same article, which I have edited for adding details to the definition of ''bit complexity''. [[User:D.Lazard|D.Lazard]] ([[User talk:D.Lazard|talk]]) 18:11, 9 June 2021 (UTC)
== worst-case analysis ==
Line 466 ⟶ 467:
== Supertasks ==
The [[supertask]] article has a note at the top stating "''For the computer science term, see [[Computational complexity theory]].''" Is that note accurate? Taken literally, it is not, as the term ''supertask'' cannot actually be found anywhere in this article. But I ask here because readers of this talk page may know if that characterization is somehow appropriate. Regards, [[User:Orange Suede Sofa|<span style="font-variant:small-caps
== Computational complexity ==
Line 492 ⟶ 493:
::You are misquoting the book you cite. It says that a NTM M can be restricted to a DTM M1 (by choosing one specific successor state) but it does not say that M1 computes the same function as M (which is how I understand your "works as"). Using the same search terms as you did, [http://books.google.co.uk/books?id=YnLmsHAtvYEC&pg=PA72&dq=%22ntm+working+as+dtm%22&hl=en&sa=X&ei=8u1tU8vlJoPlOsiRgfAD&redir_esc=y#v=onepage&q=%22ntm%20working%20as%20dtm%22&f=false here] we find "every DTM, by definition, is a special NTM" and [http://books.google.co.uk/books?id=n2jCfkPDcIsC&pg=PA31&dq=%22ntm+working+as+dtm%22&hl=en&sa=X&ei=8u1tU8vlJoPlOsiRgfAD&redir_esc=y#v=onepage&q&f=false here] "an NTM can be simulated by a DTM, i.e. every NTM has an equivalent DTM". I would say that an NTM is a TM in which at each point there is a number of successor states, and a DTM is a TM in which at each point there is one or none. So every DTM is an NTM, but some NTMs are not DTMs, namely those NTMs in which some states have more than one successor. The concept of DTM is a restriction of the concept of NTM, and the class of DTMs is a subset of the class of NTMs. The statement that any given NTM may be "restricted" to a DTM is not the same as saying that the concept of NTM is a restriction of the concept of DTM. [[User:Deltahedron|Deltahedron]] ([[User talk:Deltahedron|talk]]) 09:23, 10 May 2014 (UTC)
::: Well, I admit, I was wrong. Thank you for the explanation, and I'll use it as a motivation to learn to read better. — [[User:Dsimic|Dsimic]] ([[User talk:Dsimic#nobold|talk]] | [[Special:Contributions/Dsimic|contribs]]) 09:50, 10 May 2014 (UTC)
== Difference between "decision problems" and "function problems" ==
We read
<blockquote>It is tempting to think that the notion of function problems is much richer than the notion of decision problems. However, this is not really the case, since function problems can be recast as decision problems. For example, the multiplication of two integers can be expressed as the set of triples (a, b, c) such that the relation a × b = c holds. Deciding whether a given triple is a member of this set corresponds to solving the problem of multiplying two numbers.</blockquote>
This does not sound correct at all. Consider the predicate "pfactors([f0...fn],composite)", which is TRUE if [f0...fn] are the prime factors of the composite. Evidently, the decision problem "pfactors([f0...fn],composite)" is MUCH easier than the function problem "pfactors([F0...Fn],composite)" where F0 ... Fn are variables to be determined and even n is unknown. Additionally, in the given example, there may be ways to check whether a x b = c holds much more easily than actually computing a x b (we just need to "fail fast" after all). Additionally, the text says "function problems can be recast as decision problems" and then proceeds to given an example where a decision problem is recast as a function problem...
See also for example FNP vs. NP : https://complexityzoo.uwaterloo.ca/Complexity_Zoo:F#fnp (which I don't quite understand yet) [[User:There is a T101 in your kitchen|There is a T101 in your kitchen]] ([[User talk:There is a T101 in your kitchen|talk]]) 21:46, 8 October 2016 (UTC)
== External links modified ==
Hello fellow Wikipedians,
I have just modified one external link on [[Computational complexity theory]]. Please take a moment to review [[special:diff/820394022|my edit]]. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit [[User:Cyberpower678/FaQs#InternetArchiveBot|this simple FaQ]] for additional information. I made the following changes:
*Added archive https://web.archive.org/web/20101212035424/http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf to http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf
When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.
{{sourcecheck|checked=false|needhelp=}}
Cheers.—[[User:InternetArchiveBot|'''<span style="color:darkgrey;font-family:monospace">InternetArchiveBot</span>''']] <span style="color:green;font-family:Rockwell">([[User talk:InternetArchiveBot|Report bug]])</span> 13:50, 14 January 2018 (UTC)
==Input size==
I will undo the change 03:53, 19 May 2018 of 69.172.150.202. The user removed the bold text from the following paragraph.
{{quote|Thus the time required to solve a problem (or the space required, or any measure of complexity) is calculated as a function of '''the size of the instance. This is usually taken to be''' the size of the input '''in bits'''.}}
So the text was changed to
{{quote|Thus the time required to solve a problem (or the space required, or any measure of complexity) is calculated as a function of the size of the input.}}
The user added the followind comment to justify the edit:
{{quote|Measuring the size of the instance "in bits" is a misleading and unfounded generalization. The same paragraph goes on to give an example where the size is measured on the number of vertices (not the number of bits needed to represent the number of vertices).}}
The original text was brought to the attention of the user by me in a discussion of a [https://codereview.stackexchange.com/a/194617/12462 post] at codereview.stackexchange.com. Ihe user than told me:
{{quote|Nobody thinks that way. That was a misleading and uncited statement on Wikipedia. Now it doesn't say that anymore.}}(https://codereview.stackexchange.com/questions/194611/hackerrank-challenge-apple-and-orange#comment374709_194617)
and changed this wiki text as described above.
The reason given for the change is nonsense.
James Aspnes says in [http://www.cs.yale.edu/homes/aspnes/classes/468/notes.pdf Notes on Computational Complexity Theory, CPSC 468/568: Spring 2017, page 7]
{{quote|The time complexity of an execution is the number of steps until the machine halts. Typically we will try to bound the time complexity as a
function of the size n of the input, defined as the number of cells occupied by the input, excluding the infinite number of blanks that surround it.}}
So the size of the input depends on the alphabet used to encode the input of the turing machine but is proportional to the number of bits of the input numbers
Also the [https://plato.stanford.edu/entries/computational-complexity/#BasCon Stanford Encyclopedia of Philosophy] says
{{quote|For each problem X, it is also assumed that an appropriate notion of problem size is defined for its instances. Formally, this is a function |⋅|:X→N chosen so that the efficiency of a decision algorithm for X will varying uniformly in |x|. As we have seen, if X⊆N, it is standard to take |n|=log2(n) i.e. the number of digits (or length) of the binary numeral ┌n┐ representing n}}
These are two citations for the original statement.
[[User:Miracle173|Miracle173]] ([[User talk:Miracle173|talk]]) 22:01, 21 May 2018 (UTC)
: I agree with your addition. Input size is conventionally measured by the number of bits in the input. --[[User:RobinK|Robin]] ([[User talk:RobinK|talk]]) 06:29, 22 May 2018 (UTC)
== The quantitative answer? ==
Under Computational problems -> Problem instances, it says quantitative answer, but all I see is a yes/no answer, where is the quantity in the answer?
I think quantitative should be removed, what do you guys think? <!-- Template:Unsigned --><small class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Shalevku|Shalevku]] ([[User talk:Shalevku#top|talk]] • [[Special:Contributions/Shalevku|contribs]]) 16:31, 9 January 2020 (UTC)</small> <!--Autosigned by SineBot-->
| |||