7 ms·
I have low hopes for P=NP. I really don’t see how you can solve for example the TSP exactly to guaranteed optimality without utilizing all of the useful availab
by whatever1 5y ago
I have low hopes for P=NP. I really don’t see how you can solve for example the TSP exactly to guaranteed optimality without utilizing all of the useful available information. Approximation approaches show that by discarding information you give up optimality guarantees.
There must be something in information theory to help with proving that to construct a solution to an NP hard problem you need at least that much information.
- sova 5y agoInformation and computation ("utilization of information") are not equivalent things. The solution is there, staring us right in the face, it's just our primitive methods of sequential operations on a silicon abacus are incapable of rendering a solution immediately. Infinitely parallellize operations, such as with a "quantum computer" and suddenly what is infeasible in one era becomes quite feasible in another. I don't think it's right to equate information theory and computing, because one is per-se data and its solubles/solutions while the other is step-wise sequential logic to infer some step-wise sequential fact.
- chowells 5y agoI think it's time someone had the talk with you: https://www.smbc-comics.com/comic/the-talk-3 https://www.smbc-comics.com/comic/the-talk-3 Quantum computing doesn't do what you think it does.
- oh_sigh 5y agoNot so coincidentally, Scott is the first person quoted in OP's article, as well as the co-author of that comic.
- thewakalix 5y ago“The Blog of Scott Aaronson If you take nothing else from this blog: quantum computers won't solve hard problems instantly by just trying all solutions in parallel.”
- sova 5y agoOnly a madman would try all possible "solutions."
- bobbylarrybobby 5y agoAlso, even if it did, that wouldn’t change the status of P=NP, which is a statement about problems computed by classical Turing machines
- sova 5y ago>a statement about problems computed by classical Turing machines Are we out of tape already?
- scottcodie 5y agoHe's just stating that there could be an equivalence class that could get us closer to P=NP and it doesn't have to be computable. The complexity class he mentions is `P^(NP[k])`, 'P With k NP Queries(for constant k)'.
- sova 5y agoRock n roll dude. Suggest that Tiger Woods can get a hole in one every time and people attack you as if you had questioned their fundamental religious beliefs. Ramanujan created an approximating function for pi in 1904 and nobody knows how it works. Packed with factorials to the gills. It's not like the digits of pi are a secret to be computed every time and to try and snag a spare computation cycle here and there -- they are what they are. And finding a pattern comes down not to the self-evident information, but to the method.
- bawolff 5y agoI'm pretty sure you're being downvoted because you're being incoherent, not because of anything you've suggested.
- bawolff 5y agoI have no idea how you could have possibly got that from anything Sova wrote. Nothing they wrote seems to remotely resemble that.
- scottcodie 5y agoI'm just trying to be helpful. :(
- bawolff 5y agoI apologize. I could have (and should have) wrote that comment in a way that was less confrontational.
- deleted 5y ago[deleted]
- hinoki 5y agoAnd even if it did, P=NP is based on a model of computation. So even if there is a proof of P=NP with quantum computers, that could still leave the question open on classical computers.
- sova 5y agoNow that's a notion I do not often hear. Maybe a question for a 3D-abacus made of stones and flowing water.
- bawolff 5y ago> So even if there is a proof of P=NP with quantum computers That doesn't really even make sense as a sentence. A quantum computer is neither a Turing machine nor a non-deterministic Turing machine. I guess what you're trying to say is that even if someone proved/disproved BQP=NP it would leave P=NP open.
- sova 5y ago"A new ontological category"... more like multiple golf balls competing for the same hole. "Choreographing interference patterns" would not actually further computation, but simply suggest a new set of tools that could be, by accident or happenstance, calibrated to produce results where other devices could not. Is that your point?
- sweis 5y agoA quantum computer is not "infinitely parallel" and though it's still an open problem, it's considered unlikely that that quantum computers can solve NP-complete problems in polynomial time.
- sova 5y ago>A quantum computer is not "infinitely parallel" Explain
- bawolff 5y agoI mean that's pretty much it. You can't use a quantum computer like a classical computer with a huge (infinite) number of compute cores. Its not a gpu. That's not how it works. If you use the metaphor that superposition is like computing many things in paralell, the problem comes in that when you measure. The superposition collapses to a single answer at random (with probability related to the amplitude of each possibility) which will usually not be the answer you're interested in.
- dvdkhlng 5y agoMy take on it: you get "infinitely parallel" computation, generating "inifinetly parallel" results that are in superposition. Problem is, at the end you can only access your "infinitely parallel" result via a classical measurement, involving a wave function collapse [1]. For some problems, people have found ways to extract useful information via classical measurements, e.g. Shor's algorithm (in theory breaking RSA/DSA/ECDSA/DH/ECDH style public-key algorithms [1]). However in the general case this does not work (so AES and hash algorithms are safe for now). [1] https://en.wikipedia.org/wiki/Wave_function_collapse https://en.wikipedia.org/wiki/Wave_function_collapse [2] https://en.wikipedia.org/wiki/Shor%27s_algorithm#Quantum_part:_period-finding_subroutine https://en.wikipedia.org/wiki/Shor%27s_algorithm#Quantum_par...
- anonuser123456 5y agoP?=NP isn't the question of, "If given an infinite number of monkeys can one compute an exponential problem really quickly?" Its the question of, "Does a mapping exist from that fast infinite monkey machine to a finite monkey machine that runs in polynomial time?" I think parent's question is "Can the problem be encoded such that one can prove that no translation can prune the number of monkeys required at an exponential rate?" I have wondered that myself, but never found any particularly useful answer.
- sova 5y agoYes, but is it right to approach this question from sequence just because computation implies sequence? Mathematics has an equals sign and suggests not the computational sequence, just the logical sequence of our axioms mapped to self-evident fact. Mathematics to Information Theory to Computation naturally goes from clear postulates and language-able axioms to water-wheelable traits. I suggest there is some room for exploration in between.
- deleted 5y ago[deleted]
- mistercow 5y agoI don’t know the history of it, but I can imagine people thinking the same thing about comparison sorts early on; how could you possibly sort a list without comparing every element to every other element? I mean, I agree with the conclusion that P probably doesn’t equal NP, if nothing else because we’ve had an awful lot of very smart people looking at it without any inkling to the contrary. But I don’t generally trust “I don’t see how” intuitions with this sort of thing.
- musicale 5y ago> I can imagine people thinking the same thing about comparison sorts early on; how could you possibly sort a list without comparing every element to every other element Maybe people who never tried (or thought about) reshelving library books, sorting/delivering mail, etc..
- Sharlin 5y agoIndeed the very word "sorting" in its general sense means arranging items into categories (ie. equivalence classes) which doesn’t usually involve pairwise comparisons at all.
- gfody 5y ago"I don't see how" can't be trusted coming from someone who hasn't even tried. if you're sorting a pile of stones by weight you quickly learn to leverage the transitive property
- tylerhou 5y agoCorrect me if I am wrong, but I don’t think the decision problem “does an optimal path in TSP have length K” is in NP (as it likely cannot be checked in polynomial time). Otherwise, we could solve optimal path TSP in polynomial time by binary searching over K. https://blog.computationalcomplexity.org/2014/01/is-traveling-salesman-np-complete.html?m=1 https://blog.computationalcomplexity.org/2014/01/is-travelin...
- Armisael16 5y agoThat isn’t quite how the decision problem is usually phrased. It’s usually “Is there a path of at most length L?”, which is pretty easily in NP. Minor difference in wording but a big difference in complexity. Asking for the optimal solution of most of the classic NP problems will make them not NP.
- tylerhou 5y agoI was aware of that distinction (of the decision problem), but I didn’t make the connection that solving the canonical decision problem in polynomial time meant that you could also solve the optimization problem in polynomial time with binary search, which is true. But the linked post also claims checking whether a path is optimal is not in NP. Even then, P=NP would still imply TSP could be solved in polynomial time. So I was kinda wrong, for subtle reasons…
- throwaway81523 5y agoAsking whether a given path is optimal is in co-NP. You can prove that the path is non-optimal by exhibiting a shorter path.
- beecafe 5y agoGiven a solution to the decision version of TSP, you can verify whether that solution is valid in polynomial time - just check if it does visit the nodes and is of the claimed length. A normal Turing machine could perform this check in poly time, and a nondeterministic one could check all solutions (exponentially many) in poly time, hence NP.
- skissane 5y agoI hope nobody proves that "P!=NP" because that would just be too boring, too expected. I think the coolest possible outcomes would be one of the following: (a) some bizarre algorithm which solves an NP-complete problem in polynomial time but with utterly intractable exponents or constants, for example worse than O(n^(10^100)) – so, yes, P=NP, in a completely useless way, and still nobody would know if a useful P algorithm for an NP-complete problem exists (b) a non-constructive proof that P=NP (c) an independence proof, that the question is independent of ZF(C) (d) a proof that you can't prove "P!=NP" from ZF(C), but which left open the question of whether "P=NP" was provable from ZF(C) or not (e) proof of something like "P!=NP implies not-CH" or "P!=NP implies not-AC" I realise the odds are against any of the above. But, here's to hoping for the bizarre unexpected outcome, rather than merely "we just hadn't yet developed the technique to prove what most people thought was true all along" – which would be less profound, less mysterious On a somewhat different topic, if my hope is for naught, and there indeed exists a proof that "P!=NP" out there waiting to be discovered, even actually discovered in a few years or decades or centuries time, then I've just expressed a counterpossible hope, a hope that an impossible world were actual – which, I think, is a philosophically rather interesting hope to express.
- rsj_hn 5y agoI would prefer option d)
- froh 5y agoHow is n^10^100 polynomial?
- skissane 5y agoO(n^k) is polynomial for all k > 1, and that remains true when k=10^100
- google234123 5y agon^2 is polynomial, 2^n is exponential (variable is in the exponent)
- throwawaylinux 5y ago> I have low hopes for P=NP. I really don’t see how you can solve for example the TSP exactly to guaranteed optimality without utilizing all of the useful available information. Not sure what you're getting at here. The available useful information is a set of cities each with distances to the other cities. About N^2 pieces of information. A computer can "utilize" all these data in polynomial time.
- whatever1 5y agoThe information needed to solve the tsp problem is not the distances matrix. It’s the set of Hamiltonian paths in your graph. And that scales factorially with the number of cities. It is the subtour elimination (remove cycles) that makes the tsp problem difficult. Not the connectivity.
- gizmo686 5y agoAll the information about the Hamiltonian paths is encoded in your N verticies and N^2 edges. Your arguement suggests the best solution to TSP runs in Θ(n!). However https://en.m.wikipedia.org/wiki/Held%E2%80%93Karp_algorithm https://en.m.wikipedia.org/wiki/Held%E2%80%93Karp_algorithm can solve TSP in Θ(2^n n^2)
- whatever1 5y agoWhich means that many of Hamiltonian paths are strictly dominated than others, so you don’t have to evaluate them at all. Same as in sorting you don’t have to evaluate all of the possible pairs. I did not imply that all information is useful. I proposed that probably there is a lower bound of information that you definitely need to find the optimal solution to the tsp.