5 results back to index

Algorithms Unlocked by Thomas H. Cormen Amazon: amazon.com — amazon.co.uk — amazon.de — amazon.fr
bioinformatics, knapsack problem, NPcomplete, optical character recognition, Silicon Valley, sorting algorithm, traveling salesman Knapsack In the knapsack problem, we are given a set of n items, each with a weight and a value, and we ask whether there exists a subset of items whose total weight is at most a given weight W and whose total value is at least a given value V . This problem is the decision version of an optimization problem where we want to load up a knapsack with the most valuable subset of items, subject to not exceeding a weight limit. This optimization problem has obvious applications, such as deciding which items to take backpacking or what loot a burglar should choose to pilfer. The partition problem is really just a special case of the knapsack problem, in which the value of each item equals its weight and both W and V equal half the total weight. If we could solve the knapsack problem in polynomial time, then we could solve the partition problem in polynomial time. … If we could solve the knapsack problem in polynomial time, then we could solve the partition problem in polynomial time. Therefore, the knapsack problem is at least as hard as the partition problem, and we don’t even need to go through the full reduction process to show that the knapsack problem is NPcomplete. General strategies As you have probably realized by now, there is no onesizefitsall way to reduce one problem to another in order to prove NPhardness. Some reductions are pretty simple, such as reducing the hamiltoniancycle problem to the travelingsalesman problem, and some are extremely complicated. Here are a few things to remember and some strategies that often help. 206 Chapter 10: Hard? Problems Go from general to specific When reducing problem X to problem Y, you always have to start with an arbitrary input to problem X. … The hamiltoniancycle problem is more restricted because each edge has only one of two “values”: present or absent. Look for special cases Several NPcomplete problems are just special cases of other NPcomplete problems, much as the partition problem is a special case of Chapter 10: Hard? Problems 207 the knapsack problem. If you know that problem X is NPcomplete and that it’s a special case of problem Y, then problem Y must be NPcomplete as well. That is because, as we saw for the knapsack problem, a polynomialtime solution for problem Y would automatically give a polynomialtime solution for problem X. More intuitively, problem Y, being more general than problem X, is at least as hard. Select an appropriate problem to reduce from It’s often a good strategy to reduce from a problem in the same, or at least a related, domain as the problem you’re trying to prove NPcomplete. 
pages: 523 words: 143,139 
Algorithms to Live By: The Computer Science of Human Decisions by Brian Christian, Tom Griffiths Amazon: amazon.com — amazon.co.uk — amazon.de — amazon.fr
4chan, Ada Lovelace, Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Albert Einstein, algorithmic trading, anthropic principle, asset allocation, autonomous vehicles, Berlin Wall, Bill Duvall, bitcoin, Community Supported Agriculture, complexity theory, constrained optimization, cosmological principle, cryptocurrency, Danny Hillis, delayed gratification, dematerialisation, diversification, double helix, Elon Musk, fault tolerance, Fellow of the Royal Society, Firefox, firstprice auction, Flash crash, Frederick Winslow Taylor, George Akerlof, global supply chain, Google Chrome, Henri Poincaré, information retrieval, Internet Archive, Jeff Bezos, John Nash: game theory, John von Neumann, knapsack problem, Lao Tzu, linear programming, martingale, Nash equilibrium, natural language processing, NPcomplete, P = NP, packet switching, prediction markets, race to the bottom, RAND corporation, RFC: Request For Comment, Robert X Cringely, sealedbid auction, secondprice auction, selfdriving car, Silicon Valley, Skype, sorting algorithm, spectrum auction, Steve Jobs, stochastic process, Thomas Malthus, traveling salesman, Turing machine, urban planning, Vickrey auction, Walter Mischel, Y Combinator The second, Continuous Relaxation, turns discrete or binary choices into continua: when deciding between iced tea and lemonade, first imagine a 50–50 “Arnold Palmer” blend and then round it up or down. The third, Lagrangian Relaxation, turns impossibilities into mere penalties, teaching the art of bending the rules (or breaking them and accepting the consequences). A rock band deciding which songs to cram into a limited set, for instance, is up against what computer scientists call the “knapsack problem”—a puzzle that asks one to decide which of a set of items of different bulk and importance to pack into a confined volume. In its strict formulation the knapsack problem is famously intractable, but that needn’t discourage our relaxed rock stars. As demonstrated in several celebrated examples, sometimes it’s better to simply play a bit past the city curfew and incur the related fines than to limit the show to the available slot. In fact, even when you don’t commit the infraction, simply imagining it can be illuminating. … (In formal notation: “Since 1rj∑ Cj is NPhard, does that imply that 1pmtn, rj∑ Cj is NPhard, too?” “No, that’s easy, remember?” “Well, 1dj∑ Cj is easy and that implies 1pmtn, dj∑ Cj is easy, so what do we know about 1pmtn, rj, dj∑ Cj?” “Nothing” [Lawler et al., “A Gift for Alexander!”; see also Lawler, “Old Stories”].) the problem becomes intractable: In fact, it’s equivalent to the “knapsack problem,” computer science’s most famously intractable problem about how to fill space. The connection between this scheduling problem and the knapsack problem appears in Lawler, Scheduling a Single Machine to Minimize the Number of Late Jobs. a certain time to start some of your tasks: What we are calling “start times” are referred to in the literature (we think somewhat ambiguously) as “release times.” Lenstra, Rinnooy Kan, and Brucker, “Complexity of Machine Scheduling Problems,” showed that both minimizing sum of completion times and minimizing maximal lateness with arbitrary release times are NPhard. … .; networking; websites fast connections geography of infrastructure of protocols and security and interrupt coalescing interruptions intractable problems defined equilibrium and relaxation and scheduling and Introduction to Relaxation Methods, An (Shaw) intuitive hunches investment strategies invitations involuntary selflessness Jacobson, Van Jain, Kamal James, William Jarvis, Richard Jaws (film) Jay, Francine Jeffreys, Harold Jet Propulsion Laboratory (JPL) jitter Jobs, Steve job search Johnson, Selmer Jones, William Joy of Less, The (Jay) judgment “just play the game” approach just society Kaelbling, Leslie Kahn, Robert “Bob” Kant, Immanuel Karels, Michael Karp, Richard Kaushik, Avinash Kayal, Neeraj Keats, John Keeping Found Things Found (Jones) Kenney, Richard Kepler, Johannes Kerr, Clark Keynes, John Maynard alKhwārizmī King County Library System (KCLS) king of the hill Kipling, Rudyard Kirkpatrick, Scott Kleinrock, Leonard Kline, Charley knapsack problem Knuth, Donald Koomen, Pete Ladder tournaments Lagrange, JosephLouis Lagrangian Relaxation Lai, Tze Leung lancet liver fluke Lange, Rebecca language Lao Tzu Laplace, PierreSimon Laplace’s Law Lasso latency lateness, minimizing maximum laundry law enforcement Lawler, Eugene “Gene” “Lawn Tennis Tournaments” (Dodgson) Law of Gross Tonnage Lawrence, Peter A. Lawrence Berkeley Laboratory (LBL) lawsuits Lazzarini, Mario Least Recently Used (LRU) Lee, Michael leftside insertion rule Le Guin, Ursula K. 
pages: 229 words: 67,599 
The Logician and the Engineer: How George Boole and Claude Shannon Created the Information Age by Paul J. Nahin Amazon: amazon.com — amazon.co.uk — amazon.de — amazon.fr
Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Albert Einstein, Any sufficiently advanced technology is indistinguishable from magic, Claude Shannon: information theory, conceptual framework, Fellow of the Royal Society, finite state, four colour theorem, Georg Cantor, Grace Hopper, Isaac Newton, John von Neumann, knapsack problem, New Journalism, reversible computing, Richard Feynman, Richard Feynman, Schrödinger's Cat, Steve Jobs, Steve Wozniak, thinkpad, Turing machine, Turing test, V2 rocket That is, a quantum computer actually follows a multitude of superimposed, parallel computational paths (a process called quantum interference) to arrive at its final result. Such massive parallelism is the fundamental origin of the quantum computer’s phenomenal speed. A class of famous, easytounderstand problems (quite different from the factoring and search problems) that could also benefit from the massive parallelism of a quantum computer are the socalled knapsack problems. They are old problems, dating back at least to 1897, but they have modern applications, including cryptography. One knapsack problem asks the following question: given a stretchable knapsack that can hold a maximum weight of W, and n objects of individual weights w1, W2,…, wn, is there a subset of these objects that can be put into the knapsack that just achieves the knapsack’s weight capacity? That is, is there a solution for the xi in the equation where xi = 0 or 1 for 1 ≤ i ≤ n? … See also error detection Hartley, Ralph Hermite, Charles Hermitian matrix Hilbert, David Hopper, Grace Huxley, Thomas identity matrix infinity: countable; uncountable invertor gate, quantum. See also NOT “Investigation of the Laws of Thought, An” (Boole) irreversible: computation; logic gate JK flipflop Jobs, Steve Karnaugh, Maurice; map of Kelland, Philip Kelly, Jr., John Kelvin, Lord. See Thomson, William Kirchhoff, Gustav; circuit laws of knapsack problems Landauer, Rolf Laplace, PierreSimon latch Leibniz, Gottfried Levor, Norma logical operations: and; exclusiveor; inclusiveor; NOT. See also switch logic gates: irreversible; reversible. See also gates, logic “Logic of Chance” (Venn) machine (asynchronous); synchronous) majority logic map method. See Karnaugh map “Mathematical Analysis of Logic” (Boole) “Mathematical Theory of Communication, A” (Shannon) matrix. 
pages: 470 words: 144,455 
Secrets and Lies: Digital Security in a Networked World by Bruce Schneier Amazon: amazon.com — amazon.co.uk — amazon.de — amazon.fr
Ayatollah Khomeini, barriers to entry, business process, butterfly effect, cashless society, Columbine, defense in depth, double entry bookkeeping, fault tolerance, game design, IFF: identification friend or foe, John von Neumann, knapsack problem, mutually assured destruction, pez dispenser, pirate software, profit motive, Richard Feynman, Richard Feynman, risk tolerance, Silicon Valley, Simon Singh, slashdot, statistical model, Steve Ballmer, Steven Levy, the payments system, Y2K, Yogi Berra But given a single product, it can be impracticable to factor the number and recover the two factors. This is the kind of math that can be used to create publickey cryptography; it involves modular arithmetic, exponentiation, and large prime numbers thousands of bits long, but you can elide the details. Today, there are a good halfdozen algorithms, with names like RSA, ElGamal, and elliptic curves. (Algorithms based on something called the knapsack problem were another early contender, but over the course of about 20 years they were broken every which way.) The mathematicals are different for each algorithm, but conceptually they are all the same. Instead of a single key that Alice and Bob share, there are two keys: one for encryption and the other for decryption. The keys are different, and it is not possible to compute one key from the other. 
pages: 489 words: 148,885 
Accelerando by Stross, Charles Amazon: amazon.com — amazon.co.uk — amazon.de — amazon.fr
call centre, carbonbased life, cellular automata, cognitive dissonance, Conway's Game of Life, dark matter, dumpster diving, Extropian, finite state, Flynn Effect, glass ceiling, gravity well, John von Neumann, knapsack problem, Kuiper Belt, Magellanic Cloud, mandelbrot fractal, market bubble, means of production, packet switching, performance metric, phenotype, planetary scale, Pluto: dwarf planet, reversible computing, Richard Stallman, SETI@home, Silicon Valley, Singularitarianism, slashdot, South China Sea, stem cell, technological singularity, telepresence, The Chicago School, theory of mind, Turing complete, Turing machine, Turing test, upwardly mobile, Vernor Vinge, Von Neumann architecture, web of trust, Y2K He's not sure Pamela ever let him see her fully naked: She thought skin was more sexy when it was covered. Annette squeezes him again, and he stiffens. "More!" By the time they finish, he's aching, and she shows him how to use the bidet. Everything is crystal clear, and her touch is electrifying. While she showers, he sits on the toilet seat lid and rants about Turingcompleteness as an attribute of company law, about cellular automata and the blind knapsack problem, about his work on solving the Communist Central Planning problem using a network of interlocking unmanned companies. About the impending market adjustment in integrity, the sinister resurrection of the recording music industry, and the stillpressing need to dismantle Mars. When she steps out of the shower, he tells her that he loves her. She kisses him and slides his glasses and earpieces off his head so that he's really naked, sits on his lap, and fucks his brains out again, and whispers in his ear that she loves him and wants to be his manager. 