공정분할 미해결 문제 목록

이 페이지는 공정 분업과 관련된 주목할 만한 개방적 문제들 - 수학, 컴퓨터 과학, 정치학, 경제학이 교차하는 분야.null

공정한 케이크 커팅의 개방적 문제

질투 없는 케이크 커팅의 복잡성 쿼리

부러움 없는 케이크 커팅 문제에는 간격을 두고 모델링한 케이크가 있고, 케이크를 놓고 가치 측도가 다른 n ${\displaystylen}에이전트$가 있다.가치 측정은 "주어진 케이크 조각을 평가" 또는 "주어진 값으로 케이크 조각을 표시" 형식의 질의를 통해서만 접근할 수 있다.n${\displaystyle }$= ${\displaystyle 2}$ ${\displaystyle n=2}$ 에이전트에서는$$ divide와 select를 통해 두 개의 쿼리를 사용하여 질투 없는 분할을 찾을 수 있다.> ${\displaystyle n>2}$ 에이전트에서는 필요한 쿼리 수와 관련하여 몇 가지 개방적인 문제가 있다.null

1. 첫째, 케이크 전체를 할당해야 한다(즉, 폐기물이 없다), 조각이 분리될 수 있다고 가정한다.몇 개의 쿼리가 필요한가?null

• 하한: Ω${\displaystyle \mathrm{}({}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$) ${\displaystyle \Oomega(n^{2$^[1]
• 상한: O${\displaystyle }$( ${\displaystyle {}^{}}$ ${\displaystyle {{n{}^{}}^{}}^{}}$ ${\displaystyle {{{n{}^{}}^{}}^{}}^{}}$ n n ${\displaystyle {{{{n^{}}^{}}^{}}^{}}^{}}$) ${\$^[2] .

2. 다음으로, 일부 케이크는 할당되지 않은 상태로 둘 수 있지만(즉, 무료 처분이 있다), 할당량은 비례해야 한다(부럽지 않은 것에 더하여), 각 대리인은 총 케이크 값의 최소$$ $[\displaystyle$ 1$/n}$을 얻어야 한다.조각들은 여전히 분리되어 있을 수 있다.몇 개의 쿼리가 필요한가?null

• 하한: 알 수 없음(이론적으로 다항식적으로 해결할 수 있는 것일 수 있음).
• 상한:${\displaystyle }$( ${\displaystyle n}$!${\displaystyle {}^{}}$) ${\displaystyle {2n\mathrm{}}^{}}$ 2 ${\$$^{2}n^{2$^[2]

3. 다음으로, 자유처분이 있다고 가정하면, 배분은 여전히 비례해야 하지만, 조각들은 연결되어야 한다.몇 개의 쿼리가 필요한가?null

• n${\displaystyle }$= ${\displaystyle 3}$ ${\displaystyle n=3$의 경우 54개의 쿼리를 가진 알고리즘이 있다.^[3]
• n ${\displaystyle \ge }$ ${\displaystyle 4}$ ${\displaystyle n\geq 4}$의 경우$,$ 현재 유한 알고리즘은 알려져 있지 않다.

4. 다음으로, 무료 처분이 있다고 가정하고, 조각들은 연결되어야 하지만, 배분은 대략적인 비례에 불과할 수 있다(즉, 일부 대리점들은 전체 케이크 $값$의${\displaystyle }$1/$[\displaystyle/n}$ 이하를 얻을 수 있다).유한한 질투 없는 프로토콜을 사용하여 각 에이전트에게 어떤 가치를 보장할 수 있는가?null

• $n{\displaystyle }$= ${\displaystyle 3}$ ${\displaystyle n=3$의 경우 1/3을 달성하는 알고리즘이 있는데, 이것이 최적이다.
• $n{\displaystyle }$= ${\displaystyle 4}$ ${\displaystyle n=4}($최소 오픈 케이스)의 경우 1/7을 달성하는 알고리즘이 있다.^[3]
• $n{\displaystyle }$ ${\displaystyle n}$에 대해$,$ $1{\displaystyle \mathrm{}}$/${\displaystyle }$( ${\displaystyle \mathrm{3n}}$) ${\displaystyle$ 1$/(3n)}$을(를) 갖는 알고리즘이 있다$.$^[2]

5. 마지막으로, 케이크 전체를 할당해야 하고 조각이 분리될 수 있지만, 절단 횟수(또는 에이전트당 조각 수)는 가능한 한 적어야 한다고 가정한다.한정된 수의 질의에서 질투 없는 할당을 찾으려면 얼마나 많은 삭감이 필요한가?null

• $n{\displaystyle }$ ${\displaystyle \ge }$ ${\displaystyle 3}$ ${\displaystyle n\geq 3$의 경우, ${\displaystyle \mathrm{n}}$- 1 ${\displaystyle n-1}$ 컷$$(에이전트당 1개)에 대해 유한 알고리즘이 존재하지 않는다.^[4]
• $n{\displaystyle }$= ${\displaystyle 3}$ ${\displaystyle n=3}$의 경우, Selfridge-Conway 절차는 5개의 컷(에이전트당 최대 2개)으로 유한 시간 내에 문제를 해결한다.
• $n{\displaystyle }$ ${\displaystyle \ge }$ ${\displaystyle 4}$ ${\displaystyle n\geq 4$의 경우, Aziz-Mackenzie 절차는 유한한 시간 내에 문제를 해결하지만 많은 컷(및 에이전트당 많은 조각)을 사용하여 문제를 해결한다.
• 최소 오픈 케이스: 에이전트 3개, 컷 3~4개, 에이전트 4개, 에이전트 1개당 2개.

서로 다른 자격을 가진 케이크 절단 횟수

모든 에이전트가 동일한 자격을 가질 경우,${\displaystyle }$n - ${\displaystyle 1}${\$displaystyle n-1}$컷을 사용하여$$ 비례 케이크 커팅을 구현할 수 있으며, 이것이 최적이다.null

자격이 다른 $n{\displaystyle }$ ${\displaystyle n}$ 에이전트$$ 중 비례적인 케이크 커팅을 구현하려면 얼마나 많은 컷이 필요한가?

• 하한: ${\displaystyle \mathrm{2n}}$- 2 ${\displaystyle 2n-2$^[5]
• 상한: ${\displaystyle \mathrm{3n}}$- 4 ${\displaystyle 3n-4$^[6]
• 최소 개방 사례: n${\displaystyle }$= ${\displaystyle 3}$ ${\displaystyle n=3}$ ${\displaystyle 에이전트\mathrm{}}$(모든$$ $사용{\displaystyle \mathrm{}}$ 권한: 1${\displaystyle }$/ 7 ${\displaystyle 1/7$ ${\displaystyle 2\mathrm{}}$/ 7 ${\displaystyle 2/7}$ 및$$ 4${\displaystyle }$/ ${\displaystyle 7\mathrm{}}$ ${\displaystyle 4/7$^[5]

서로 다른 $자격$을 가진$$n {\$displaystyle$ n$}$에이전트$$ 간에 질투 없는 케이크 커팅을 구현하려면 얼마나 많은 컷이 필요한가?

• 하한: ${\displaystyle \mathrm{2n}}$- ${\displaystyle 2}$ ${\displaystyle 2n-2$ 질투 없는 것은 비례한다는 것을 의미하므로.
• 상한: 알 수 없음.

부분 연소된 케이크의 공정한 분할

부분적으로 불에 탄 케이크는 케이크에 대한 비유로, 에이전트들이 긍정적인 가치와 부정적인 가치를 둘 다 가질 수 있다.^[7]null

그러한 케이크의 비례적인 구분이 항상 존재한다.null

부분 연소된 케이크의 연결 비율 할당을 계산하는 런타임 복잡성은 무엇인가?

알려진 경우:

• 모든 평가가 양의 값이거나 모든 평가가 음의 값일 때, Even-Paz 프로토콜은 $O{\displaystyle (n}$ ${\displaystyle \log }$ ${\displaystyle }$ n${\displaystyle }$) ${\displaystyle O(n\log n)}$ 쿼리를$$ 사용하여 연결된 비례 구분을 찾으며, 이것이 최적이다.
• 평가가 혼합될 수 있는 경우 $이동{\displaystyle }$ 나이프 프로토콜을 사용하여 O${\displaystyle }$( ${\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$) ${\displaystyle O(n^{2})$ 쿼리를$$ 사용하여 연결된 비례 구분을 찾을 수 있다.^{[8]: Thm.5} 이 값을 $O{\displaystyle (n}$ ${\displaystyle \log }$ ${\displaystyle n}$) ${\displaystyle O(n\log n)}($으)로 개선할 수 있는가?$$

부분 연소된 케이크의 질투 없는 분할은 만약의 경우에 한해 존재한다고 보장된다. 단, 에이전트 수가 소수 정수의 힘이라면 말이다.^[9]그러나 한정된 프로토콜로는 찾을 수 없다. - 그것은 근사치일 뿐이다.작은 양의 숫자 D를 주어, 각 에이전트에 대해 컷을 최대 D(길이 단위)까지 이동시키면 배분이 질투가 없을 경우 D-envy-free라고 불린다.null

부분 연소된 케이크의 D-envy-free 연결 할당을 계산하는 런타임 복잡성은 무엇인가?^[7]

진실한 케이크 커팅

진실한 케이크 커팅은 공정한 케이크 커팅을 위한 진실한 메커니즘의 디자인이다.현재 알려진 알고리즘과 불가능한 결과를 여기에 나타낸다.결정론적 진실된 공정 메커니즘의 존재 여부를 알 수 없는 주요 사례는 다음과 같다.^[10]

• 3개 이상의 대리점들이 조각처럼 균일하게 평가되며, 무료 처분 없이 있다.
• 2개 이상의 대리인이 있으며, 폐기 여부와 관계없이(연결성 또는 비폐기성과 같은 추가 요구사항이 없는 경우) 공정하게 평가한다.

분리할 수 없는 항목의 공정한 할당에 있어 개방적인 문제

대략적인 최대 공유 공정성

에이전트의 ${\displaystyle }$ ${\displaystyle n}$최대$$ 공유(MMS)는 항목을 $n{\displaystyle }$ ${\displaystyle n}$ 번들로$$ 분할하고 최악의 번들을 수신하여 에이전트가 보호할 수 있는 최대 유틸리티다.두 에이전트의 경우, 분할과 선택은 각 에이전트에 최소한 자신의 의 1 MMS를 부여한다. > 2 ${\displaystyle$ n$>$$2}$ 에이전트의 경우, 각 에이전트에 대해 $$의 1-n$${\$displaystyle$ n$$} MMS를 부여하는 것은 거의 항상 가능하지만 항상은 않다. 이것은 여러 종류의 의문을 제기한다.null

1. 계산 복잡성

특정 인스턴스가 $$의 1개$({\displaystyle n}$MMS$$ 할당을 허용하는지 여부를 결정하는 런타임 복잡성은 무엇인가?^[11][12]

• 상한: $N{\displaystyle {}^{}}$ ${\displaystyle P^{}}$ N ${\displaystyle P^{}}$ ${\$$NP}}($다항식 계층 구조에서 \ ${\displaystyle {}_{}^{}}$ P ${\$ $$- 레벨 2)
• 하한: 없음(따라서 계층의 수준 2 또는 1 또는 0일 수 있음).

참고: 다음과 같은 관련 문제는 계산적으로 어려운 것으로 알려져 있다.

• 지정된 에이전트의 ${\displaystyle }$ ${\displaystyle n}$ MMS$$ 계산은 모든 에이전트가 추가 기본 설정(파티션 문제로 인한 감소)을 가지고 있더라도 NP-hard이다.
• 추가 선호도를 가진 에이전트에 대해 지정된 할당량이 $$의$1개인지 여부$를 결정하는 것은 공동 NP 완료다$.$

2. 추기경 근사

각 에이전트에게 최소 r배 이상의 $효용$을 제공하는 할당량이 항상 존재할 수 있는 가장 큰 r은 무엇인가$?$

알려진 경우:

• $두{\displaystyle }$에이전트의 $:$ r = 1 {\$displaystyle r=1$}을$($를) 분할 및 선택.
• 첨가제 값을 가진 세 의 경우: r< ${\displaystyle r<1$ 주의 깊게 조작된 예에 의한 것이다.^[13]
• 부가 가치가 있는 에이전트 수: ${\displaystyle \mathrm{r}}$ ${\displaystyle \ge }$ 3${\displaystyle }$/ ${\displaystyle 4\mathrm{}}$ ${\displaystyle r\geq 3/4$^[14]
• 부가적인 부정적 평가가 있는 모든 수의 에이전트(예: 집안일): ${\displaystyle \mathrm{r}}$ ${\displaystyle \ge }$ 9${\displaystyle }$/ ${\displaystyle 11}$ $[\displaystyle r\geq 9/11$^[15] .

3. 순서형 근사치

$각{\displaystyle }$ 에이전트에 최소 1개의 ${\displaystyle }$ ${\displaystyle N}$MMS를$$ 제공하는 $n{\displaystyle }$ ${\displaystyle$ $n$$}$ 에이전트$$ 간에 항상 할당이 존재하도록 하는 가장 $작은{\displaystyle }$ 정수 N$${\$displaystyn$은 무엇인가?$$

알려진 경우:

• $두{\displaystyle }$에이전트의 $:$ N = 2 {\$displaystyle N=2$ 분할 및 선택.
• 이항 평가를 받는 에이전트 수:${\displaystyle N}$= ${\displaystyle n}$ ${\displaystyle N=n$ 라운드 로빈으로.EF1은 ${\displaystyle }$ ${\displaystyn}$ -MMS를$$ 의미한다.
• > ${\displaystyle n>2}$에이전트의 경우: > ${\displaystyle N>n$ 주의 깊게 조작된 예에 의해.^[13]
• 부가 가치가 있는 에이전트 수:${\displaystyle \mathrm{라운드}}$ 로빈으로 N${\displaystyle 1}$ ${\displaystyle \mathrm{2n}}$- 1 ${\displaystyle$ N\$leq 2n-1$EF1은 1-of (${\displaystyle \mathrm{2n}}$- $){\displaystyle (2n-1)}$ -MMS를$$ 의미한다.
• 부가 가치가 있는 에이전트 수:${\displaystyle N}$ ${\displaystyle \le }$ ${\displaystyle 2}$ ${\displaystyle n}$- ${\displaystyle 2}$ ${\displaystyle N\leq 2n-2$ 질투 없는 매칭 사용.^[16]

따라서 답은 $n{\displaystyle }$+ ${\displaystyle 1}$ ${\displaystyle n+1}$과(와) $2{\displaystyle \mathrm{}}$ ${\displaystyle \mathrm{n}}$ -${\displaystyle }$2 ${\displaystyle 2n-2}$ 사이의 모든 것이 될 수 있다$.$최소 오픈 케이스:

$추가{\displaystyle }$ 평가가 있는 n${\displaystyle }$= ${\displaystyle 4}$ ${\displaystyle n=4}$ 에이전트의$$ 경우 항상 최대 5분의 1의 최대 지분 할당이 존재하는가?

참고: 항상 최대 1/1(${\displaystyle }$ +${\displaystyle 1}${\$displaystyle n+1$의 최대 공유를 보장하는 동등한 소득으로부터의 대략적인 경쟁적 균형(Ablight Competitive Balance from Equal Income)이 존재한다.^[17]그러나 이러한 할당에는 과잉공급이 있을 수 있으며, 더 중요한 것은 초과수요가 있을 수 있다는 점이다. 모든 에이전트에 할당된 번들의 합은 모든 항목의 집합보다 약간 클 수 있다.이러한 오류는 소수 좌석을 추가하면 적은 양의 초과 공급량을 교정할 수 있기 때문에 학생들 사이에 강좌 좌석을 할당할 때 타당하다.그러나 전형적인 공정분할 문제는 항목이 추가되지 않을 수도 있다는 것을 가정한다.null

한 아이템까지 시샘이 없는 아이템

두 에이전트 $i{\displaystyle }$ ${\displaystyle i}$ 및 j$$ ${\displaystyle$ j$}$에$$$대해{\displaystyle }$ 그리고 $j{\displaystyle }$ ${\displaystyle$ $j$$}$ 번들에 포함된 크기의 하위 집합에 대해$$$해당{\displaystyle }$ 하위 집합을 j ${\displaysty$ j$}$의$$번들에서 제거하면 i ${\displaysty$ i$}$이 부러워지지$$ 않을 경우 할당을 EF1(최대 한 항목 없음)이라고 한다.EF1 할당은 항상 존재하며 질투 주기 알고리즘에 의해 찾을 수 있다.그것을 다른 재산과 결합하는 것은 몇 가지 공개적인 문제를 제기한다.null

파레토 최적 EF1 할당(재화 및 불량)

모든 항목이 양호하고 모든 평가가 부가적인 경우, 항상 PO+EF1이 존재한다. 즉, 유틸리티의 제품을 최대화하는 할당은 PO+EF1이다.^[18]할당을 최대화하는 이 방법을 찾는 것은 NP-hard이지만 이론적으로는 다른 PO+EF1 할당(제품의 최대화가 아님)을 찾는 것이 가능할 수 있다.^[19]null

상품에 대한 PO+EF1 할당을 찾는 런타임의 복잡성은 무엇인가?

PO+EF1 배분은 모든 가치가 부가적인 경우에도 존재하는 것으로 알려져 있지 않다.null

PO+EF1 배분은 항상 존재하는가?

검색의 런타임 복잡성 그러한 할당, 존재한다면?

연속 EF1 할당

종종 물건들은 줄지어 주문된다. 예를 들어, 거리의 집들.각 요원은 연속 블록을 얻기를 원한다.^[20]null

부가 가치가 있는 3개 이상의 에이전트에 대해 EF1 할당이 항상 존재하는가?

알려진 경우:

• 부가 가치 평가가 있는 두 에이전트의 경우 정답은 "그렇다"이다. 즉, 연결된 질투 없는 케이크 커팅(예: 분할과 선택으로 발견)을 반올림할 수 있다.
• 부가 가치 평가를 받는 $n{\displaystyle }$ ${\displaystyle n}$ 에이전트의$$ 경우, 연결된 질투 없는 케이크 커팅을 반올림하여 "EF 마이너스 2" 할당을 찾을 수 있으며, EF2 할당(Speerner의 보조정리 변형을 사용하는 증명)도 존재한다.^[21]
• 가법적 이진법(모든 항목 값이 0 또는 1)을 갖는 n ${\displaystyle n}$ 에이전트의$$ 경우 "EF - 2" 할당도 EF1이므로 대답은 "예"이다.

연속적인 EF1 할당이 존재하더라도 그것을 찾는 런타임 복잡성은 불분명하다.

이항 적층 평가를 받는 3개 이상의 에이전트의 경우, 연속적인 EF1 할당을 찾는 복잡성은 무엇인가?

• 시샘이 없는 연결된 케이크 커팅은 찾기 위해 무한히 많은 질문이 필요할 수 있다.EF1 할당은 항상 가능한 모든 할당을 확인함으로써 유한한 시간에 찾을 수 있지만, 이 알고리즘은 지수적인 런타임을 필요로 한다.

공정가격

공정성의 가격은 어떤 할당에서든 최대 사회복지(유틸리티 총합)와 공정 배분에서 최대 사회복지 사이의 비율이다.EF1 공정성의 가격은 얼마인가?null

• 상한은 라운드 로빈 또는 최대 내시 복지에 의해 $O{\displaystyle }$(${\displaystyle n}$ ${\displaystyle )}$ ${\displaystyle O(n)}$이다.$$
• 하한은 $O{\displaystyle }$( ${\displaystyle n}$) ${\displaystyle O({\sqrt{n}})}$ 입니다$.$^{[22]: sec.1.1}

EFx 할당 유무

$두{\displaystyle }$ 에이전트 i ${\$$displaystyle$ $i$$}$ $및{\displaystyle }$ j$$ ${\displaystyle j}$에 대해$$그리고 j {\$displaystyle j$$}$의$$번들에서 해당 제품을 제거하면 $I{\displaystyle }$ ${\displaystyle$ i$}$이(가) 부러워하지 않는$$ 경우 할당을 EFx("최대 "완료")라고 한다$.$^[23]null

부가 가치가 있는 3개 에이전트의 경우 EFx 할당이 항상 존재하십니까?

일반적인 단조로운 평가를 받는 $n{\displaystyle }$ ${\displaystyle n}$ 에이전트에$$ 대해 EFx 할당이 존재하지 않음을 증명할 수 있는가?

알려진 경우:

• $n{\displaystyle }$- ${\displaystyle 1}$ ${\displaystyle n-1}$이상의 값이 동일한$$ 경우: 예.
• 따라서, 두 명의 요원은: 네.이것은 심지어 일반적인 단조로운 평가에도 적용된다.^[24]
• 세 명의 요원을 위해: 예, 최근 작업 보고서에 의해.^[25]

파레토 효율적인 PROPx의 배드배분 유무

$임의$의 에이전트$$i {\$displaystyle$i} $및{\displaystyle }$i {\$displaystyle$ i$}$이(가$)$ 소유한 모든 불량에 $대해{\displaystyle }$i {\$displaystyle$i$\}$의 번들에서 해당 불량품을 $제거$하면$$i {\$displaysty$i$\}$의 $불변성$이 1/n$$ ${\displaysty1/n}$보다 작을 경우 baduffictenc라고 한다.^{[26]: Sec.7} null

항상 PROPx와 Pareto 효율성이 모두 있는 불량배분이 존재하는가?

관련 알려진 사례:

• PROPx의 상품 할당은 존재하지 않을 수 있다(Pareto 효율성이 없더라도).
• PROPx 배분은 항상 존재한다(Pareto 효율성 없음).
• PROP1과 Pareto의 효율적인 상품 또는 불량 배분이 항상 존재한다.

거의 모든 소득에 대한 경쟁적 균형

경쟁적 균형(CE)은 매우 강력한 공정성 개념이다. - 그것은 파레토 최적성과 시기심을 내포하고 있다.수입이 같을 때, CE는 두 개의 에이전트와 한 개의 좋은 에이전트가 있어도 존재하지 않을 수 있다.그러나 다른 모든 소득공간에 CE는 두 개의 에이전트와 한 개의 좋은 에이전트가 있을 때 존재한다.즉, 거의 모든 소득계층에 대한 경쟁적 평형이 존재한다.null

상품 수량에 대한 부가 가치 평가가 있는 두 대리점의 경우, 거의 수입에 대한 경쟁적 평형이 존재하는가?^[27]

알려진 경우:

• 3개 또는 그 이하의 상품: 항상 그렇다.
• 상품 4개 포함: 일반적 평가가 있는 2개 대리점, 일반 평가가 있는 3개 대리점, 부가 가치 평가도 4개 대리점 제외.^[28]
• 5개 이상의 상품 포함: 일반적 가치를 지닌 2개 대리점 제외.

개방적인 추측:

• 부가 가치가 있는 두 개의 대리점이 있을 때 거의 모든 소득에 대한 CE는 상품 수에 관계없이 존재한다.
• 부가 가치 평가가 있더라도 세 가지 요인이 있을 때 거의 모든 소득에 대한 CE는 존재하지 않을 수 있다.

일부분할당항목의 공정분할

한정된 공유로 공정한 할당을 위한 런타임 복잡성

n ${\displaystyle \ge }$ ${\displaystyle 2}$ ${\displaystyle n\geq 2}$ 에이전트$$, $m{\displaystyle }$ ${\displaystyle m}$ 항목$$ 및 정수 k ${\displaystyle$ k$}$이(가) 주어진 경우$,$ $최대{\displaystyle }$ k ${\displaystyle$ k$} 항목$이 두$$ 개 이상의 에이전트 간에 공유될 수 있다고 가정해 보십시오.비례적/부럽지 않은 할당이 존재하는지 여부를 결정하는 런타임의 복잡성은 무엇인가?

알려진 경우:

• $k{\displaystyle }$= ${\displaystyle 0}$ ${\displaystyle k=0}$ 및 동일한$$ 값을 갖는 경우, $n{\displaystyle }$ ${\displaystyle \ge }$ ${\displaystyle 2}$ ${\displaystyle n\geq$ 2$\}$에 대해 문제는 파티션 문제와 동일하므로 NP-완전이다.
• $k{\displaystyle }$ ${\displaystyle \ge }$ ${\displaystyle \mathrm{n}}$ -${\displaystyle }$1 ${\displaystyle k\geq n-1}$을$($를) 사용하는 경우 답은 항상 "예"이며, 할당량은 다항식 시간 내에 찾을 수 있다.^[29]
• $n{\displaystyle }$= ${\displaystyle 3}$ ${\displaystyle n=3}$ 및 ${\displaystyle \mathrm{k<img\; alt="n=3"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/1c5a5a42ced00df920fad4ab2d4acdb960a4105b"\; style="vertical-align:\; -0.338ex;\; width:5.656ex;\; height:2.176ex;"\; papago-attr-id="323">}}$= $1{\displaystyle }$ ${\displaystyle k=1$}과$($와)^[30] 동일한 값을 갖는 경우 다항식 시간 내에 할당을 찾을 수 있다.

최소 공개 사례:

• ${\displaystyle n}$= ${\displaystyle 3}$ $[\displaystyle n=3}$ 및 $k$ = ${\displaystyle 1}$ ${\displaystyle k=1}$및$$ 다른 평가.
• ${\displaystyle n}$= ${\displaystyle 4}$ ${\displaystyle n=4}$ 및$$ $k{\displaystyle }$ ${\displaystyle \in }${ ${\displaystyle 1}$,${\displaystyle 2}$ ${\displaystyle \}}$ ${\displaystyle k\in \{1,2\}$ 및 동일한 평가$$.

참조