Talk:Computational complexity theory: Difference between revisions

Revision as of 22:01, 21 May 2018

Latest revision as of 19:46, 4 June 2025

(21 intermediate revisions by 13 users not shown)

Line 1:

{{Skip to talk}}

{{Talk header}}

{{ArticleHistoryArticle history|action1=RBP

{{Vital article|level=4|topic=Mathematics|class=C}}

{{WikiProjectBannerShell|1=

{{WikiProject Computer science|class=c|importance=Top}}

{{WikiProject Systems|class=c|importance=mid}}

{{maths rating|frequentlyviewed=yes|class=B|importance=high |field=discrete |historical= }}

{{WikiProject Computing|class=c|importance=Mid}}}}

{{ArticleHistory|action1=RBP

|action1date=12:29, 19 January 2004

|action1link=Wikipedia:Archive/Refreshing brilliant prose - Science

Line 26 ⟶ 20:

|currentstatus=FFA

}}

{{WikiProject banner shell|class=B|vital=yes|1=

{{WP1.0|v0.7=pass|class=c|category=Math|small=yesWikiProject Computer science|importance=midTop}}

{{WikiProject Computer science|class=cSystems|importance=TopMid}}

{{WikiProject Systems|class=cMathematics|importance=mid}}

{{WikiProject Computing|class=c|importance=Mid}}}}

}}

==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|<fontspan colorstyle="color:#ff6996;">+</fontspan>]] 05:10, 11 Aug 2004 (UTC)

=="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">[[User:Orange Suede Sofa|<font; color=":DarkGreen;">Orange Suede Sofa</fontspan>]]</span> ([[User talk:Orange Suede Sofa|talk]]) 07:11, 23 October 2012 (UTC)

== Computational complexity ==

Line 522 ⟶ 523:

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}(http://www.cs.yale.edu/homes/aspnes/classes/468/notes.pdf)]

* {{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.}}

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 [Stanford Encyclopedia of Philosophy](https://plato.stanford.edu/entries/computational-complexity/#BasCon) Stanford Encyclopedia of Philosophy] says

* 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

* {{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 |&#124;⋅|&#124;:X→N chosen so that the efficiency of a decision algorithm for X will varying uniformly in |&#124;x|&#124;. As we have seen, if X⊆N, it is standard to take |&#124;n|=&#124;&#61;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">—&nbsp;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-->