우리가 현재 사용하고 있는 현대 컴퓨터를 결정론적 튜링 머신이라고 이야기하고,
양자 컴퓨터를 비결정론적 튜링 머신이라고 이야기 하자나
그리고 이 결정론적 튜링 머신과 비결정론적 튜링 머신의 차이가
결정론적 튜링 머신은 한번에 한 시점에 한가지 상태밖에 가지지 못한다는거고
비결정론적 튜링 머신은 한번에 한 시점에 여러 상태를 가질 수 있는거고,
따라서 비결정론적 튜링 머신은 지수 시간의 시간 복잡도를 가지는 문제들을 다항 시간내에 해결할 수도 있다. 자나.
근데 이거 그냥 결정론적 튜링 머신을 병렬적으로 연결해서 사용하면 사실상 여러 상태를 한 시점에 가지고 있는거 아냐?
물론 이건 지수시간의 시간 복잡도를 다항 시간 내에 해결 할 수 없겠지.
결정론적 튜링 머신을 병렬적으로 연결해서 한시점에 여러 상태를 가지고 있는거랑
비결정론적 튜링 머신이 한시점에 여러 상태를 가지고 있는거랑 정확히 무슨 차이인지 알려조
문과 대가리로는 잘 모르겠어 흑흑 인터넷에 찾아봐도 뭐라는지 모르겠구
내가 아는바론 양자컴퓨터는 통상적인 논리게이트 AND, OR과 같은거 대신에 퀀텀 연산이라는 다른 게이트를 달 수 있는거고 그게 NDTM을 해주진 않아.
그네. 더 찾아보니까 quantum computing이랑 NDTM이랑은 완전 별개하카네
무식한 질문에 현명한 답변 ㄳ
그거랑 별개로 양자컴퓨터가 NP문제 일부를 풀긴 하는데 양자컴퓨터가 다항시간안에 풀수있는 문제가 NP와 포함관계가 어느 한쪽으로 있는것도 알려져있지 않은걸로 알고있음
마지막으로 그 통상적인 DTM으로 모든 상태값을 추적하면 NDTM을 굴릴수 있다는게 말은 맞는말인데 그럼 시간이 지수적으로 걸려서 도로묵이 됐던걸로 기억함.. 애초에 몇스텝 굴리지도 못할거야
니 말대로 병렬로 튜링머신 연결하면 되는데 핵심은 양자컴퓨터의 경우 큐빗이 늘어날수록 컴퓨팅 파워가 지수적으로 증가한다는거다. 튜링머신은 연결할수록 한계체감 때문에 로그로 증가하고 - return 0;