Has the NP-Complete Problem been solved?

2006-01-19 4:37 pm

回答 (4)

2006-01-20 6:10 am
✔ 最佳答案
No no in classical model of mathemetics.But in quantum logic one of these problem the factorization problem is solved by the Shor's algorithm..In fact this gave the scientist a new look for the quantum computation.
2016-12-13 12:23 am
The NP-finished complexity classification is defined for a Turing gadget. they do no longer keep on with for different computing paradigms, like quantum computing. God, being all-powerful, can genuinely layout a computer that ought to remedy any NP-finished situation in polynomial time.
2006-01-20 4:22 am
Of course NP Complete problems can be solved, just not in polynomial time.

If you could solve them in polynomial time, I wasted a third of a semester by studying them. Not to mention, RSA cryptography would be pretty well useless, since it relies on an NP complete problem for its security. Some conspiracy theory types believe that the NSA has secretly solved the problem and so can easily decrypt any RSA transmissions...but it seems unlikely to me, since so many people have been working on this problem.
2006-01-19 4:43 pm
No. An NP-complete problem means you must try all possibilities before you can decide which is the best one. They are generally tackled in real life by trying many possibilities and choosing the best of those, as it is likely that that is very close to the best possibility.

Some people thing quantum computers will be able to tackle NP-complete problems by trying all the possibilities at the same time, but quantum computers that are controllable and have enough q-bits are a long way off.


收錄日期: 2021-04-23 15:40:07
原文連結 [永久失效]:
https://hk.answers.yahoo.com/question/index?qid=1006011901920

檢視 Wayback Machine 備份