Content deleted Content added
Deltahedron (talk | contribs) the maximum time isn't a useful concept -- although it can be thought-provoking, see Bogosort for example |
Duckmather (talk | contribs) rate as mid for math |
||
| (44 intermediate revisions by 26 users not shown) | |||
Line 1:
{{
{{Talk header}}
{{Article history|action1=RBP
|action1date=12:29, 19 January 2004
|action1link=
|action1result=kept
|action1oldid=2615306
Line 9:
|action2=FAR
|action2date=05:10, 11 Aug 2004
|action2link=Wikipedia:Featured article
|action2result=demoted
|action2oldid=5347739
Line 20:
|currentstatus=FFA
}}
{{WikiProject banner shell|class=B|vital=yes|1=
{{WikiProject Computer science
{{WikiProject Systems
{{WikiProject Mathematics|importance=mid}}
{{WikiProject Computing
}} ==older entries==
Line 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 87:
:While I know we generally frown upon automated translation services, this link[http://64.233.179.104/translate_c?hl=en&ie=UTF-8&oe=UTF-8&langpair=de%7Cen&u=http://de.wikipedia.org/wiki/Komplexit%25C3%25A4tstheorie&prev=/language_tools] will translate the German page fairly well. Because of the way the links are set up, if you click on a wikilink, you will be sent to a translated version of the target page. --[[User:Braindrain0000|Carl]] <sup>([[User_talk:braindrain0000|talk]]|[[Special:Contributions/Braindrain0000|contribs]])</sup> 03:57, 15 September 2006 (UTC)
::I just translated some portions of the German article. I omitted large chunks; nevertheless I think that the boilerplate should go here:
{{Translated page|de|Komplexitätstheorie}}
::--[[User:Hermel|Hermel]] ([[User talk:Hermel|talk]]) 12:27, 26 September 2009 (UTC)
Line 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 220 ⟶ 223:
[[User:Easwaran|Easwaran]] ([[User talk:Easwaran|talk]]) 12:12, 14 September 2009 (UTC)
:This is not what Gödel's Incompleteness Theorem is about. It just says that for a "sufficiently strong" logic+theory, there are statements that must be labeled "true" but cannot be proved within that system (but possibly can be proved via another meta-system) (Also, Gödels canonical example of a self-referential statement has a bad smell as frankly it seems to me he intermixes truth values from different levels with scant justification, but that's another topic). If you stay in First-Order Logic + Some Theory (e.g. Arithmetic), it intuitively seems correct to say that if "problems that are easy to check are easy to solve" (i.e. P=NP) then "finding a proof" of a provable statement should be about as easy as "checking a proof" of a provable statement (which is known easy). This needs to be made more precise of course. [[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:22, 8 October 2016 (UTC)
== Graph Theory ==
Line 462 ⟶ 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 468 ⟶ 473:
:The complexity is the minimum time required, the running time of the most efficient algorithm. It is possible to spend as much time as you like on solving a problem, so the maximum time isn't a useful concept -- although it can be thought-provoking, see [[Bogosort]] for example. The worst case is the maximum of those minimum times, in other words the greatest length of time you can be compelled to spend even doing it as quickly as possible. [[User:Deltahedron|Deltahedron]] ([[User talk:Deltahedron|talk]]) 18:26, 18 November 2012 (UTC)
::I agree with you. My point is: if you say "''one is interested in proving upper and lower bounds on the '''minimum''' amount of time required by the most efficient algorithm solving a given problem''", I get that considering the most efficient algorithm, you say that the complexity is the time it spend in its best-case. In other words, it seems to me that the best-fitting formalization for that proposition above is <math>\min_{x\in X} \{time(T(x))\}</math> where <math>X</math> is the set of possible input and <math>T</math> is the most efficient algorithm. <small><span class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Natematic|Natematic]] ([[User talk:Natematic|talk]] • [[Special:Contributions/Natematic|contribs]]) 19:25, 18 November 2012 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->
== Dodgy Map ==
Why does the map showing the shortest route to visit 15 german cities, only actually visit 14 of them ?[[User:Eregli bob|Eregli bob]] ([[User talk:Eregli bob|talk]]) 11:19, 11 May 2013 (UTC)
:You're right. Other sources also claim that this route covers 15 cities. For example, see [http://www.gizmag.com/d-wave-quantum-computer-supercomputer-ranking/27476/pictures#2]. --[[User:RobinK|Robin]] ([[User talk:RobinK|talk]]) 19:14, 14 May 2013 (UTC)
::The answer to the mystery was one mouse click away. Instead of doing [[WP:NOR|original research]] :-) The image description says that [[Dortmund]] is not labelled in the map (I guess because, as you can see it yourself, there is simply no place for it on the map, despite (or because of) being the largest city in Ruhr area :-) [[User:Staszek Lem|Staszek Lem]] ([[User talk:Staszek Lem|talk]]) 02:16, 12 May 2014 (UTC)
== Reversal ==
An editor is reversing "deterministic" and "non-deterministic" in the following sentence:
<blockquote>Since deterministic Turing machines are special non-deterministic Turing machines, it is easily observed that each problem in P is also member of the class NP.</blockquote>
As it would make no sense that way, could someone please try to explain to {{u|Dsimic}} why it makes no sense? I don't think I can do it. — [[User:Arthur Rubin|Arthur Rubin]] [[User talk:Arthur Rubin|(talk)]] 05:02, 10 May 2014 (UTC)
: Hello there! Well, let's face it, you haven't even tried to explain it through {{Diff|Computational complexity theory|607300453|607293997|your edit summaries}}, while at the same time I'm far away from being a clueless monkey which "needs to learn to read" as {{Diff|Computational complexity theory|607867082|607301091|you've described it}}. Of course, I can be wrong and there shouldn't be a big problem with that if we spend some time and energy discussing the issue{{snd}} nobody knows everything, if you agree.
: Now, back to the subject after I've thought about it again. By [[Generalization|definition]], concept {{mvar|A}} is a ''[[special case]]'' or ''specialization'' of concept {{mvar|B}} precisely if and only if every instance of concept {{mvar|A}} is also an instance of concept {{mvar|B}}, but there are instances of concept {{mvar|B}} which are not instances of concept {{mvar|A}}. Non-deterministic Turing machines (NTMs) [http://books.google.com/books?id=oG6lRcwRqCUC&pg=PA14&lpg=PA14&dq=ntm+working+as+dtm&source=bl&ots=yknFtR37TK&sig=ssLZaOiAUIftTgphRdTxXf7LHok&hl=en&sa=X&ei=fultU_D4A4eg7Abp_4DYBw&redir_esc=y#v=onepage&q=ntm%20working%20as%20dtm&f=false can be restricted] so they work as deterministic Turing machines (DTMs), while an ''ordinary'' DTM (not its multi-tape variations or anything else) can't work as an NTM. Thus, by the definition, NTMs are a special case of DTMs{{snd}} and that's the way {{Diff|Computational complexity theory|607300863|607300453|I've edited}} the article.
: Thoughts? If I'm wrong, please point out where's that the case, so the monkey can learn to read better. :) — [[User:Dsimic|Dsimic]] ([[User talk:Dsimic#nobold|talk]] | [[Special:Contributions/Dsimic|contribs]]) 09:10, 10 May 2014 (UTC)
::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-->
| |||