문제가 VPN 문제인지 어떻게 증명할 수 있나요? 컴퓨터 과학자들이 간단한 방법을 찾았습니다.

P/NP 문제는 계산 복잡성 분야에서 해결되지 않은 문제입니다. 사람들은 "합리적인 시간 내에 모든 컴퓨팅 문제를 효율적으로 해결할 수 있습니까?"라는 질문에 대한 답을 찾으려고 노력해 왔습니다.

합리적인 시간은 무엇입니까? 실제로 우주가 끝나기 전에 해결될 수 있는 문제들은 합리적인 시간 내에 고려된다. 그러나 많은 문제는 합리적인 시간 내에 해결하기 어려워 보이며 이러한 문제의 어려움을 입증하려면 수학이 필요합니다.

2021년 연구는 위 질문에 대한 답변을 통해 다음과 같은 사실을 확인했습니다. 대부분의 문제는 효과적으로 해결하기 어렵습니다.

워싱턴 대학의 Paul Beame은 이 연구에 대해 다음과 같이 논평했습니다. "산을 오르는 것과 마찬가지로 이 연구는 계산 이론 연구로 가는 길의 중단점입니다."

이 연구의 세 연구원: 컴퓨터 과학자 Srikanth Srinivasan(왼쪽), Nutan Limaye(오른쪽 위) 및 Sébastien Tavenas.

이 연구에서는 덧셈과 곱셈만 관련된 문제를 고려했지만 이러한 문제가 특정 방식(덧셈과 곱셈의 특정 교대 패턴)으로 해결되도록 제한되면 문제가 매우 어려워집니다.

놀랍게도 이 연구에서는 새로운 프레임워크나 도구를 사용하지 않았습니다. 대신 저자는 Noam Nisan과 공동으로 프린스턴 고등연구소 수학부 교수인 Wigderson이 설명한 수십 년 간의 작업을 우회했습니다. 예루살렘 히브리 대학교 수학 장애물.

연구원 중 한 명인 덴마크 오르후스 대학의 Srikanth Srinivasan은 다음과 같이 말했습니다. "우리는 이 장애물을 피할 수 있는 매우 간단한 방법이 있다는 것을 깨달았습니다. 그리고 그러한 간단한 방법을 사용하여 우리가 불가능하다고 생각했던 일을 할 수 있다면

중요한 질문

컴퓨터가 출현한 후 과학자들은 컴퓨터 알고리즘이 많은 문제를 해결할 수 있다는 사실을 발견했지만 때로는 이러한 알고리즘이 실제 계산 시간보다 너무 오래 걸리는 경우도 있습니다. .

그들은 문제가 크든 작든 어떤 문제는 본질적으로 해결하기가 너무 어렵다고 의심하기 시작합니다. 예를 들어, 그래프에서 중요한 문제는 해밀턴 경로가 있는지, 즉 각 꼭지점을 정확히 한 번씩 통과하는 경로가 있는지 확인하는 것입니다. 정점(및 가장자리)의 수를 늘리면 그러한 경로가 존재하는지 확인하는 데 시간이 더 오래 걸리겠지만, 최고의 알고리즘이라도 그래프 크기가 ​​증가하면 기하급수적으로 더 오랜 시간이 걸리므로 이 문제를 해결하는 것이 비현실적이 됩니다.

컴퓨터 과학자들은 어떤 방식으로든 특정 유형의 어려운 문제를 효과적으로 해결할 수 있는 알고리즘이 다른 유사한 어려운 문제의 해결책으로 변환될 수 있음을 증명하려고 노력합니다. 그들은 이러한 유형의 문제를 NP 문제라고 부릅니다.

물론, 어려워 보이지 않고 해결하는 데 시간이 많이 걸리지 않는 문제도 많이 있습니다. 이러한 문제 중 다수는 어떤 의미에서는 동일하며 이러한 문제를 P 문제라고 합니다. 그들은 NP 문제가 실제로 P 문제보다 더 어렵고 NP 문제는 결코 효율적으로 해결될 수 없다고 주장합니다. 하지만 증거가 없다면 이 생각은 틀릴 수도 있습니다.

그래서 컴퓨터 과학자들은 NP 문제가 실제로 더 어렵다는 것을 증명할 방법을 찾기 시작했습니다. 이를 위해서는 NP 문제를 해결하는 데 기하급수적인 시간이 걸린다는 것을 증명해야 했지만 이를 증명하는 것은 쉽지 않습니다.

