해당 논문은 이것보다 일반화된 문제를 다루며, 조건도 "It is forbidden to leave exactly the members of a forbidden set in FL (resp., FR) on the left bank (resp., the right bank)."이라서 조금 다릅니다. 정해가 O(M^2)은 아니었을 것이라고 생각합니다.

Determining Reachability Only에서 서술된 바와 다릅니다

exactly라고 하지만 구체적으로는 sub-hypercube의 정점 x가 F에 들어있는 정점 쌍에 포함되는지에 따라 forbidden이 정해지므로 Proof of Theorem 3과 이 문제는 동치입니다 

1. exactly가 어떻게 사라지는지 모르겠는데 좀 더 자세히 설명해 주실 수 있나요?
2. 사라진다고 하더라도, 이 문제는 모든 forbidden set의 크기가 3인 특수 케이스입니다. 특수 케이스이므로 더 효율적인 알고리즘이 존재할 여지가 있습니다.

방금 Theorem 3의 증명을 읽어봤는데, "x가 F에 들어있는 정점 쌍에 포함되는지에 따라 forbidden이 정해짐"은 이걸 말씀하신 것 같습니다.

F는 D∪C의 멱집합의 부분집합이므로, F의 원소는 D∪C의 부분집합입니다. 따라서 x∈F는 D∪C의 부분집합 x가 정확히 forbidden임을 의미합니다.

D∪C는 승객 그 자체를 포함하지만 Theorem 3에서 언급하는 vertex x는 다음의 하이퍼큐브의 정점입니다

 F또한 마찬가지로 Vn의 부분집합이며 문제의 조건에 따라 F를 구성한다면 입력으로 주어지는 각각의 승객을 포함하는 모든 x가 F에 속해야 하므로 여전히 동치입니다

제 댓글에서 x는 C라는 노테이션이 "D∪C"의 C와 겹치길래 아무 기호나 잡은 것입니다. 하지만 다시 겹쳐버렸네요.

같은 댓글에서 F는 F_L과 F_R을 의미했습니다. 이것도 겹쳤네요.

이 문제에서 제시하는 M을 F로 나타내면 N =  5, M = {1 2 3}일 경우에 {11100},{11101},{11110},{11111}∪{δ}와 같습니다

마지막은 잘못썼네요

그러면 |F| = O(2^N-3M)인가요?

중복되는 원소가 있어 아닙니다

바꿔 질문드리면, |F| = M이 맞나요? 리스트의 길이가 1이어도 |F| = 2^N-3이 되는 것 같습니다.

작성하다보니 |F| != M이네요 혼동을 드려 죄송합니다

논문은 무슨 말씀인지 모르겠습니다. 시간 제한의 1/3 정도에 작동하는 정답 코드가 있습니다. 

스택 기준 2116ms네요.

3명이 모이면 안된다는건 임의의 n명중에 3명이 포함되는 경우도 해당되는건가요 아니면 정확히 3명만이 어느 행성에 있는 경우만 안되는건가요?

포함이 명백하다고 생각합니다.

당연히 포함입니다..

해당 논문은 exactly가 맞고, 제가 theorem 3의 증명을 이해한 바로도 그렇습니다. 논문에서 다항 시간에 풀었다고 했는데 |F| = 2^N-3이 되면 다항 시간 알고리즘이 아니니까요.

포함/정확 여부를 건너뛰더라도, 거듭 말씀드렸지만 이 문제는 특수 케이스이기 때문에 논문 문제와 동치가 될 수 없습니다. 예를 들어 그래프의 최대 매칭을 구하는 문제를 선형 시간에 풀 수는 없지만, 그래프 중에서 트리만 주어지는 특수 케이스라면 간단한 선형 시간 알고리즘이 존재합니다. 이처럼 특수 케이스를 푸는 알고리즘이 더 일반적인 문제를 푸는 알고리즘보다 빠를 여지는 얼마든지 있습니다.

논문의 존재 여부와 이 문제의 정당성 여부는 아무 상관이 없습니다. 학계의 SOTA로 풀 수 없는 문제면 SOTA보다 잘 하셔서 푸시면 됩니다.

지금 제가 이 문제 시도하고 있는데, 이 문제는 일반적인  강 건너기 문제가 아니고, 다른 접근법을 필요로 합니다.

알고리즘 구현이 매우 어렵긴 하지만 이론적 시간 복잡도는 앞의 상수가 좀 큰 O(N+M)으로 보입니다.