سمینار کارشناسی ارشد علوم کامپیوتر: شنبه 29 بهمن 1390، ساعت 14

02/18/2012 14:00
02/18/2012 15:00
Asia/Tehran

سمینار کارشناسی ارشد علوم کامپیوتر
 
عنوان :
SAT Problem: A Quantum Approach
سخنران:
آقای علی شکیبا
زمان:
شنبه ۲۹ بهمن ۱۳۹۰، ساعت ۱۴
مکان:
کلاس ۳۰۴ - دانشکده ریاضی
 
چکیده:

 
Satisfiability problem, or SAT for short, is one of the fundamental problems in computability theory and mathematical logic. From a theoretic point of view, SAT is an NP-complete problem. Moreover it is a core problem to the NP-complete complexity class.
Quantum computational model, which is pioneered by Feynman in 1982, has attracted a great deal of attention. Following Shor’s result that factoring and extraction of discrete logarithms are both solvable in quantum polynomial time, it is natural to ask whether all of NP can be efficiently solved in quantum polynomial time.
Ordinary approaches to quantum algorithms are based on Quantum Turing machines or quantum circuits. Unfortunately it seems this approach with today’s technologies is not powerful enough to solve NP-complete problems in polynomial time.
In this talk, a new approach to NP-complete problems, more precisely SAT problem, by combining ordinary quantum computing methods with chaotic dynamical systems is reviewed