속성시험

컴퓨터 과학에서 의사결정 문제에 대한 속성 테스트 알고리즘은 입력에 대한 질의 복잡성이 문제의 인스턴스 크기보다 훨씬 작은 알고리즘이다.일반적으로 속성시험 알고리즘은 일부 조합구조 S(그래프나 부울함수 등)가 일부 속성 P를 만족하는지 또는 이 속성을 갖는 것과 "멀리"인지를 구별하는데 사용된다. 즉, S를 만족시키기 위해 S를 만족시키기 위해 S를 수정해야 한다는 것을 의미한다.개체에 대한 "로컬" 쿼리 수입니다.^[1]^[2]

예를 들어, 다음과 같은 약속 문제는 쿼리 복잡성이 인스턴스 크기(임의 상수 > > 0)와 독립적인 알고리즘을 허용한다.

"n 정점에 대한 그래프 G를 보면, G의

\epsilon {\tbinom {n}{2}}

(

\epsilon {\tbinom {n}{2}}

2

){\

2}}개의 가장자리에서

\epsilon {\tbinom {n}{2}}

임의의 부분집합을 제거한 후에도 G가 초당적인지 여부를 결정하라."

확률적으로 확인할 수 있는 증거는 본질적으로 속성 시험 알고리즘에 의해 검증될 수 있는 증명이기 때문에 속성 시험 알고리즘은 확률적으로 검사 가능한 증빙의 정의의 중심이다.

정의 및 변형

공식적으로, 의사결정 문제 L에 대한 쿼리 복잡성 q(n)과 근접 매개변수 ε을 가진 속성 시험 알고리즘은 입력 x (L의 인스턴스)에서 최대 q( x ) 쿼리를 x에 하고 다음과 같이 동작하는 임의화된 알고리즘이다.

x가 L에 있으면 알고리즘은 최소한 probability의 확률로 x를 받아들인다.
x가 L에서 ε-멀면 알고리즘은 최소한 ⅔의 확률로 x를 거부한다.

여기서 "x는 L에서 멀리 떨어져 있다"는 것은 l에서 x와 임의의 문자열 사이의 해밍 거리가 적어도 ε x임을 의미한다.

속성시험 알고리즘은 인스턴스(instance) x ∈ L에 대한 수용 확률을 instead 대신 1로 하는 강한 조건을 만족하는 경우 단측 오차를 갖는다고 한다.

속성 테스트 알고리즘은 이전 쿼리에 대한 답을 "구제"하기 전에 모든 쿼리를 수행할 경우 적응성이 떨어진다고 한다.그러한 알고리즘은 다음과 같은 방식으로 작동하는 것으로 볼 수 있다.먼저 알고리즘이 입력을 수신한다.입력을 보기 전에 알고리즘은 내부 랜덤성을 사용하여 어떤 입력을 쿼리할 지 결정한다.다음으로 알고리즘은 이러한 기호를 관찰한다.마지막으로 추가 쿼리를 하지 않고(그러나 임의성을 사용하여) 알고리즘은 입력의 수락 여부를 결정한다.^[1]

특징 및 제한 사항

속성 시험 알고리즘의 주요 효율성 매개변수는 쿼리 복잡성으로, 주어진 길이의 모든 입력(및 알고리즘에 의해 이루어진 모든 임의 선택)에 대해 검사된 입력 기호의 최대 수입니다.하나는 쿼리 복잡성이 가능한 한 작은 알고리즘 설계에 관심이 있다.많은 경우에 속성 시험 알고리즘의 실행 시간은 인스턴스 길이의 하위 선형이 된다.일반적으로 먼저 인스턴스 크기 n의 함수처럼 가능한 한 쿼리 복잡성을 작게 만든 다음 근접 파라미터 ε에 대한 의존성을 연구하는 것이 목표다.

