What is Digg?Sponsored by Dragon Age: Origins
Join the Dragon Age: Origins development team on Facebook view!
facebook.com/DragonAgeOrigins - EA presents BioWare's new dark fantasy epic Dragon Age: Origins. '9/10' from Game Informer.
79 Comments
- inactive, on 10/12/2007, -8/+67This is nonsense. Computers do NOT have trouble completing Sudoku puzzles. While a lot of computations are typically required to obtain an answer for every cell in the Sudoku grid, modern computers can finish a whole Sudoku grid in FAR less time than is required to calculate just one good move in a chess game. If you want to prove this to yourselves, all you need to do is Google for "Sudoku Solver", which will give you a plethora of websites that have downloadable solvers or embedded Java applets right on the site. Try them out and see just how fast they are. Hell, there are actually Sudoku games and solvers on cell phones, even those that are very cheap and low-end.
For a true test of computational power, try writing a program that is proficient at the game of "Go". The amount of calculations required for that game are so insanely huge that we still don't have a computer (nor a piece of AI software) that can successfully defeat an above-average human Go player, whereas multiple Chess programs can defeat most human grandmasters in Chess. - JohnMarkT, on 10/12/2007, -0/+35Sudoku? This is what I was expecting to happen when they turned it on this morning:
9:37 am: found a cure for cancer
10:11 am: made contact with aliens
10:42 am: ended world hunger
...and then spend the rest of the day figuring out how to satisfy a woman. - EvilZoo42, on 10/12/2007, -4/+30Not sure if Quickdood was being sarcastic here, but sudoku puzzles are not difficult to solve using a computer (a simplistic solver works in seconds). In fact, most sudoku puzzles are ranked in difficulty as to how many steps it takes a computer to solve them.
- Quickdood, on 10/12/2007, -4/+28Although typical Sudoku puzzles (with 9×9 grid and 3×3 regions) can be solved quickly by computer, the generalization to larger grids is known to be NP-Complete. To learn more about NP-Complete go here: http://en.wikipedia.org/wiki/NP-Complete Basically once the grids get larger than 9x9 computers have trouble figuring the problems out.
- pbaehr, on 10/12/2007, -0/+17"We're breaking new ground every day in the field of quantum computing, but we're having a particularly difficult time getting out of the Candy Cane Forest."
- juniorcosmonaut, on 10/12/2007, -0/+15What's with everyone pointing out that Sudoku are so easy to solve, that isn't the point, the whole idea is that it's actually solving them using QUANTUM MECHANICS!!!
This technology is in it's very earliest stages and as it advances it has the promise of far surpassing what we have today - you have to start somewhere - elhaf, on 10/12/2007, -2/+17Wow. As a PhD candidate in theoretical computer science, I can't let meatbiproduct's stunning ignorance on the subject of computability theory just lie there unanswered. Most things cannot be computed easily, regardless of the computer (or the programmer). These things are called np-hard or np-complete (depending on how the problem is stated). They are thought to have a solution requiring search of the entire exponential solution space. This is intractable (will take longer than lifetimes) for problems of size as small as 80. A quantum computer bypasses this by "trying all solutions at once" in quantum space. However, even a quantum computer can't compute the halting problem. That is uncomputable by anything, because if it were computable, you'd just ask it about itself and reverse the answer to loop forever or halt, such as "If I halt, loop forever else halt." Many problems are known to be equivalent to this, even though the self-reference isn't obvious. You can't even compare two programs and say, "do they compute the same function?" So no, not every problem can be solved.
- Stompp, on 10/12/2007, -1/+15I agree, I have sodoku on my cellphone and IT has no problem solving puzzles... fairly quickly too.
- nepawoods, on 10/12/2007, -1/+15As someone else pointed out above, it's NP-Complete, which fits most criteria for "hard for computers to solve".
http://en.wikipedia.org/wiki/Sudoku#Computer_solutions - afx1, on 10/12/2007, -2/+15People can relate to Sudoku, not quantum entanglement.
- WarpFox, on 10/12/2007, -2/+14Allow me to use the example of cryptogrophy to explain to you what a big deal this is. A computer needs to find a solution of bits, lets say the answer is 101. (this would be found very quickly obviously, but lets pretend it is a much much larger string of bits that would take modern day computers a lot of time to crack, say years.) Typical computers must try each solution one at a time, 000, 001, 010, 011, 100, etc. until it arrives at the solution.
Quantum computers use superposition (http://en.wikipedia.org/wiki/Superposition) to try ALL SOLUTIONS AT THE SAME TIME, since bits are both 0 at 1 at the same time thus providing an immidate answer to an otherwise unsolvable problem. - doshindude, on 10/12/2007, -1/+13Pretty soon we will have computers that play Candy Land too.
- Quickdood, on 10/12/2007, -7/+18Although this is not the quantum computer I was hoping to see, I am happy to see that quantum computers may be closer than we all thought they would be. Can't wait to see the 1,000 qubit version next year!
- CraigB12, on 10/12/2007, -2/+13This doesn't really belong here, but i thought if i posted it up top someone that knew would see it.
I know quantum computers use qubits as opposed to bits, and i know what a qubit is, but whats the difference between a 16-bit quantum computer and a 1000 qubit quantum computer. I guess my main question is how do you correlate the 2 on the same platform? - dtd00d, on 10/12/2007, -5/+14[Insert Will it Blend, Russian Reversal, Run-On-Linux, and "im in ur...." spinoffs here.]
The first dozen times was funny for each, but come on. Use some originality. - pkulak, on 10/12/2007, -0/+9Well, sure, the D-Wave looks impressive, don't touch it, but I predict that within 100 years, quantum computers will be twice as powerful, 10,000 times larger, and so expensive that only the five richest kings of Europe will own them.
Could it be used for dating?
Well, theoretically, yes. But the quantum computer matches would be so perfect as to eliminate the thrill of romantic conquest. Mw-hurgn-whey. - dansy, on 10/12/2007, -0/+8The major problem with quantum computers is scaling - a 16 bit digital computer can generally solve any problem that a 32 bit computer will solve but in a longer time - however a 16 qubit computer can instantly solve problems that can be expressed in 16-qubit terms but can never solve a 17-qubit problem ...
- fredrated, on 10/12/2007, -1/+9"Any mathematical problem or puzzle can be solved no matter the size. It just takes the correct approach and the right solution."
Not quite true, see Godels first incompleteness theorem: "For any consistent formal theory that proves basic arithmetical truths, an arithmetical statement that is true but not provable in the theory can be constructed." - geronimo, on 10/12/2007, -0/+7The possible combinations of a 9x9 sudoku puzzle are 10!*9!*8!...1! or
6,658,606,584,104,736,522,240,000,000
which requires 93 bits to solve via brute force. So with just 93 qubits they can solve sudoku immediately. 1000 qubits is quite insane. From my calculations it could solve a 33 x 33 board immediately via brute force. It would be scary if the NSA has this kind of equipment. - dfg59, on 10/12/2007, -3/+10@meatbigproduct
Obviously you are unaware of the meaning of NP-Complete. Who cares if a problem can be solved if it takes FOREVER to solve it? There are MANY classes of problems in real life that currently can not be solved in polynomial time (that is, an amount of time polynomially relative to the size of the problem). Thus, as these problems get larger, the time to solve them spins WAY out of control. Sure, any problem can be solved. I'll just brute-force the answer with every possible combination I can think of for the next million years. Is that an acceptable "answer" to you? - erkokite, on 10/12/2007, -1/+8Uh no. Actually it's not. It's been all across the news over the last few days. OSNews, Digg, and Physorg, and probably Slashdot too have all been covering it thoroughly. It was publicly demonstrated yesterday. Sciam is also reputable.
- mystagogue, on 10/12/2007, -0/+6i think you need to read up on NP-completeness, meat.
- k0sty, on 10/12/2007, -0/+6@lighty14
If you are given a Good Sudoku (meaning that it has one unique solution, as described in the definition of a sudoku puzzle) a brute force approach is guaranteed to succeed. all you have to do is a depth first search... most of the sudoku solvers that you'll see online use this aforementioned approach. - JAVandiver, on 10/12/2007, -0/+5Glaven!
- postaldave, on 10/12/2007, -2/+7skynet
http://en.wikipedia.org/wiki/Skynet - stuman77, on 10/12/2007, -3/+8In Soviet Russia, Sudoku solves you!
- ryannerd, on 10/12/2007, -0/+5Cool for proof of concept.
I was starting to think that computer science was becoming stagnated, and had almost resigned myself to the most interesting thing being the Microsoft vs. Linux/Mac/WhomEverChallengesBill debate that has been boring us all for years now. - partialinfinity, on 10/12/2007, -1/+5The answer is 42.
- elhaf, on 10/12/2007, -3/+7And meatbiproduct said "mathematical problem" so let me pose one. Write me a program that finds the largest twin primes (primes that differ by two). It's easy enough to write, just loop for all i, if i is prime, check if i+2 is prime too, and when you get to the last one, stop. When your program is done, we will know whether there are infinitely many twin primes, or not. kthxbi.
- helf, on 10/12/2007, -1/+5wow, elhaf. "Theoretical Computer Science"?
isn't that just a way of saying... "I don't do *****."? - WarpFox, on 10/12/2007, -5/+8@dtd00d
http://en.wikipedia.org/wiki/Meme
welcome to the internet. - addicted68098, on 10/12/2007, -0/+3that made my day
- stevenb486, on 10/12/2007, -0/+3@CraigB12
I think he meant to say 16-QUbit which is something like 2^16 or 65536 simultaneous states, which is pretty mediocre considering modern cpus can do billions of instructions per second. In the article it says they're making a 1000 qubit computer? thats 2^1000 or - more then the number of protons in the universe - simultaneous states, sounds unbelievable to me - lighty14, on 10/12/2007, -4/+7^^ Is correct. My Data Structures prof. demonstrated a Sudoku solver that used a satisfiability solver that he and a few others created together. Even the most difficult Sudoku was solved rapidly with very little backtracking. He also showed a brute force method of solving it, which took forever to solve the puzzle and also doesn't guarantee success.
- Xanadude, on 10/12/2007, -0/+3elhaf, Your point is well-taken, but to nitpick your specific example, determining the largest twin primes is not necessarily a non-computable problem - you have provided a non-halting "solution" for it, but not a proof that no finite-time solution exists.
- bubbius, on 10/12/2007, -0/+2@elhaf
As a PhD student, you should know better than to open your mouth before carefully considering what you are saying. Quantum computers cannot simply compute exponentially many solutions as would be the case in searching for witnesses to languages in NP. Indeed, you can prepare an input register in a superposition of all possible n-bit inputs, and compute any classical circuit describing f immediately, but measuring the output register essentially just gives you a sample of the function on a random input. The key to solving problems in the quantum model is destructive interference and widdling down this huge superposition into something reasonably likely to succeed, i.e. with some constant probability.
Of course, the theory does not exclude the possibility of somebody coming up with non-black-box techniques for solving NP-complete problems efficiently on a quantum machine, but the "brute force" search is PROVEN to only offer a quadratic speedup, which is obviously still exponential in n.
However, I agree completely that people need to distinguish between computability and complexity of computable languages. - DigitalJester, on 10/12/2007, -1/+3Awesome...
I even understoond the Frink noise at the end. - Prysorra, on 10/12/2007, -0/+2"Although typical Sudoku puzzles (with 9×9 grid and 3×3 regions) can be solved quickly by computer, the generalization to larger grids is known to be NP-Complete. Various optimisation[sic?] methods have been proposed for large grids"
Next time, read through the comments before repeating the same crap arguments. - Xyleene, on 10/12/2007, -0/+2@meatbiproduct
Obviously didn't read the what parent posted.. Any problem can be solved.. but the worst case of some problems (TSP etc.. i.e. np-complete problems) is still of exponential order (i.e. infesable by any polynomial bound turing equivalent machines). Don't worry thou... its an 2-3yr comp sci university course u usually learn that in... unless you read the wikipedia article.. nvm, u didn't. - DarkXanthos, on 10/12/2007, -3/+4@fredrated You misunderstood @meatbiproduct. What @meatbiproduct was saying is that any mathematical problem for which there exists a solution can be solved by a computer. This is especially true in the case of a puzzle as opposed to a board game such as Go or Chess. Puzzles begin at a high complexity and are worked down from that, reducing complexity with each step. Board games start simple and increase complexity with each step.
- fluxion, on 10/12/2007, -0/+1@smellinator
i believe you're correct, at least i know that Shor's algorithm has been demonstrated on hardware at some point. all i mean to say is that if this hardware were a full-fledged quantum computer, they would have almost certainly demonstrated Shor's algorithm on it, since 16 qubits would a pretty substantial step forward, and would have yeilded tons of publicity for them. if this was capable of running the algorithm, and they were serious about have 1000 qubits soon, the world would be in a frenzy right now. although i believe in these types of implementations, only a rather small subset of the total qubits are actually usable. - robbiemuffin, on 10/12/2007, -0/+1@ilyag, you're missing the point. No one is trying to create a really, REALLY good sudoku solver ... a generalization of sudoku happens to be NP-Complete ... a class of problems computers can approximate fairly well and quickly, but to get the perfect answer takes inordinate time as the size of the problem grows. Adiabatic QC could possibly solve these sorts of problems quickly, if the process scales to many qubits. Sudoku just happens to be fun, something people can relate to, and still useful from an complexity point-of-view.
- themastersb, on 10/12/2007, -0/+1My computer can solve sudoku. I just search Google for a sudoku solver and that's it.
- smellinator, on 10/12/2007, -0/+1@ fluxion:
If I recall correctly, Shors algorithm was demonstrated last year on a quantum computer. Not this model, mind you. But some 3 Qbit processor or something like that. As I recall, it factored the number 15, and made the news..
Yes, that would be less impressive!
RSA is safe for a little while longer. (well, RSA-1 isn't! But RSA-512 or RSA-1024.. I think we're still safe.) - augmentalist, on 10/12/2007, -0/+1Here is a link with some of the video from this demonstration.
http://www.youtube.com/watch?v=VQul2asgXbw - evilbeatfarmer, on 10/12/2007, -0/+1I thought this was supposed to solve this problem instantly, there's a "processing..." bar.. WTF? So much for quantum computing...
- Caleb83, on 10/12/2007, -2/+3The new age of computing is upon us! This is all so interesting.
- digggggggggg, on 10/12/2007, -0/+1This book: http://www.amazon.com/Algorithms-Sanjoy-Dasgupta/dp/0073523402 has a pretty good chapter on quantum computing, which dosn't require background in modern physics to understand.
Apparently, quantum algorithms don't seem to have that much effect on NP-complete problems, as in, they can't reduce what would be an order exponential problem in NP-complete to an order polynomial. I'm surprised that D-Wave didn't introduce a fourth application for their supposed "quantum computer" - factoring huge numbers. Since factoring is widely believed not to be an NP-complete problem, it's thought that a quantum computer could reduce it to polynomial time.
The three things that you can do with their systems now are not hard to solve on regular computers. It's not a very convincing demonstration. - shoover, on 10/12/2007, -0/+1It's a SCIAM article ya twit, this isn't World-Weekly-News...
- evilbeatfarmer, on 10/12/2007, -0/+1@helf
No it means he uses a calculator to do math problems! -
Show 51 - 79 of 79 discussions
Browsing Digg on your phone just got easier with our enhancements to the 
© Digg Inc. 2009
— Content created and posted by Digg users is