"어려움"은 얼마나 어려운가요?

덧셈과 곱셈만 필요한 특정 문제 세트를 상상해 보세요. 예를 들어, 점 집합이 주어지면 점에 대한 데이터를 사용하여 덧셈과 곱셈만으로 가능한 모든 해밀턴 경로(존재하는 경우)를 계산할 수 있습니다.

문제 크기가 커지면 일부 산술 문제(예: 해밀턴 경로 계산)에는 시간이 더 걸립니다. 1979년에 하버드 대학교의 레슬리 발리언트(Leslie Valiant)는 많은 산술 문제가 난이도 측면에서 동일하고 다른 산술 문제는 난이도가 없다는 측면에서 동일하다는 것을 보여주었습니다. 컴퓨터 과학자들은 나중에 그의 이름을 따서 이 두 가지 유형의 문제를 각각 VNP와 VP라고 명명했습니다.

그리고 P NP 문제와 마찬가지로 VNP 문제는 후자에 기반을 두고 있기 때문에 VNP 문제보다 어렵다는 것만 알 수 있습니다. 경로가 존재합니다.

“NP보다 어렵기 때문에 어렵다는 것을 보여주기가 더 쉬울 것입니다.”라고 Shpilka는 말했습니다.

다음 수십 년 동안 컴퓨터 과학자들은 P 대 NP 문제보다 VP 대 VNP 문제에서 훨씬 더 큰 진전을 이루었지만 대부분은 Valiant가 만든 대수적 복잡성 하위 필드로 제한되었습니다. Limaye, Srinivasan 및 Tavenas의 최근 작업 이전에는 일반적인 의미에서 산술에 문제가 있는지 여부를 말하기가 여전히 어려웠습니다.

다항식 조정

이 새로운 작업은 컴퓨터 과학자들이 덧셈과 곱셈 문제에 대해 생각하는 방식을 탐구하는 데 도움이 됩니다. 수학적으로 이러한 문제는 더해지고 곱해지는 변수로 구성된 다항식(예: x^2 + 5y + 6)으로 작성될 수 있습니다.

해밀턴 경로 계산과 같은 특정 문제의 경우 이를 나타내는 다항식을 구성할 수 있습니다. 예를 들어 변수를 사용하여 각 점과 모서리를 나타낼 수 있으므로 더 많은 점과 모서리가 추가되면 더 많은 변수가 다항식에 추가될 수 있습니다.

해밀턴 경로 계산과 같은 산술 문제가 어렵다는 것을 보여주기 위해서는 더 많은 점과 모서리가 추가될수록 해당 다항식을 지수 시간 내에 해결하려면 더 많은 연산이 필요하다는 것을 보여야 합니다. 예를 들어 x^2에는 하나의 작업(x * x)이 필요하고 x^2 + y에는 두 개의 작업(x * x, + y)이 필요합니다. 연산의 수를 다항식의 크기라고 합니다.

하지만 다항식의 크기를 결정하는 것은 어렵습니다. 예를 들어 다항식 x^2 + 2x + 1입니다. 크기가 4(두 개의 곱셈과 두 개의 덧셈)인 것처럼 보이지만 다항식은 두 개의 합계(x + 1)(x + 1)의 곱으로 다시 작성할 수 있습니다. 이는 더 적은 수의 피연산자(덧셈 두 개, 곱셈 한 개)를 갖습니다. 종종 문제의 크기가 커지고 더 많은 변수가 다항식에 추가됨에 따라 수학적 변환이 문제의 크기를 단순화하고 줄이는 데 도움이 될 수 있습니다.

Valiant의 연구 후 몇 년 후, 컴퓨터 과학자들은 문제의 규모를 더 쉽게 분석할 수 있는 방법을 찾았습니다. 이를 위해 그들은 다항식이 합계와 곱을 전환하거나 번갈아 바꾸는 횟수를 지정하는 "깊이"라는 속성을 제안했습니다. 예를 들어, 다항식 x^2 + 2x + 1은 곱의 합(예: x^2 및 2x)이기 때문에 깊이가 2입니다. 반면 (x + 1)(x + 1) 표현식은 곱의 합으로 계산된 0 + (x + 1)(x + 1)과 깊이가 같기 때문에 깊이가 3입니다.