다른 복잡성-이론적 설정과는 달리, 속성 시험 알고리즘의 점증적 질의 복잡성은 인스턴스(instance)의 표현에 의해 극적으로 영향을 받는다.예를 들어 ε = 0.01일 때 밀도 그래프의 초당성 테스트 문제(접근 행렬로 표현됨)는 일정한 쿼리 복잡성의 알고리즘을 허용한다.반대로 n 정점의 희소성 그래프(접근성 목록으로 표시됨)는 쿼리 복잡성 $\Omega ({\sqrt {n}})$ ) $\Oomega({\sqrt{n})$ 의 속성 테스트 알고리즘을 필요로 한다 $\Omega ({\sqrt {n}})$

속성 시험 알고리즘의 질의 복잡성은 근접 매개변수 ε가 모든 비삼각적 특성에 대해 작아질수록 증가한다.입력에서 ε 미만의 기호를 변경하는 것은 O(1/312) 이하의 질의를 사용하여 일정한 확률로 검출할 수 없기 때문에 on에 대한 이러한 의존성이 필요하다.밀도가 높은 그래프의 많은 흥미로운 속성은 그래프 크기 n이 아닌 ε에만 의존하는 쿼리 복잡성을 사용하여 테스트할 수 있다.그러나 질의 복잡성은 ε의 함수로서 엄청나게 빠르게 성장할 수 있다.예를 들어, 그래프가 삼각형을 포함하지 않는지 여부를 테스트하기 위한 가장 잘 알려진 알고리즘은 폴리(1/320)의 타워 함수인 쿼리 복잡성을 가지고 있었고, 2010년에야 이것은 로그(1/320)의 타워 함수로 개선되었다.이 엄청난 한계 성장의 이유 중 하나는 그래프의 속성 테스트에 대한 많은 양의 결과가 Szemerédi 정규성 보조정리기를 사용하여 설정되기 때문인데, 결론에 타워형 경계도 있다.Szemerédi 정규성 보조정리 및 관련 그래프 제거 보조정리 보조정리부와의 속성시험의 연결은 아래에 자세히 설명되어 있다.

그래프 속성 테스트

정점이 없는 그래프 G의 경우, 우리가 사용할 거리의 개념은 편집 거리 입니다.즉, $\varepsilon n^{2}$ ${\$ n $^{2}}$ 개의 $\varepsilon n^{2}$ 가장자리를 추가 및/또는 삭제할 수 있고 첫 번째 그래프에서 두 번째 그래프까지 얻을 수 있을 정도로 두 그래프 사이의 거리가 가장 작다고 말한다.그래프의 합리적인 표현에서 이것은 이전의 해밍 거리 정의와 동등하다(아마도 상수의 변경까지).

그래프 맥락에서 속성 시험의 일반적인 개념을 정확하게 만들기 위해, 그래프 속성 P의 시험자는 최소한 G 만족 사례와 G 만족도가 P 만족도와 편집 거리가 먼 사례 사이의 확률로 구별해야 한다.검사자는 일부 Oracle에 액세스하여 한 쌍의 꼭지점 사이에 엣지가 있는지 여부를 G로 쿼리할 수 있다.쿼리 복잡성은 이러한 오라클 쿼리의 수입니다.검사자가 잘못된 긍정이 아니라 단측 오류가 있으며, 즉, G가 P를 만족하면 검사자가 항상 정답을 출력한다고 가정하십시오.^[3]^[4]

P를 만족시키는 그래프와 만족하지 않는 그래프만 구별할 수 있다.후자의 경우 두 개의 그래프를 고려하십시오. G 만족도 P와 H 만족도가 몇 개의 가장자리만 변경하여 P를 만족하지 않음.하나의 예는 정확히 하나의 삼각형이 있는 그래프와 이러한 가장자리 중 하나가 제거된 G를 H로 삼각형 자유도를 테스트하는 것이다.그러면 검사자는 모든 에지를 조사하지 않으면 그들을 구분할 수 없고, 그렇게 할 수 없다.

짧은 역사

그래프 속성 검사 분야는 골드리치, 골드웨서, 론 등이 처음 도입했다.1998년에 발간된 그들의 논문에서 추상적인 그래프 파티션 문제를 분석하고 몇몇 테스터를 제공했다.여기에는 초당성, k-색상성, 큰 패거리, 큰 컷과 같은 몇 가지 중요한 그래프 속성이 포함된다.^[3] 특히 하위 그래프를 표본으로 추출하여 속성을 만족하는지 확인하는 자연 알고리즘은 비록 차선의 쿼리 복잡성이 있더라도 모두 정확하다.

그 이후 여러 건의 관련 발견이 이루어졌다.

1992년 알론, 듀크, 레프만, 뢰들, 유스터는 모든 그래프 H에 대해 하위그래프로서 H를 포함하지 않는 속성이 시험 가능하다는 것을 보여주었다.^[5]
1999년, 알론, 피셔, 크리벨레비치, 스제게디는 모든 그래프 H에 대해 유도 하위그래프로서 H를 포함하지 않는 속성이 시험 가능하다는 것을 보여주었다.^[6]
2005년에 알론과 샤피라는 모든 모노톤 그래프 속성(정점 및 가장자리 삭제 시 보존되는 속성)이 단측 오류로 테스트 가능하다는 것을 보여주었다.^[7]
2008년 알론과 샤피라는 모든 유전적 그래프 속성에 대해 일방적인 오류가 있는 테스터를 전시했다.그들은 또한 테스트하기 쉬운 성질을 특징으로 했다.즉, 이러한 자연적 성질은 반계통적이다.이 진술들은 아래에서 더 명확하게 밝혀질 것이다.^[1]

유전형 그래프 속성 테스트

그래프 속성은 정점을 삭제한 상태에서 보존되는 경우 세습되며, 유도 하위 그래프를 사용하여 보존되는 경우 세습되므로 이름이 세습된다.몇 가지 중요한 유전적 특성은 H-자유도(일부 그래프 H의 경우), k-색상성 및 평면성이다.모든 유전적 성질은 테스트할 수 있다.

정리(Alon & Shapira 2008).모든 유전적 그래프 속성은 일방적인 오류로 테스트할 수 있다.^[1]

그 증거는 무한대의 유도 서브그래프를 위한 그래프 제거 보조정리 버전에 의존한다.우리는 증거도 없이 여기서 정리를 재현한다.특히 상수 $h_{0}$ $h_{0}$ ${\$ 은(는) 샘플 크기로 자연스럽게 올라오는 $h_{0}$ 점에 유의한다.또한 이 규칙성 접근법을 이용한 질의 복잡성은 스제메레디 규칙성 보조정리(Szemerédi regularity)에 묶인 탑 기능 때문에 크다.

정리(무한 그래프 제거 보조정리).그래프 H{\displaystyle{{H\mathcal}의 각(아마도 무한한)}}과ε>0{\displaystyle \varepsilon>0}, h0{\displaystyle h_{0}}과δ>이하로 0{\displaystyle \delta>0}이 G{G\displaystyle}은 n{n\displaystyle}-vertex 그래프 존재한다. δ nv(H

\delta n^{v(H)}

copies of

H

for every

H\in {\mathcal {H}}

with at most

h_{0}

vertices, then

G

can be made induced

{\mathcal {H}}

-free by adding/removing fewer than

\varepsilon n^{2}

\varepsilon n^{2}

개의 가장자리

\varepsilon n^{2}

.^[8]

망각 테스터

비공식적으로, 망각 테스터는 입력의 크기를 망각한다.그래프 속성 P의 경우 매개변수 and과 그래프 G를 입력으로 취한 후 G에 정확히 Q(ε) 쿼리를 하는 근접 매개변수 ε으로 속성 P에 대한 속성 테스트 알고리즘으로 실행하는 알고리즘이다.

정의.망각 테스터는 매개변수 ε을 입력하는 알고리즘이다.정수 q(()를 계산한 다음 임의로 균일하게 선택한 G에서 정확히 q(() 정점에 대해 유도 서브그래프 H를 Oracle에 요청한다.그런 다음 ε과 H에 따라 (아마 임의로) 받아들이거나 거부한다.우리는 그것이 속성 P를 가진 G에 대해 적어도 확률로 수용하고, 속성 P와 거리가 먼 확률로 거부한다면 속성 P를 시험한다고 말한다.

결정적으로, 망각 테스터가 하는 쿼리 수는 입력 그래프 G의 크기가 아니라 ε에만 의존하는 상수다.속성 시험 알고리즘과 완전히 유사하게, 우리는 일방적 오류가 있는 망각 테스터에 대해 이야기할 수 있다.

반열 그래프 속성 테스트

우리는 그것에 대한 테스터가 정점의 수에 접근해야 하는 몇몇 그래프 속성을 확실히 조작할 수 있다.여기 한 예가 있어요.

예.G 그래프는 짝수 정점과 쌍방향이거나 홀수 정점으로 완벽하다면 속성 P를 만족시킨다.^[1]

이 경우 검사자는 정점의 개수를 알지 못하는 한 어떤 속성(양극성 또는 완전성)을 검사해야 하는지도 구별할 수 없다.그런 부자연스러운 성질의 예는 얼마든지 있다.사실, 일방적인 오류로 망각한 테스터가 테스트할 수 있는 그래프 속성의 특성화는 자연 속성의 한 종류로 이어진다.

정의.만약 H가 어떤 그래프고, 모든 ε 을에 P가 H를 충족시키면;0{\displaystyle \varepsilon>0}이 M(ε)은{M(\varepsilon)\displaystyle}가 크기의 모든 그래프 적어도 M(ε){M(\varepsilon)\displaystyle}은 유전적인 그래프 속성이 있는 그래프 속성 Hsemi-hereditary 있다. ε-far만족 P로부터 H를 만족시키지 못하는 유도 하위 그래프를 포함한다.

세습적 속성도 사소한 것으로는 반계승적이다.이 특성화는 위의 다른 알론 & 샤피라 정리와의 정반대로 부분적으로 답한다: 성질을 테스트하기 쉬운 성질(일방적인 오류가 있는 망각 테스터를 갖는 것)은 거의 유전적이다.같은 신문에서 그들은

정리(Alon & Shapira 2008).그래프 속성 P는 P가 반계통인 경우에만 망각적인 단측 오류 테스터를 가지고 있다.^[1]

예제: 일부 그래프 속성 테스트

이 절에서는 삼각 자유도, 초당성 및 k-색상성에 대한 단측 오차가 있는 자연 망각 테스트 알고리즘을 제공한다.그것들은 우리가 G의 정점 X의 일부 부분집합 X를 무작위로 추출하고 그래프 속성이 X에 의해 확장된 하위 그래프에 잡히는지 확인하는 자연스러운 생각을 따른다는 점에서 자연스러운 것이다.우리는 이러한 속성들이 실제로 유전적이기 때문에 일방적인 오류를 가지고 있다: 만약 G가 속성을 만족한다면, X에 의해 확장된 유도 서브그래프도 그렇게 해야 하기 때문에 우리의 검사자는 항상 이를 받아들인다.

삼각형 자유도를 위해 테스터는 삼각형 제거 보조정리기를 응용한 것이다.특히 그래프 G가 삼각형이 없는 것과 거리가 먼 경우, G가 $\delta n^{3}$ $\delta n^{3}$ 3 ${\$ \ $delta$ =\delta =\ $delta$ (\ $varepsilon )}$ 의 삼각형이 $\delta n^{3}$ 있도록 (컴퓨팅 $\delta =\delta (\varepsilon )$ 가능한) 상수 Δ = $\delta =\delta (\varepsilon )$ = $\delta =\delta (\varepsilon )$ = Δa =\ $delta n^{3}}}$ 의 삼각형이 있음을 알려준다.

예(삼각-자유도 테스트 알고리즘).
주어진 그래프 G에서 $q(\varepsilon )=1/\delta$ ) $q(\varepsilon )=1/\delta$ = $q(\varepsilon )=1/\delta$ / $(\displaystyle q(\varecsilon )=1/\delta }$ 의 정점 세 배를 $q(\varepsilon )=1/\delta$ 임의로 선택한다. 여기서 Δ는 위와 같다.

X에서 정점의 세 쌍마다 정점의 세 쌍이 모두 G에 인접해 있는지 쿼리한다.

알고리즘은 정점의 세 배가 삼각형을 유도하지 않으면 받아들이고, 그렇지 않으면 거부한다.^[9]

초당성과 k-색상성을 위해 Δ를 다음 테스터에 대한 오차 확률을 원하는 상한이 되도록 한다.기, 쿼리 복잡성을 실행 시간과 혼동해서는 안 된다.후자는 유도 서브그래프의 위주성을 시험하기 위한 다항 시간 결정 알고리즘이 부족하기 때문에 (두 경우 모두와 마찬가지로) 지수적인 경우가 많다.우리는 대신 무차별적인 수색으로 확인한다.^[3]

예(Bipartite Testing 알고리즘).
지정된 그래프 G에서 $q(\varepsilon )=O(\log(1/(\varepsilon \delta ))/\varepsilon ^{2})$ $q(\varepsilon )=O(\log(1/(\varepsilon \delta ))/\varepsilon ^{2})$ ) $q(\varepsilon )=O(\log(1/(\varepsilon \delta ))/\varepsilon ^{2})$ = $q(\varepsilon )=O(\log(1/(\varepsilon \delta ))/\varepsilon ^{2})$ $q(\varepsilon )=O(\log(1/(\varepsilon \delta ))/\varepsilon ^{2})$ ( $q(\varepsilon )=O(\log(1/(\varepsilon \delta ))/\varepsilon ^{2})$ / ( $q(\varepsilon )=O(\log(1/(\varepsilon \delta ))/\varepsilon ^{2})$ ) $q(\varepsilon )=O(\log(1/(\varepsilon \delta ))/\varepsilon ^{2})$ 2 $q(\varepsilon )=O(\log(1/(\varepsilon \delta ))/\varepsilon ^{2})$ ) ${\displaystyle q(\varecpsilon )=O(\log(1/(\varecpsilon \delta )/\varecpsilon ^{2}})$ 정점을 $q(\varepsilon )=O(\log(1/(\varepsilon \delta ))/\varepsilon ^{2})$ 랜덤 집합으로 선택하십시오.

X의 모든 꼭지점 쌍에 대해, 그것들이 G에 인접해 있는지 쿼리한다.

X에 있는 G의 유도 서브그래프가 초당적이라면 받아들이고, 그렇지 않으면 거부한다.^[3]

예(k-색상성 테스트 알고리즘).
주어진 그래프 G에서 $q(\varepsilon )=O(k^{4}\log ^{2}(k/\delta )/\varepsilon ^{3})$ ( $q(\varepsilon )=O(k^{4}\log ^{2}(k/\delta )/\varepsilon ^{3})$ ) $q(\varepsilon )=O(k^{4}\log ^{2}(k/\delta )/\varepsilon ^{3})$ = $q(\varepsilon )=O(k^{4}\log ^{2}(k/\delta )/\varepsilon ^{3})$ ( k $q(\varepsilon )=O(k^{4}\log ^{2}(k/\delta )/\varepsilon ^{3})$ $q(\varepsilon )=O(k^{4}\log ^{2}(k/\delta )/\varepsilon ^{3})$ $q(\varepsilon )=O(k^{4}\log ^{2}(k/\delta )/\varepsilon ^{3})$ $q(\varepsilon )=O(k^{4}\log ^{2}(k/\delta )/\varepsilon ^{3})$ ( $q(\varepsilon )=O(k^{4}\log ^{2}(k/\delta )/\varepsilon ^{3})$ / $q(\varepsilon )=O(k^{4}\log ^{2}(k/\delta )/\varepsilon ^{3})$ ) $q(\varepsilon )=O(k^{4}\log ^{2}(k/\delta )/\varepsilon ^{3})$ / $q(\varepsilon )=O(k^{4}\log ^{2}(k/\delta )/\varepsilon ^{3})$ $q(\varepsilon )=O(k^{4}\log ^{2}(k/\delta )/\varepsilon ^{3})$ ) ${\displaystyle q(\varecpsilon )=O(k^{4}\log ^{2}(k/\delta )/\varecpsilon ^{$ 3 $q(\varepsilon )=O(k^{4}\log ^{2}(k/\delta )/\varepsilon ^{3})$ }} 정점}}}의 랜덤 집합 X를 선택하십시오.

