Factoring integers
Just to clear something up, factoring a number 100% is NOT NP-Complete, NP-Complete problems refer to problems that involve a yes/no decision (ie. primality testing). It might be NP-Hard which involves non-decision problems, but I don''t know if that has been proven/disproven yet.
quote:Original post by alvaro
Nope. What was recently proved is that primality testing can be done in polynomial time.
You're right. Homepage of Manindra Agrawal if anybody wants to check it out.
quote:Original post by alvaro
Please, stop posting if you don't know what you are talking about.
I've been a little lazy lately on checking my facts before I post them. I could use a reminder to do better every once in a while. I've posted a lot of good stuff here, too though, so I hope you're not talking about my record in general.
[edited by - GaulerTheGoat on October 9, 2003 8:37:25 PM]
quote:Original post by GaulerTheGoat
I''ve posted a lot of good stuff here, too though, so I hope you''re not talking about my record in general.
No, I was talking about this particular thread. I''m sorry if I sounded two harsh.
.
quote:Original post by alvaro
Please, stop posting if you don't know what you are talking about.
Aww, you hurted my feelings. That's just one sentence at the top of my post.
[edited by - furby100 on October 11, 2003 4:25:36 PM]
>>Actually, you CAN factor in polynomial time...
>>...you just >>need a quantum computer.
Aren''t quantum computers somewhat stochastic (ie. have a source of indefinity in them)? If that''s the case, these algorithms aren''t too much of joy (though you can test if the candidate, possibly erroreous, factors are the real factors by just multiplying them or by doing a modulo operation).
- Mikko Kauppila
>>...you just >>need a quantum computer.
Aren''t quantum computers somewhat stochastic (ie. have a source of indefinity in them)? If that''s the case, these algorithms aren''t too much of joy (though you can test if the candidate, possibly erroreous, factors are the real factors by just multiplying them or by doing a modulo operation).
- Mikko Kauppila
In theory, no. However because of their quantum nature, it is hard to isolate the computer from the rest of the world, resulting in imprecissions creeping in. This happens to some extent in "normal" computers too, however it''s much less pronounced. Some work is being done on both error-correction for quantum computers and improving the isolation/tolorence of quantum computers, however we''re still quite a few years from getting a workable quantum computer, from what I''ve heard.
The best a quantum computer has done so far, IIRC, is factor 15 into 5 and 3 -- and (also from what I''ve heard, although from a different source) is that the technology used to do this can''t be easily extended to much larger numbers.
The best a quantum computer has done so far, IIRC, is factor 15 into 5 and 3 -- and (also from what I''ve heard, although from a different source) is that the technology used to do this can''t be easily extended to much larger numbers.
Oh, and I think quantum computers can also solve NP-complete problems in polynomial time... I''m not completely sure, but pretty sure...
The goal of quantum computers is to be able to run some non-deterministic alorithms.
Since NP-hard problems are in P for non-deterministic computers, a full blown quantum computer should be able to solve problems in NP.
Quantum computers are not turing machines, so their associated complexity theory is different from the one we usually consider.
I don''t know the state of the art of quantum computing, but it coming to reality will be a MAJOR breakthrough in science (just like quantum theory was). This is going to be interesting...
Since NP-hard problems are in P for non-deterministic computers, a full blown quantum computer should be able to solve problems in NP.
Quantum computers are not turing machines, so their associated complexity theory is different from the one we usually consider.
I don''t know the state of the art of quantum computing, but it coming to reality will be a MAJOR breakthrough in science (just like quantum theory was). This is going to be interesting...
quote:Original post by Garfong
Oh, and I think quantum computers can also solve NP-complete problems in polynomial time... I''m not completely sure, but pretty sure...
Yes, they are Non-deterministic machines. And NP state for Nondeterminisctic Polynomial, so...
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
