Talk:Computational complexity theory: Difference between revisions

Revision as of 04:48, 22 May 2018

Latest revision as of 19:46, 4 June 2025

(18 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 549 ⟶ 550:

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 {|}&#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-->