X의 모든 꼭지점 쌍에 대해, 그것들이 G에 인접해 있는지 쿼리한다.

X에 G의 유도 서브그래프가 k-컬러블이면 받아들이고, 그렇지 않으면 거부한다.^[3]

참조

^ ^a ^b ^c ^d ^e ^f ^g ^h Alon, Noga; Shapira, Asaf (2008). "A characterization of the (natural) graph properties testable with one-sided error" (PDF). SIAM Journal on Computing. 37: 1703–1727.
^ Goldreich, Oded (1999). "Combinatorial Property Testing (a survey)". Randomization Methods in Algorithm Design. 43: 45–59. ISBN 0821870874.
^ ^a ^b ^c ^d ^e Goldreich, Oded; Goldwasser, Shari; Ron, Dana (1 July 1998). "Property testing and its connection to learning and approximation". Journal of the ACM. 45 (4): 653–750. doi:10.1145/285055.285060.
^ Rubinfeld, Ronitt; Shapira, Asaf (2011). "Sublinear Time Algorithms". SIAM Journal on Discrete Mathematics. 25 (4): 1562–1588. CiteSeerX 10.1.1.221.1797. doi:10.1137/100791075.
^ Alon, N.; Duke, R. A.; Lefmann, H.; Rodl, V.; Yuster, R. (1 January 1994). "The Algorithmic Aspects of the Regularity Lemma". Journal of Algorithms. 16 (1): 80–109. doi:10.1006/jagm.1994.1005.
^ Alon, Noga; Fischer, Eldar; Krivelevich, Michael; Szegedy, Mario (1 April 2000). "Efficient Testing of Large Graphs". Combinatorica. 20 (4): 451–476. doi:10.1007/s004930070001.
^ Alon, Noga; Shapira, Asaf (22 May 2005). "Every monotone graph property is testable". Proceedings of the thirty-seventh annual ACM symposium on Theory of computing: 128–137. doi:10.1145/1060590.1060611.
^ Fox, Jacob (2010). "A new proof of the graph removal lemma". arXiv:1006.1300.
^ ^a ^b Goldreich, Oded (2017). Introduction to Property Testing. Cambridge University Press. ISBN 9781107194052.
^ Ron, Dana (2000). Property Testing (Technical report).

