이 "유효한 수학적 표현"문제 P 또는 NP입니까?

Question

이 질문은 순전히 호기심에서 벗어납니다. 나는 여름 동안 학교를 떠나고 재미를 위해 이것을 해결하기 위해 알고리즘을 구현하려고했습니다. 위의 질문으로 이어졌습니다.이 문제는 얼마나 어려운가요?

문제 : 긍정적 인 정수 목록, 수학 연산자 세트 및 동일한 부호 (=)가 제공됩니다. 정수 (동일한 순서로)와 연산자 (몇 번이나)를 사용하여 유효한 수학 표현식을 만들 수 있습니까?

예를 들어 질문을 명확히해야합니다.

주어진 : {2, 3, 5, 25}, {+, -, *, /}, {=}
출력 : 예

표현 (내가 생각하는 것만)은 (2 + 3) * 5 = 25입니다. 예/아니오 만 출력하면됩니다.

나는 문제가 NP에 있다고 믿는다. 나는 결정 문제 (예/아니오 답변)이기 때문에 이것을 결정하는 비 결정적 폴리 시간 알고리즘을 찾을 수 있습니다.

ㅏ. 정수 사이에 배치 할 일련의 연산자를 비 결정적으로 선택하지 않습니다.
비. 답변이 유효한 수학적 표현인지 확인하십시오 (이것은 일정한 시간에 수행 할 수 있음).

이 경우 가장 큰 문제는 이것입니다. p의 문제입니까? (즉, 결정을 결정하는 결정 론적 폴리 시간 알고리즘이 있습니까?) 문제 NP가 완료됩니까? (즉, 알려진 NP 완전한 문제를 이것으로 줄일 수 있습니까? 아니면 모든 NP 언어 폴리 시간 시간 이이 문제로 축소 될 수 있습니까?) (즉, NP의 문제이지만 NP는 완료되지 않습니다)

참고 :이 문제 설명은 p가 NP와 같지 않다고 가정합니다. 또한 스택 오버플로를 처음 접했지만 숙제 태그에 익숙합니다. 이것은 실제로 숙제가 아니라 호기심입니다 :)

Answer 1

에서 간단한 감소 파티션 문제 (NP- 완성) -N 정수 세트가 주어지면 "유효한 수학"문제에 대한 입력은 S, N -2 '+'연산자의 요소 및 '='부호입니다.

Answer 2

NP- 완전성을 확인하는 방법에 대해 어떤 종류의 혼란이있는 것 같습니다. NP- 완료 문제는 적어도 특히 NP의 다른 문제와 마찬가지로 적어도 어렵습니다. 일부 포스터가하려고하는 것처럼 우리가 3SAT와 비교하고 있다고 가정합니다.

이제 주어진 문제를 3SAT로 줄이는 것은 아무것도 증명하지 않습니다. 그러면 3SAT가 효율적으로 해결 될 수 있다면 (P = NP를 의미) 주어진 문제를 효율적으로 해결할 수 있습니다. 그러나 주어진 문제를 효율적으로 해결할 수 있다면 아마도 3SAT의 쉬운 특수 사례에만 해당됩니다.

주어진 문제로 3SAT를 줄여야합니다. 이는 주어진 문제의 해결책이 3SAT 문제를 해결하는 방법을 알려줄 수 있도록 임의의 3SAT 문제를 주어진 문제의 예로 변환하기위한 규칙을 구성해야한다는 것을 의미합니다. 이것은 3SAT가 주어진 문제보다 어려울 수 없음을 의미합니다. 3SAT가 가장 어려운 것이기 때문에 주어진 문제도 가장 어려워야합니다.

파티션 문제의 감소는 작동합니다. 그 문제는 다음과 같이 작동합니다. 다중 세트의 정수가 주어지면, 우리는 이것을 분리 된 서브 세트의 합이 동일하도록 각각의 멤버를 포함하는 두 개의 분리 서브 세트로 나눌 수 있습니까?

이를 위해, 우리는 0으로 시작하여 S의 각 요소를 포함하고 0으로 시작한 시퀀스를 구성합니다. 그런 다음 0은 {+, -}를 조작 세트로 사용합니다. 이는 S의 각 요소가 총 0에 추가되거나 빼면 첨가 된 요소의 합이 빼낸 요소의 합과 동일하다는 것을 의미합니다.

따라서이 문제는 적어도 파티션 문제만큼 어렵습니다. 주어진 프로그램을 해결할 수 있다면 예제 파티션 프로그램을 해결할 수 있으므로 NP가 완성되기 때문입니다.

Answer 3

자, 먼저 정수의 "세트"를 지정하지만 세트는 정의에 따라 정의되지 않으므로 정수의 "목록"을 의미합니다.

또한, 나는 여기서 잘못 될 수있는 가정을 할 것입니다. 즉, = 부호는 항상 두 번째부터 마지막과 마지막 정수 사이에 정확히 한 번 나타납니다. 가운데에 Equals 부호를 허용하면 더 복잡해집니다.

