Content deleted Content added
m →Translate German WP article?: signed my contributed talk |
Duckmather (talk | contribs) rate as mid for math |
||
| (82 intermediate revisions by 42 users not shown) | |||
Line 1:
{{Skip to talk}}
{{Talk header}}
{{Article history|action1=RBP
|action1date=12:29, 19 January 2004
|action1link=
|action1result=kept
|action1oldid=2615306
Line 8 ⟶ 9:
|action2=FAR
|action2date=05:10, 11 Aug 2004
|action2link=Wikipedia:Featured article
|action2result=demoted
|action2oldid=5347739
Line 19 ⟶ 20:
|currentstatus=FFA
}}
{{WikiProject banner shell|class=B|vital=yes|1=
{{WikiProject Computer science
{{WikiProject Systems
{{WikiProject Mathematics|importance=mid}}
{{WikiProject Computing|importance=Mid}}
}}
==older entries==
I wonder where would be a good place to mention that we know some problems not in '''P''', for instance [[:Presburger arithmetic|Presburger arithmetic]]. --AxelBoldt
Line 55 ⟶ 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 93 ⟶ 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)
The article is beginning to look a lot better now that [[User:Hermel|Hermel]] has begun translating from the German article. I think this image from the German Wikipedia is excellent: [[de:Datei:Theoretische-informatik.svg|Relationship between complexity theory, formal languages and computability theory]]. If someone who speaks German also agrees that this would make a great addition to the English WP, please go ahead and translate it. (Since it's an SVG, this is really easy. Just open the file in a text editor and replace the German names with English names.) --[[User:RobinK|Robin]] ([[User talk:RobinK|talk]]) 02:11, 28 September 2009 (UTC)
== [[Wikipedia:Good articles|Good Article]] [[Wikipedia:Good articles/Nominations|nomination]] has failed ==
Line 153 ⟶ 149:
== What machine model? ==
What kind of machine is used to measure the number of steps or amount of memory required to solve a problem? A [[Random access stored program machine|RASP machine]]? I don't think it's a [[Turing machine]]. --[[User:
:The definitions of major classes are explicitly designed to be robust against "reasonable" changes in the definition of the underlying abstract machine. In typical presentations various types of Turing machines are used but it doesn't matter - RAM models, cache-oblivious models, pretty much everything works fine. That's why we discuss P and not, say, DTIME(n<sup>3</sup>). [[User:Dcoetzee|Dcoetzee]] 20:20, 18 December 2007 (UTC)
Line 196 ⟶ 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 221 ⟶ 220:
That would have been big news - it definitely isn't right so far.
But as a related question - in the section on P=NP, why is finding proofs of theorems in pure mathematics listed as something that could be done more efficiently if P=NP? By
[[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 253 ⟶ 254:
Kolmogorov Complexity (length of generating program for given data), rather than run time, is what many if not most people would mean by 'Computational Complexity', and this article should refer to it early on with a reference to its Wikipedia article. Other than that, I'm not sure that the material covered in the article is actually a 'subject' per se. P = NP is a legitimate subject: so are algorithmic design, cryptography, etc. The mere design of a notation about how long something takes to run, isn't much of a subject. The little o and big O notations, for instance, have many other uses in math unrelated to algorithm runnning time: I hope they have a separate article. <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/63.229.11.118|63.229.11.118]] ([[User talk:63.229.11.118|talk]]) 04:55, 18 June 2009 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->
:I strongly disagree. As I said a few lines above: Compare the recent books by Arora and Safra: "Computational Complexity: A Modern Approach" ([http://www.cs.princeton.edu/theory/index.php/Compbook/Draft draft available online]) and by Goldreich: "Computational Complexity: A conceptual perspective" ([http://www.wisdom.weizmann.ac.il/~oded/cc-book.html drafts of some chapters available online]). It IS indeed a subject on its own, and is as such different from Kolmogorov complexity. [[User:Hermel|Hermel]] ([[User talk:Hermel|talk]]) 18:19, 21 June 2009 (UTC)
:Yes, I also disagree that "many or most people" would think computational complexity is Kolmogorov complexity. --[[User:Doradus|Doradus]] ([[User talk:P3d0|talk]]) 20:00, 14 October 2009 (UTC)
== List of complexity theorists ==
I removed this text from the article:
{{Prose|1=paragraph|date=August 2009}}
<blockquote>
The field was subsequently expanded by many researchers, including:
<--
This is NOT a "Hall of Fame". All people with wikipedia articles are notable.
Please add only names which are described as "groundlayers" by the peers,
with citations and summary of major contributions
-->
* [[Manuel Blum]]
* [[Allan Borodin]]
* [[Stephen Cook]]
* [[Michael Fellows]]
* [[Michael R. Garey]]
* [[Oded Goldreich]]
* [[Juris Hartmanis]]
* [[David S. Johnson]]
* [[Richard Karp]]
* [[Marek Karpinski]]
* [[Donald Knuth]]
* [[Leonid Levin]]
* [[Christos H. Papadimitriou]]
* [[Alexander Razborov]]
* [[Richard Stearns (computer scientist)|Richard Stearns]]
* [[Leslie Valiant]]
* [[Andrew Yao]]
</blockquote>
We need to establish some criteria for inclusion, or not have such a list at all. I haven't seen such lists on other articles either. The article on [[physics]] doesn't have a list of notable physicists like Newton, Einstein, etc. --[[User:RobinK|Robin]] ([[User talk:RobinK|talk]]) 18:26, 14 October 2009 (UTC)
== Image relating complexity theory and other fields ==
This image shows the relationship between [[computability theory]], complexity theory and [[formal language theory]]. I had originally put it in the lead section, but it takes too much space and makes the lead look bad. Any suggestions on where this might go (including new sections which haven't been written yet)? --[[User:RobinK|Robin]] ([[User talk:RobinK|talk]]) 13:13, 26 October 2009 (UTC)
: Could we perhaps have a hyperlinked version of the image in the "See also" section (so that we would have an illustrated "see also" section instead of the usual boring list of links)? Or perhaps we could replace the navigation box {{tl|ComplexityClasses}} with this (at the very bottom of the page)? — [[User:Miym|Miym]] ([[User talk:Miym|talk]]) 00:12, 4 November 2009 (UTC)
:: I would prefer putting it in the "see also" section. Another idea I had was to put this in the history section, with a subsection devoted to how complexity theory is historically related to computability theory and formal language theory. --[[User:RobinK|Robin]] ([[User talk:RobinK|talk]]) 01:13, 4 November 2009 (UTC)
[[Image:Theoretical computer science.svg|thumb|800px|center|Relationship between [[computability theory]], complexity theory and [[formal language theory]].]]
== Improving this article ==
Someone watching this article might have noticed that I've been editing it for the last few weeks trying to improve it. I'd really like to hear suggestions / comments / criticisms to improve it further. Of course, you can be [[WP:BOLD]] and improve the article yourself, but if you don't have the time or inclination to do so, I would appreciate any comments you have to improve the article. Any topics you feel that must be mentioned in the article and haven't been covered adequately? Any topics covered too much in detail? --[[User:RobinK|Robin]] ([[User talk:RobinK|talk]]) 22:45, 3 November 2009 (UTC)
:One of my concerns is the illustration in [[Computational complexity theory#Theory vs. practice]]. There seems to be some serious confusion regarding how to read the plot and what it means. Could we simply remove it, as well as all discussion that refers to it? — [[User:Miym|Miym]] ([[User talk:Miym|talk]]) 23:42, 3 November 2009 (UTC)
::Yes, sure. I'm not a fan of that myself. The whole section on intractability is a bit sketchy, but I'm not too sure how to present it properly. It feels like a "criticisms of complexity theory" section, but presented badly. There might be interesting things to mention in such a section, like the fact that SAT solvers in reality to do handle largish instances (10000+ variables) in practice, and that even though problems might be hard to solve exactly, they might be easy to approximate. I'll see if I can get more information on this and write some stuff up. --[[User:RobinK|Robin]] ([[User talk:RobinK|talk]]) 23:56, 3 November 2009 (UTC)
== Table or list? ==
Which one of the following seems better for presenting information?
{| class="wikitable"
|-
! Complexity class
! Type of problem
! Model of computation
! Bounded resource
! Bound for the resource
|-
| [[DTIME]](''f''(''n''))
| Decision problem
| Deterministic Turing machine
| Time
| ''f''(''n'')
|-
| [[P (complexity)|P]]
| Decision problem
| Deterministic Turing machine
| Time
| polynomial
|-
| [[EXPTIME]]
| Decision problem
| Deterministic Turing machine
| Time
| exponential
|-
| [[NTIME]](''f''(''n''))
| Decision problem
| Non-deterministic Turing machine
| Time
| ''f''(''n'')
|-
| [[NP (complexity)|NP]]
| Decision problem
| Non-deterministic Turing machine
| Time
| polynomial
|-
| [[NEXPTIME]]
| Decision problem
| Non-deterministic Turing machine
| Time
| exponential
|-
|}
OR a list, like this:
* [[DTIME]](f(n)): Decision problems solvable by a deterministic Turing machine within time ''f''(''n'').
* [[P (complexity)|P]]: Decision problems solvable by a deterministic Turing machine within time polynomial in the input size.
* [[EXPTIME]]: Decision problems solvable by a deterministic Turing machine within time exponential in the input size.
* [[NTIME]](f(n)): Decision problems solvable by a nondeterministic Turing machine within time ''f''(''n'').
* [[NP (complexity)|NP]]: Decision problems solvable by a nondeterministic Turing machine within time polynomial in the input size.
* [[NEXPTIME]]: Decision problems solvable by a nondeterministic Turing machine within time exponential in the input size.
[[User:RobinK|Robin]] ([[User talk:RobinK|talk]]) 15:57, 19 November 2009 (UTC)
The table looks better, but perhaps we could have fewer columns:
{| class="wikitable"
|-
! Complexity class
! Type of problem
! Model of computation
! Resource constraint
|-
| [[DTIME]](''f''(''n''))
| Decision problem
| Deterministic Turing machine
| Time ''f''(''n'')
|-
| [[P (complexity)|P]]
| Decision problem
| Deterministic Turing machine
| Polynomial time
|-
| [[EXPTIME]]
| Decision problem
| Deterministic Turing machine
| Exponential time
|-
| [[NTIME]](''f''(''n''))
| Decision problem
| Non-deterministic Turing machine
| Time ''f''(''n'')
|-
| [[NP (complexity)|NP]]
| Decision problem
| Non-deterministic Turing machine
| Polynomial time
|-
| [[NEXPTIME]]
| Decision problem
| Non-deterministic Turing machine
| Exponential time
|-
|}
— [[User:Miym|Miym]] ([[User talk:Miym|talk]]) 13:33, 21 November 2009 (UTC)
:Alright, agreed. Maybe if we end up listing only decision problems, that column can be taken out too. --[[User:RobinK|Robin]] ([[User talk:RobinK|talk]]) 14:33, 21 November 2009 (UTC)
By the way, while "polynomial time" is fairly obvious, "exponential time" isn't. If someone new to the topic had to guess what it means, it might be easy to think something like [[E (complexity)]] instead of something like [[EXPTIME]]. To add to the confusion, we have a (somewhat strange) article [[Exponential time]] that strengthens the false impression. Hence we might consider something more explicit like this:
{| class="wikitable"
|-
! Complexity class
! Type of problem
! Model of computation
! Resource constraint
|-
| [[DTIME]](''f''(''n''))
| Decision problem
| Deterministic Turing machine
| Time ''f''(''n'')
|-
| [[P (complexity)|P]]
| Decision problem
| Deterministic Turing machine
| Time poly(''n''), i.e. polynomial
|-
| [[EXPTIME]]
| Decision problem
| Deterministic Turing machine
| Time 2<sup>poly(''n'')</sup>, i.e. exponential
|-
|}
— [[User:Miym|Miym]] ([[User talk:Miym|talk]]) 15:30, 21 November 2009 (UTC)
:OK, sounds reasonable. --[[User:RobinK|Robin]] ([[User talk:RobinK|talk]]) 15:38, 21 November 2009 (UTC)
== One says ==
It is not good form to use the phrase, "one tries to keep"
"Even though some proofs of complexity-theoretic theorems regularly assume some concrete choice of input encoding, one tries to keep the discussion abstract enough to be independent of the choice of encoding. This can be achieved by ensuring that different representations can be transformed into each other efficiently.one tries to keep the discussion abstract enough to be independent of the choice of encoding. This can be achieved by ensuring that different representations can be transformed into each other efficiently."
Better might be,
"When considering complexity the problem should be presented in an abstract form, so that each concrete representation may be transformed into the same problem." <small><span class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Thepigdog|Thepigdog]] ([[User talk:Thepigdog|talk]] • [[Special:Contributions/Thepigdog|contribs]]) 08:06, 12 October 2011 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->
== 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; color:DarkGreen;">Orange Suede Sofa</span>]] ([[User talk:Orange Suede Sofa|talk]]) 07:11, 23 October 2012 (UTC)
== Computational complexity ==
[[Computational_complexity_theory#Upper_and_lower_bounds_on_the_complexity_of_problems|Upper_and_lower_bounds_on_the_complexity_of_problems]], begin with stating that "''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. The complexity of an algorithm is usually taken to be its worst-case complexity''" Shouldn't it be the maximum amount of time?--[[User:Natematic|Natematic]] ([[User talk:Natematic|talk]]) 17:55, 18 November 2012 (UTC)
: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-->
| |||