부울 방정식 세트 보완

만약 n 비트 부울 방정식 세트가 있다면, 쉬운 방법이나 보완 집합을 얻는 알고리즘이 있습니까?부울 방정식 세트 보완

예를 들어 I (3 비트에 순열) U에서 설정 보완 얻을 수있는 쉬운 방법 {000010011100101,111}이다가, 3 비트 부울 식 세트 {110, 001}이 있다고?

감사합니다.

출처

2010-12-06 Ang

내 중요한 점은, 알고리즘이 기하 급수적으로 보인다 U.에서 설정을 뺄 수 있을까? – Ang

U의 원소 수는 n과 지수 함수 적으로 증가합니다. 즉, 원소의 수는 기하 급수적으로 증가 할 것입니다. – mbeckish

'n'(또는 'O (2^n)'에서 선형 적으로)의 지수 함수 인 알고리즘 (이 문제에 대한 알고리즘)은 없습니다. 여기서 n은 비트 수입니다. – NPE

전체 U (0에서 2^x - 1까지의 x는 비트 수)에서 실행하고 이미 가지고있는 것을 생략하십시오. 당신은 그들을 평등을 더 빨리 확인하기 위해 숫자로 변환 할 수 있습니다.

출처

2010-12-06 18:28:23 Andrey

그러나 x가 상당히 큰 경우 알고리즘은 기하 급수적입니까? 그것을 피할 수있는 방법이 있습니까, 아니면 NPC입니까? 고맙습니다! – Ang

@koko - 문제는 기하 급수적으로 커지지 만 NP 완료는 아닙니다. 다른 개념. – mbeckish

@koko 좋아요, 그것은 기하 급수적입니다. 나를 위해 그것은 본질적으로 가장 빠른 방법처럼 보입니다. 그렇지 않으면 어떻게 그 요소를 얻을 수 있기 때문에? 숫자가 매우 큰 경우 (예 : 모든 숫자가 1 비트를 1 비트로 설정 한 경우) 미리 분석하여 루프의 사이클 양을 건너 뛸 수 있습니다. – Andrey

SET[] = {6, 1} 

for(i=0;i<N;i++) { 
if(!exists(SET)) { 
    add(i, COMPLEMENT_SET) 
} 
}

N = 2^N-1과 같은 뭔가 ...

출처

2010-12-06 18:30:21 lm2s

당신은 n이 증가 될 때

출처

2010-12-06 18:31:58 mbeckish

부울 방정식 세트 보완

답변

관련 문제