Talk:Time complexity: Difference between revisions
no reason for such aggressive archiving |
Tag: Reverted |
||
| Line 1: | Line 1: | ||
{{Talk header}} |
{{Talk header}} |
||
{{User:MiszaBot/config |
{{User:MiszaBot/config |
||
| algo = old( |
| algo = old(90d) |
||
| archive = Talk:Time complexity/Archive %(counter)d |
| archive = Talk:Time complexity/Archive %(counter)d |
||
| counter = 1 |
| counter = 1 |
||
| maxarchivesize = |
| maxarchivesize = 125K |
||
| archiveheader = {{Automatic archive navigator}} |
| archiveheader = {{Automatic archive navigator}} |
||
| minthreadstoarchive = 2 |
| minthreadstoarchive = 2 |
||
| minthreadsleft = 5 |
| minthreadsleft = 5 |
||
}}{{Archives|bot=Lowercase sigmabot III|age=90}} |
|||
}} |
|||
<!-- Template:Setup auto archiving --> |
<!-- Template:Setup auto archiving --> |
||
{{maths rating|class=B|priority=High|field=discrete}} |
{{maths rating|class=B|priority=High|field=discrete}} |
||
Revision as of 12:18, 5 July 2023
| This is the talk page for discussing improvements to the Time complexity article. This is not a forum for general discussion of the article's subject. |
Article policies
|
| Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL |
Archives: 1Auto-archiving period: 90 days  |
|
|
|
This page has archives. Sections older than 90 days may be automatically archived by Lowercase sigmabot III when more than 5 sections are present. |
 | Mathematics B‑class High‑priority | |||||||||
| ||||||||||
 | Computer science B‑class High‑importance | ||||||||||||||||
| |||||||||||||||||
 | The contents of the Linear time page were merged into Time complexity. For the contribution history and old versions of the redirected page, please see its history. |
Mistake
There is a mistake in description of Quasi-polynomial time: 3sat it is not NP hard problem but NP complete, we have a polynomial verification for the solution of the problem.
- NPC is the intersection of NP and NPH, so all NPC problems are NPH. See NP-hardness to learn more. (I did fix an unrelated error, though.) 2620:0:1A10:7816:4CE9:BD3B:BE35:4850 (talk) 22:30, 15 December 2021 (UTC)
It wasn't an error, though. Polynomial and sublinear time algorithms are still also quasipolynomial time algorithms. Your edit introduced an error by saying that they are not. —David Eppstein (talk) 01:07, 16 December 2021 (UTC)
APR-CL time complexity
In the "Superpolynomial time" section the APR algorithm is given as an example for algorithm with time complexity of , but in the article about the algorithm the complexity mentioned is . This might be caused if the complexity in the other article uses to represent the unary length of the number instead of binary but I don't think that is the case. —YotamEdit (talk) 18:51, 7 July 2021 (UTC)
P and NP Problems.
My question is: If N^3 is p type problem, and to solve this it's take almost 3 hours, Then now I want to ask what is value of N^3. 2402:8100:2652:B42D:61B8:A047:8958:1CFB (talk) 07:51, 29 March 2022 (UTC)
What is T(n)?
In the section on 'Constant Time', the function T(n) first shows up without any previous explanation. There should be a section differentiating b/w Time Complexity and 'Order/degree of Time Complexity'. — Preceding unsigned comment added by Granzer92 (talk • contribs) 07:33, 26 May 2022 (UTC)
Article too long
This article is too long. I suggest splitting it into separate articles. At the very least, polynomial time should have its own article. Other important complexity classes should have their own articles, too. 2601:547:B05:ECD:ED93:4837:4D47:671 (talk) 06:29, 31 January 2023 (UTC)
- At 33kB "readable prose size" we are at the point where WP:TOOBIG says "Length alone does not justify division". But some of these time classes may well work better as standalone topics. The bigger problem is that many sections are completely unsourced. With sources, they could stand up a lot better to expansion and splitting off into separate articles. Without sources, we cannot make articles out of them. —David Eppstein (talk) 07:58, 31 January 2023 (UTC)