[HN Gopher] Complexity theory's 50-year journey to the limits of...
___________________________________________________________________
Complexity theory's 50-year journey to the limits of knowledge
Author : nsoonhui
Score : 39 points
Date : 2023-08-18 05:07 UTC (17 hours ago)
(HTM) web link (www.quantamagazine.org)
(TXT) w3m dump (www.quantamagazine.org)
| PartiallyTyped wrote:
| Is there a missed connection between entropy and circuit
| complexity? It looks like one might be able to draw some
| parallels between the two.
|
| Other thoughts; it's interesting that PvsNP is essentially about
| the lengths of proofs, and thus it is the task of deciding in
| poly time whether you can decide all decidable problems whose
| proofs are polynomial to their encoding.
| PartiallyTyped wrote:
| This is easily one of the most well written articles published by
| quanta. Truly a pleasure to read.
| xmonkee wrote:
| Yeah, a lot of love went into this. Could be made into a book,
| i would buy.
| guga42k wrote:
| nitpick: I wonder how TSP became NP complete. It would require
| to polynomial time algorithm to validate the solution. I doubt
| such algorithm does exist.
| bumbledraven wrote:
| > Suppose that P = NP. To prove it, researchers would need to
| find a fast algorithm for an NP-complete problem, which might be
| hiding in some obscure corner of that vast landscape.
|
| They wouldn't need to _find_ such an algorithm. They would just
| need to prove that such an algorithm _exists_.
| wddkcs wrote:
| Can you really separate the two? For something like NP-
| completeness, I'm having trouble conceptualizing how a proof
| for existence would not require demonstration.
| linkgoron wrote:
| An example for such a proof would be using the probabilistic
| method. However, even if we are ignoring some artificial
| problems, there are some "natural" problems that are known to
| be in P that we do not have algorithms for.
|
| https://en.wikipedia.org/wiki/Non-
| constructive_algorithm_exi...
|
| Also see:
|
| https://cs.stackexchange.com/questions/92087/are-there-
| any-p...
| fooker wrote:
| Yes, proofs don't have to be constructive.
|
| Consider proofs by contradiction, you could potentially show
| that if such an algorithm does not exist some important true
| statement would be rendered false.
| viscountchocula wrote:
| Sure. There is definitely a googolth digit of pi. Computing
| what the digit is, however, is not necessary to prove that
| such a digit exists.
| tetrazine wrote:
| This is an aside. But I twigged on a caption for one of the
| figures: "Every computational problem takes longer to solve as
| its input grows larger, but not all problems grow harder at the
| same rate."
|
| It's obvious from CS201 that this phrase is generally true and I
| have no pedantic objection to its inclusion in the article.
| However, I'm curious if this is strictly true or if we can find a
| (nontrivial) counterexample. Are there any algorithms that run
| faster as input grows? My first intuition is some kind of
| probabilistic question solved to a given correctness bound.
|
| Edit: it is trivial to construct an algorithm with this property.
| My precise question is whether any meaningful problems have
| optimal algorithms with this property.
___________________________________________________________________
(page generated 2023-08-18 23:00 UTC)