선형 시스템의 최소 관련 변수

선형 시스템에서 Minimum 관련 변수(Min-RVLS)는 수학적 최적화의 문제다.선형 프로그램을 부여하면 0이 아닌 변수의 수가 가능한 한 적은 실현 가능한 해결책을 찾아야 한다.

이 문제는 NP-강력한 것으로 알려져 있으며 심지어 근사치조차 어려운 것으로 알려져 있다.

정의

Min-RVLS 문제는 다음과 같이 정의된다.^[1]

• 2진수 관계 R, 이것은 {=, ,, >, ≠} 중 하나이다.
• m-by-n 행렬 A(여기서 m은 제약 조건의 수, n 변수 수)
• m-by-1 벡터 b.

선형 시스템은 A x R b에 의해 주어진다.실현 가능한 것으로 가정한다(즉, 적어도 하나의 x로 만족한다).R에 따라 이 시스템에는 다음과 같은 4가지 변형이 있다.A x = b, A x ≥ b, A x > b, A x ≠ b.

목표는 시스템 A x R b를 만족하고 그에 따라 가능한 적은 수의 0이 아닌 원소를 포함하는 n-by-1 벡터 x를 찾는 것이다.

특수 케이스

Min-RVLS[=] 문제는 Garey와 Johnson에 의해 제시되었는데,^[2] 그는 이를 "선형 방정식에 대한 최소 무게 솔루션"이라고 불렀다.그들은 그것이 NP-hard라는 것을 증명했지만 근사치는 고려하지 않았다.

적용들

Min-RVLS 문제는 기계 학습과 선형 판별 분석에서 중요하다.일련의 긍정적인 예와 부정적인 예를 들어, 그것들을 정확하게 분류하는 데 필요한 특징의 수를 최소화해야 한다.^[3]이 문제는 최소 기능 집합 문제로 알려져 있다.$O{\displaystyle (\log }$log${\displaystyle }$(${\displaystyle m}$ )${\displaystyle$ O$(\log(m))}$의 계수 내에서 Min-RVLS에 근사치를 갖는 알고리즘은 주어진 정확도 수준을 달성하는 데 필요한 훈련 샘플의 수를 실질적으로 줄일 수 있다$$.^[4]

코딩 이론에서 가장 짧은 코드워드 문제는 계수가 GF(2)에 있을 때 Min-RVLS[=]와 같은 문제다.

관련 문제

Minimum 불만족 선형 관계(Min-ULR)에서는 2진수 관계 R과 선형 시스템 A x R b가 주어지는데, 현재 실현 불가능한 것으로 가정하고 있다.다른 모든 것을 만족시키면서 가능한 한 적은 수의 관계를 위반하는 벡터 x를 찾는 것이 목표다.

Min-ULR[limit]은 실제 변수와 제한된 수의 불평등 제약 조건을 가진 어떤 시스템도 실현 가능하기 때문에 사소한 해결이 가능하다.다른 세 가지 변종:

• Min-ULR[=,]는 균일한 계통과 양극 계수({1,-1}의 경우)가 있더라도 NP-hard이다.^[5]
• NP-완전한 문제 최소 피드백 아크 세트는 Min-ULR[min]로 감소하며, 각 제약조건에 정확히 1과 1 -1이 있으며, 모든 우측은 1과 같다.^[6]
• Min-ULR[=, )는 n개의 변수가 일정하다면 다항식이다: 시간 O${\displaystyle (n}$ ${\displaystyle \cdot }$ m${\displaystyle {}^{}{n}^{}}$ / ${\displaystyle 2^{}}$ n${\displaystyle {}^{}}$- ${\displaystyle 1^{}}$) ${\displaystyle$ O$(n\cdot$ m$^{n}/2^{n-1})$를 사용하여^[7] 다항식으로 해결할 수 있다$.$
• 최소-ULR[=,]은 모든 하위 시스템을 O(n) 시간에 확인할 수 있기 때문에 제약 조건 m의 수가 일정하면 선형이다.
• Min-ULR[[]은 특수한 경우 다항식이다.^[6]
• Min-ULR[=,]는 다항 시간에서 n + 1 이내에 근사치를 구할 수 있다.^[1]
• 최소-ULR[]은 균일한 시스템 및 3차 계수({-1,0,1})를 사용하더라도 최소 배율 설정 하드다.
• Min-ULR[=] cannot be approximated within a factor of ${\displaystyle 2^{\log ^{1-\varepsilon }n}}$, for any ${\displaystyle \varepsilon >0}$, unless NP is contained in DTIME(${\displaystyle n^{\operatorname {polylog} (n)}}$).^[8]

보완적 문제에서 최대 실현 가능한 선형 서브시스템(Max-FLS)의 목표는 동시에 충족될 수 있는 제약조건의 최대 하위 집합을 찾는 것이다.^[5]

• Max-FLS[max-FLS]는 다항식 시간 내에 해결할 수 있다.
• Max-FLS[=]는 균질 계통과 양극 계수가 있는 경우에도 NP-hard이다.

• . 정수계수로는 $m{\displaystyle {}^{}}$ ${\displaystyle {\epsilon }^{}}$ ${\$의 근사치가 어렵다$.$ GF[q] 이상의 계수는 q-tammable이다.
• Max-FLS[]와 Max-FLS[192]는 균질 계수와 양극 계수가 있는 경우에도 NP-hard이다.이 값은 2-약식이지만 더 작은 상수 요인 내에서 근사치를 계산할 수 없다.

근사 경도

4가지 유형의 Min-RVLS는 모두 근사치하기가 어렵다.In particular all four variants cannot be approximated within a factor of ${\displaystyle 2^{\log ^{1-\varepsilon }n}}$, for any ${\displaystyle \varepsilon >0}$, unless NP is contained in DTIME(${\displaystyle n^{\operatorname {polylog} (n)}}$).^{[1]: 247–250} 경도는 감소를 통해 증명된다.

• Min-ULR[=]에서 Min-RVLS[=]로 감소가 있다.각 방정식은 두 개의 상호 보완적인 불평등으로 대체될 수 있기 때문에 Min-RVLS[[]와 Min-RVLS[]에도 적용된다.
• 최소 도수 설정에서 Min-RVLS[min-RVLS]로 감소가 있다.

한편, Min-RVLS[=]에서 Min-ULR[=]로 감소가 있다.각 방정식은 두 개의 보완적 불평등으로 대체될 수 있기 때문에 Min-ULR[[]과 Min-ULR[]에도 적용된다.

따라서 R이 {=,>에 있을 때 Min-ULR과 Min-RVLS는 근사 경도 면에서 동등하다.

참조