[as2008-1] ^ ^a ^b ^c ^d ^e ^f ^g ^h Alon, Noga; Shapira, Asaf (2008). "A characterization of the (natural) graph properties testable with one-sided error" (PDF). SIAM Journal on Computing. 37: 1703–1727.

[g1999-2] Goldreich, Oded (1999). "Combinatorial Property Testing (a survey)". Randomization Methods in Algorithm Design. 43: 45–59. ISBN 0821870874.

[ggr1998-3] Goldreich, Oded; Goldwasser, Shari; Ron, Dana (1 July 1998). "Property testing and its connection to learning and approximation". Journal of the ACM. 45 (4): 653–750. doi:10.1145/285055.285060.

[rs2011-4] Rubinfeld, Ronitt; Shapira, Asaf (2011). "Sublinear Time Algorithms". SIAM Journal on Discrete Mathematics. 25 (4): 1562–1588. CiteSeerX 10.1.1.221.1797. doi:10.1137/100791075.

[adlry1992-5] Alon, N.; Duke, R. A.; Lefmann, H.; Rodl, V.; Yuster, R. (1 January 1994). "The Algorithmic Aspects of the Regularity Lemma". Journal of Algorithms. 16 (1): 80–109. doi:10.1006/jagm.1994.1005.

[afks1999-6] Alon, Noga; Fischer, Eldar; Krivelevich, Michael; Szegedy, Mario (1 April 2000). "Efficient Testing of Large Graphs". Combinatorica. 20 (4): 451–476. doi:10.1007/s004930070001.

[as2005-7] Alon, Noga; Shapira, Asaf (22 May 2005). "Every monotone graph property is testable". Proceedings of the thirty-seventh annual ACM symposium on Theory of computing: 128–137. doi:10.1145/1060590.1060611.

[f2010-8] Fox, Jacob (2010). "A new proof of the graph removal lemma". arXiv:1006.1300.

[g2017-9] Goldreich, Oded (2017). Introduction to Property Testing. Cambridge University Press. ISBN 9781107194052.

[r2000-10] Ron, Dana (2000). Property Testing (Technical report).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

Search