에서는 스레드 , Norbet 블룸의 시도 증거는 간결 Tardos 함수 정리 6 반례 것을 주목 반증한다.피≠ N피

$P\ne NP$

$P \neq NP$

정리 6 : 모노톤 부울 함수로합니다. CNF-DNF-approximator에 있다고 가정 A를 위해 하한을 증명하는 데 사용될 수 C를 m ( F ) . 그러면 A는 또한 행 같은 저급 증명하는 데 사용될 수 C S t ( F을 ) .에프∈ B엔

$f\in {\mathcal{B}}_n$

$f \in \mathcal{B}_n$에이

$\mathcal{A}$

$\mathcal{A}$기음엠( f)

$C_m(f)$

$C_m(f)$에이

$\mathcal{A}$

$\mathcal{A}$기음s t( f)

$C_{st}(f)$

$C_{st}(f)$

내 문제는 다음과 같습니다. Tardos 함수는 부울 함수가 아니므로 Theorem 6의 가설을 어떻게 충족합니까?

에서는 이 종이 , 그들 기능의 복잡성 논의 일반 정보 모노톤 부울 함수가 아닌, 증가 에지 할 수 있기 때문에, φ ( X를 ) 확인 큰 φ ( X ) ≤ F ( v ) 입력에서 1 이 적 으면 참입니다 . 함수 φ ( X ) ≥ f ( v ) 는 일반적 으로 T에서 1 을 계산하지 않습니다.φ (X) ≤ f( V )

$\phi (X)\le f(v)$

$\varphi(X) \leq f(v)$φ (X)

$\phi (X)$

$\varphi(X)$φ ( X) ≤ f( V )

$\phi (X)\le f(v)$

$\varphi(X) \leq f(v)$1

$1$

$1$φ ( X) ≥ f( V )

$\phi (X)\ge f(v)$

$\varphi(X) \geq f(v)$1

$1$

$1$T 0의 경우 1 과 0 입니다.티1

$T_1$

$T_1$0

$0$

$0$티0

$T_0$

$T_0$

실제로, 테스트 세트 및 T 0 정확하게 이렇게 계산하는 것이 선택되는 1 에서 T 1 및 0 에서 T 0 (그들이 경계 정의 단순성으로하는 정밀 CLIQUE 컴퓨팅에 함수를 의미 하나 의과 0 의하여 입력의 격자)), 따라서이 설명은 Tardos 기능이 CLIQUE와 동일하다는 것을 의미하며, 이는 사실이 아닙니다.티1

$T_1$

$T_1$티0

$T_0$

$T_0$1

$1$

$1$티1

$T_1$

$T_1$0

$0$

$0$티0

$T_0$

$T_0$1

$1$

$1$0

$0$

$0$

그러나 많은 사람들과 지식이 풍부한 사람들은 Tardos 기능이 즉각적인 반례를 제공한다고 주장하므로 누락 된 것이 있어야합니다. 이해 관계자이지만 귀하의 수준에 미치지 못하는 사람들에 대한 자세한 설명이나 증거를 제공해 주시겠습니까?

---

---

답변