[일반] MIP*=RE가 뭐임?

[논리화학(logicalchemistry)]

ㅈㄱㄴ 유한시간내에 튜링머신으로 yes or no를 도출할 수 있는 문제랑 양자뭐시기랑 같다는거같은데 이 양자뭐시기가 뭔지를 모르겠네

[익명(175.223)]

https://www.nature.com/articles/d41586-020-00120-6

[llll(147.46)]

RE는 유한시간에 yes no 를 도출하는거보다 더 큰 문제임. YES인 string들을 순서대로 나열할수 있는 문제들의 클래스들이고, 이거는 심지어 halting problem이라는 computable 불가능한 문제까지 포함함. (halting problem은 이 인풋 프로그램을 돌리면 끝나는가? 라는 문제고, YES를 나열하기 위해서는 T=1,2,...에 대해 T에 끝나는 프로그램들을 순서대로 나열하면 됨) IP는 interactive proof라는 앤데, 무한한 힘을 가진 증명하고자하는애(Prover)가 나한테 주어진 문제가 YES인걸 증명 가능한지를 묻는 애임. 나는 다항식시간 연산만 하구. (NP의 확장으로 볼수있음).

[llll(147.46)]

이거에서 Prover가 여러명이 되면 더 많은 문제의 클래스를 포함하게 됨 (prover들끼리의 interaction은 없음). 이게 MIP인데, MIP=NEXP인게 증명되어있음. MIP*는 그럼 그 prover들이 quantum entanglement를 share하고있으면 어떻게되냐? 는거고, 이게 궁금한 이유는 quantum entanglement의 complexity class에서 힘이 어느정도 되냐는거지. 이번에 증명된게 MIP*=RE로 MIP보다 훨씬, 훨씬훨씬 훨씬 강력하다는거고.

[dd(110.12)]

RE도 잘못이해한거같은데 RE는 computable한 결정문제의 class보다 큼. 유한시간안에 yes, no를 판별하는게 아니라 답이 yes일때 유한시간안에 판별할수 있으면 되고 답이 no일때는 못해도 됨. 예를들어 디오판틴 방정식이 해를 가지는가? 하는 결정문제는 가능한 모든 정수를 하나씩 다해보면 답이 yes일때는 언젠간 답을 주겠지만 no일때는 무한루프에 빠질텐데 이정도만 할 수 있어도 RE에 속함.

[논리화학(logicalchemistry)]

오..글쿤용