다항식을 단순화하기 위해 컴퓨터 과학자들은 문제가 커져도 합계와 곱의 패턴이 변하지 않는 "일정 깊이"라는 속성을 사용하여 다항식을 고정된 형식으로 제한합니다. 이로 인해 다항식의 크기가 깊이가 증가함에 따라 감소하면서 크기가 더욱 고정됩니다. 일정한 깊이에 대한 표현식을 공식이라고 합니다. 일정한 깊이를 사용하면 다항식 연구를 더 많이 진행할 수 있습니다.

마법의 "깊이"

1996년 Nisan과 Wigderson의 논문은 행렬 곱셈 문제를 해결하는 데 중점을 두었습니다. 그들은 이 문제를 두 가지 방법으로 단순화했습니다. 첫째, 그들은 일정한 깊이, 즉 깊이 3에 대한 공식을 사용하여 표현합니다. 둘째, 그들은 각 변수의 최대 지수가 1인 간단한 구조의 공식만 고려했는데, 이는 원래 문제를 "다중 선형" 문제로 만듭니다.

컴퓨터 과학자들은 다항식 크기가 기하급수적으로 증가하는 대신(지수 증가율과 비교하여) 특정 문제가 상대적으로 단순한 집합 다중 선형 구조로 변환될 수 있음을 발견했습니다.

Nisan과 Wigderson은 나중에 행렬 곱셈 문제를 행렬이 커짐에 따라 해결하는 데 기하급수적인 시간이 걸린다는 사실을 보여주었습니다. 즉, 중요한 문제는 어렵다는 것을 보여주고, 어떤 종류의 문제는 어렵다는 것을 보여주려고 노력한다. 그러나 그 결과는 단순하고 집합적인 다중 선형 구조를 갖는 공식에만 적용됩니다.

Leslie Valiant

다항식의 깊이를 늘리면 크기가 감소하는 경향이 있습니다. 시간이 지남에 따라 컴퓨터 과학자들은 이 두 속성 간의 균형을 더욱 정확하게 만들었습니다. 그들은 깊이 3에 두 가지 깊이 수준을 추가하면 앙상블 다중선형 다항식이 앙상블 다중선형 구조의 크기 이득의 균형을 맞출 수 있음을 보여줍니다. 깊이 5의 구조화된 수식에 기하급수적인 시간이 걸리면 일반적이고 구조화되지 않은 특성의 깊이 3 수식도 마찬가지입니다.

Srikanth Srinivasan et al.의 새로운 연구에서는 행렬 곱셈 문제의 심층 5세트 다중선형 공식이 실제로 기하급수적인 속도로 증가한다는 것을 보여줍니다. 이는 일반적인 깊이 3 공식에도 기하급수적인 시간이 걸린다는 것을 의미합니다. 그런 다음 그들은 유사한 패턴이 모든 깊이(단지 3과 5가 아님)에 적용된다는 것을 보여주었습니다. 이 관계를 통해 그들은 동일한 문제에 대한 모든 깊이의 일반 공식의 크기가 문제의 크기에 따라 기하급수적으로 증가한다는 것을 보여주었습니다.

또한 깊이가 무엇이든 일정한 깊이를 갖는 공식으로 행렬 곱셈을 표현하는 것이 어렵다는 것을 보여줍니다.

이 연구의 결과는 산술 문제가 "어려운" 경우, 즉 상수 심도 공식으로 표현될 수 없는 경우에 대한 최초의 일반적인 이해를 제공합니다. 행렬 곱셈의 특정 문제는 VP 문제로 알려져 있습니다. 그리고 VP 문제는 일정한 깊이에 국한되지 않으면 상대적으로 쉬운 것으로 알려져 있는데, 일정한 깊이가 문제의 '난이도'의 원인인 것으로 밝혀졌다.

VNP 문제는 VP 문제보다 어렵나요? 새로운 결과는 이를 직접적으로 보여주지 않고 단지 일정한 깊이 공식이 어렵다는 것을 보여줍니다. 그러나 이는 VNP 문제가 VP 문제와 동일할 수 없음을 입증하는 데 있어 여전히 중요한 이정표입니다.

더 큰 P 대 NP 문제의 경우 언젠가 답을 찾을 수 있을 것이라는 점을 이제 더 낙관할 수 있습니다. 결국 어려운 문제를 해결하기 위해서는 먼저 어느 방향이 절망적인지 알아야 한다.

위 내용은 문제가 VPN 문제인지 어떻게 증명할 수 있나요? 컴퓨터 과학자들이 간단한 방법을 찾았습니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!