부울 계층

부울 계층은 NP 세트의 부울 조합(교차, 결합 및 보완) 계층입니다.마찬가지로 부울 계층은 NP 술어에 대한 부울 회선의 클래스라고 할 수 있습니다.부울 계층이 축소되면 다항식 ^[1]계층이 축소됩니다.

형식적 정의

BH는 다음과 ^[2]같이 정의됩니다.

• BH는₁ NP입니다.
• BH는_2k BH의 언어와_2k-1 coNP의 언어가 교차하는 언어 클래스입니다.
• BH는_2k+1 BH의 언어와_2k NP의 언어를 결합한 언어 클래스입니다.
• BH는 BH의_i 결합이다.

파생 클래스

• DP(차이 다항식 시간)는₂ ^[3]BH입니다.

동등한 정의

클래스 연결 및 분리를 다음과 같이 정의하면 보다 콤팩트한 정의를 할 수 있습니다.두 클래스의 결합에는 첫 번째 클래스의 언어와 두 번째 클래스의 언어가 교차하는 언어가 포함됩니다.분리(disjection)는 교차로 대신 결합(union)과 유사한 방식으로 정의된다.

• C ∧ D = { A b B A c C B d D }
• C ∨ D = { A b B A c C B d D }

이 정의에 따르면 DP = NP co coNP이다.부울 계층의 다른 클래스는 다음과 같이 정의할 수 있습니다.

$({displaystyle {mathsf {BH}_{2k}={coNP}}\wedge {{mathsf {BH}}_{2k-1})$

$({displaystyle {BH}_{2k+1}={np}}\vee {mathsf {BH}}_{2k})$

부울 ^[4]계층 클래스의 대체 정의로 사용할 수 있는 등식은 다음과 같습니다.

$({displaystyle {mathsf {BH}_{2k}=\bigve_{i=1}^{k}{\mathsf {DP}})$

$({displaystyle {BH}_{2k+1}=bigvee_{i=1}^{k}{\mathsf {DP}})$

또는 ^[5]k ≤ 3마다:

$({displaystyle {mathsf {BH}_{k}=mathsf {DP}}\vee {mathsf {BH}}_{k-2})$

경도

임의의 NP-완전 문제 A의 인스턴스 수에서 감소를 나타내는 것으로, 부울 계층의 클래스의 경도를 증명할 수 있다.특히 시퀀스 {x₁}이(가) 주어집니다.x a A가 x a A를 의미하도록_ii-1 A 인스턴스의 x}는 x a A의 수가_i 홀수이거나 ^[4]짝수인 경우에만 y b B가 되는 인스턴스 y를 생성하는 감소가 필요합니다_m.

• bh-hardness는_2k m ${\displaystyle =}$ $(\displaystyle$ m$=2k)$이고 x µ A의 수가_i 홀수일 경우 $증명$된다.
• bh-hardness는_2k+1 m$=$ ${\displaystyle \mathrm{2k}}$ + ${\displaystyle 1}$({$displaystyle$ m$=2k+1})$이고 x µ A의_i 수가 짝수이면 $증명$된다.

이러한 감소는 모든 고정 k에 적용된다.임의의 k에 대해 이러한 감소가 존재한다면, P는^{NP[O(log n)]} 이 문제를 해결하기 어렵다.

레퍼런스