6 ms·
Information and computation ("utilization of information") are not equivalent things. The solution is there, staring us right in the face, it's just our primit
by sova 5y ago
Information 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.