다음은 "유효한 수학적 표현"(VME)이 NP 완료라는 실제 증거입니다. 우리는 감소 할 수 있습니다 서브 세트 합계. Wikipedia의 서브 세트 합계 정의는 서브 세트가 비어 있지 않아야합니다. 실제로, 원하는 합이 입력의 일부인 경우 빈 하위 세트를 허용하는 서브 세트 합의보다 일반적인 문제는 NP 완료라는 것이 사실입니다. 요청하지 않으면 그 증거를주지 않을 것입니다. 서브 세트 합계의 인스턴스가 주어지면 {i_1, i_2, ..., i_n} 원하는 합과 함께 s, VME의 다음 인스턴스를 만듭니다.

{0, i_1, 0, i_2, 0, ..., i_n, s}, {+, *}, {=}

서브 세트 합계의 인스턴스가 해결 가능한 경우 정수가 0으로 추가되는 일부 하위 집합이 있습니다. 정수 인 경우 i1 합의 일부이며 해당 0 (왼쪽에 즉시)으로 추가하고 i1 합계의 일부가 아니라 곱하십시오. 각 0과 오른쪽에있는 용어 사이에 추가 부호를 삽입하십시오.

Wikipedia 예제를 취합니다

{−7, −3, −2, 5, 8}

어디 { −3, −2, 5} 합계는 0으로, 우리는 그것을 인코딩합니다

{0, -7, 0, -3, 0, -2, 0, 5, 0, 8, 0}

그리고 결과적인 표현이 될 것입니다

{0*7 + 0 + -3 + 0 + -2 + 0 + 5 + 0*8 = 0}

이제이 VME 인스턴스에 대한 모든 솔루션이 서브 세트 합계에 대한 솔루션을 초래 함을 보여 주어야합니다. 이것은 당신이 생각하는 것보다 쉽습니다. 결과적인 표현식을 살펴보면 숫자를 0으로 곱한 숫자 (체인 곱셈의 일부 포함)와 그렇지 않은 숫자로 그룹화 할 수 있습니다. 0을 곱한 숫자는 최종 합에 포함되지 않습니다. 0을 곱하지 않은 숫자는 최종 합에 추가되어야합니다.

따라서이 VME 인스턴스는 서브 세트 합의 해당 인스턴스가 해결 가능한 경우에만 해결 가능하므로 감소가 완료된 경우 해결 가능하다는 것을 보여주었습니다.

편집하다: 파티션 감소 (주석과 함께)도 작동하며, Equals 사인을 어디에나 넣을 수 있기 때문에 더 좋습니다. 정돈된!

Answer 4

지금 당장 전체 답변을 할 시간이 없지만이 문제에서 감소를 설명 할 수 있습니다. 배낭 문제.

동적 프로그래밍을 사용하여 달성 할 수 있습니다 의사 폴리 언어 시간 솔루션. 이것에 주목하십시오 충돌하지 않습니다 문제가 실제로 NP가 완료되었다는 사실로.

Answer 5

NP를 완료하려면 만족 해야하는 두 가지 속성이 있습니다.

의사 결정 문제 C는 다음과 같은 if np- 완료입니다.

1. C는 NP에 있으며
2. NP의 모든 문제는 다항식 시간에 C로 환원 가능합니다.

우리는 1을 확립했습니다. 2는 NP의 모든 문제가 3SAT로 환원 될 수 있고 3SAT가 현재 문제로 환원 될 수 있다는 사실로부터 결과를 확립했습니다.

따라서 NP- 완성입니다.

(편집) 아래 의견에 대한 답변 :

나는 SAT가 현재 문제로 축소 가능하다는 것을 증명할 것이며, 3SAT는 SAT가 환원 될 수 있으므로 결과는 다음과 같습니다.

입력 공식은 다음 표현식의 결합입니다.

(엑스₁ V x₂ V x₃ v ... x_N v y₁)

(엑스₁ V x₂ V x₃ v ... x_N v y₂)

(엑스₁ V x₂ V x₃ v ... x_N v y₃)

.

.

.

(엑스₁ V x₂ V x₃ v ... x_N v y₆₄)

각 y_나 모든 x 사이에 연산자의 순서가 무엇을 적용했는지에 따라 부울입니다._나입니다. 즉, y_나 총 4x4x4x4x1 값을 취할 수 있습니다 ( +, -, x, /만이 연산자이며 = 항상 마지막 연산자라고 가정합니다. 운영자 세트가 다른 연산자를 포함하도록 수정 된 경우 변경 될 수 있습니다).

표현이 사실이 없다면 완전한 표현식은 거짓으로 평가 될 것이며 가능한 모든 값, 즉 x를 대체하지 않으면 확인할 방법이 없습니다.₁ x를 통해_N n 숫자와 y로₁ Y를 통해₆₄ 운영자를 적용 할 수있는 다양한 방법으로 (주문 관리)

이 변환은 폴리 타임이며, 주어진 부울 공식은 수학적 표현이 유효한 경우 만족할 수 있습니다.

누구든지 결함이 있습니까?

Answer 6

이것은 실제로 당신의 복잡성 질문에 대한 답이 아니지만 당신의 문제는 약간 비슷합니다. 카운트 다운 문제. 빠른 검색 으로이 백서가 나타났습니다. http://www.cs.nott.ac.uk/~gmh/countdown.pdf

Answer 7

지금은 증거를 해결할 시간이 없지만, 직감은 그것이 P에 있지 않을 수 있다고 말합니다. 이 모든 터미널을 사용합니다. 나 믿다 그 문제는 NP에 있지만 P 이외의