NP-중간체

계산 복잡도에서, 복잡도 클래스 NP에 속하지만 클래스 P나 NP-완전에 속하지 않는 문제를 NP-중간이라고 하고, 그러한 문제의 클래스를 NPI라고 합니다.1975년 리처드 E. 래드너에 의해 보여진 래드너의 정리는 P가 NP ≠이면 NPI가 비어 있지 않다는 것을 주장하는 결과입니다. 즉, NP는 P도 NP도 완전하지 않은 문제를 포함합니다.NPI 문제가 있는 경우 P는 NP ≠이므로 NPI가 비어 있는 경우에만 P = NP를 따릅니다.

P가 NP ≠ NP라는 가정 하에서 Ladner는 NPI에 문제를 명시적으로 구성하지만, 이 문제는 인위적이고 그 외에는 흥미롭지 않습니다."자연적인" 문제가 동일한 속성을 갖는지 여부는 공개된 질문입니다.Schaefer의 이분법 정리는 제한된 부울 만족도 문제의 클래스가 NPI에 있을 수 없는 조건을 제공합니다.^[2]^[3]NP-중간이 되기에 좋은 후보로 간주되는 몇 가지 문제는 그래프 동형 문제, 요인화 및 이산 로그의 결정 버전입니다.

NP 중간일 수 있는 문제 목록

대수론과 수론

인수분해 정수 결정 버전: $입력$ n $n$ 및 $n$ $k$ $k$ 에 대해 $k$ $n$ $n$ 에 구간 $[2,k]$ k $[2,k]$ $[2,k]$ 에 인수가 있습니까 $n$ $[2,k]$
이산 로그 문제의 결정 버전 및 암호화 가정과 관련된 기타 사항
선형 구분: 정수 $x$ $x$ 및 y $x$ ${\displaystyle$ y $}$ 이 $y$ 가) 주어졌을 때 $y$ ${\displaystyle$ y $}$ 에 $x$ $x$ 과(와) 일치하는 구분자가 있습니까 $x$ ^[4]^[5]

부울 논리

IMSAT, "단조 CNF 교차"에 대한 부울 만족도 문제: 각 절이 양의 항만 포함하거나 음의 항만 포함하고, 각 양의 절은 각 음의 절과^[6] 공통되는 변수를 갖는 연결 법선형
최소 회로 크기 문제: 부울 함수의 진리표와양의 $정수$ {\ $displaystyles}$ 이(가) 주어졌을 때 $s$ 이 함수에 대해 $s$ ${\displaystyles}$ 크기의 $회로$ 가 존재합니까?^[7]
단조 자기 이중성: 부울 함수에 대한 CNF 공식이 주어지면 함수는 모든 변수를 부정한 다음 출력 값을 부정하는 변환 하에서 불변합니까?^[8]

계산 지오메트리 및 계산 토폴로지

두 이진 트리 간의 회전 거리^[9] 또는 동일한 볼록 다각형의 두 삼각형 간의 플립 거리가 주어진 임계값 미만인지 여부 결정
거리 다중집합에서^[10] 점을 온라인으로 재구성하는 턴파이크 문제
객체 길이가^[11] 일정한 절단 스톡 문제
매듭 보잘것없는^[12] 것
볼록한 다면체에서^[13] 단순한 닫힌 준주선체 찾기

게임이론

패리티 게임에서 승자를 결정하는 것. 그래프 정점은 어떤 플레이어가 다음 단계를 선택하는지에 따라 레이블이 지정되고 승자는 도달한^[14] 가장 높은 우선 순위의 정점의 패리티에 따라 결정됩니다.
확률적 그래프 게임의 승자를 결정하는 것으로, 그래프 정점은 어떤 플레이어가 다음 단계를 선택하는지 또는 임의로 선택하는지 여부에 따라 레이블이 지정되며, 승자는 지정된 싱크 정점에 도달하여 결정됩니다.^[15]

그래프 알고리즘

그래프 동형 문제^[16]
평면 최소 이등분선^[17]
그래프에서 단아한 레이블링이^[18] 허용되는지 여부 결정
잎의 힘과 k-잎의^[19] 힘을 인식하는 것
경계가 있는 클라이크 너비^[20] 그래프 인식
가장자리가^[21] 고정된 동시 매립 여부 테스트

여러가지 종류의

주어진 집합 계열의 Vapnik-Chervonenkis 차원이 주어진 경계^[22] 아래에 있는지 여부 검정

참고문헌

^ Ladner, Richard (1975). "On the Structure of Polynomial Time Reducibility". Journal of the ACM. 22 (1): 155–171. doi:10.1145/321864.321877. S2CID 14352974.
^ Grädel, Erich; Kolaitis, Phokion G.; Libkin, Leonid; Marx, Maarten; Spencer, Joel; Vardi, Moshe Y.; Venema, Yde; Weinstein, Scott (2007). Finite model theory and its applications. Texts in Theoretical Computer Science. An EATCS Series. Berlin: Springer-Verlag. p. 348. ISBN 978-3-540-00428-8. Zbl 1133.03001.
^ Schaefer, Thomas J. (1978). "The complexity of satisfiability problems" (PDF). Proc. 10th Ann. ACM Symp. on Theory of Computing. pp. 216–226. MR 0521057.
^ Adleman, Leonard; Manders, Kenneth (1977). "Reducibility, randomness, and intractibility". Proceedings of the 9th ACM Symp. on Theory of Computing (STOC '77). doi:10.1145/800105.803405.
^ Papadimitriou, Christos H. (1994). Computational Complexity. Addison-Wesley. p. 236. ISBN 9780201530827.
^ Eiter, Thomas; Gottlob, Georg (2002). "Hypergraph transversal computation and related problems in logic and AI". In Flesca, Sergio; Greco, Sergio; Leone, Nicola; Ianni, Giovambattista (eds.). Logics in Artificial Intelligence, European Conference, JELIA 2002, Cosenza, Italy, September, 23-26, Proceedings. Lecture Notes in Computer Science. Vol. 2424. Springer. pp. 549–564. doi:10.1007/3-540-45757-7_53.
^ Kabanets, Valentine; Cai, Jin-Yi (2000). "Circuit minimization problem". Proc. 32nd Symposium on Theory of Computing. Portland, Oregon, USA. pp. 73–79. doi:10.1145/335305.335314. S2CID 785205. ECCC TR99-045.
^ Eiter, Thomas; Makino, Kazuhisa; Gottlob, Georg (2008). "Computational aspects of monotone dualization: a brief survey". Discrete Applied Mathematics. 156 (11): 2035–2049. doi:10.1016/j.dam.2007.04.017. MR 2437000. S2CID 10096898.
^ Sleator, Daniel D.; Tarjan, Robert E.; Thurston, William P. (1988). "Rotation distance, triangulations, and hyperbolic geometry". Journal of the American Mathematical Society. 1 (3): 647–681. doi:10.2307/1990951. JSTOR 1990951. MR 0928904.
^ Skiena, Steven; Smith, Warren D.; Lemke, Paul (1990). "Reconstructing Sets from Interpoint Distances (Extended Abstract)". In Seidel, Raimund (ed.). Proceedings of the Sixth Annual Symposium on Computational Geometry, Berkeley, CA, USA, June 6-8, 1990. ACM. pp. 332–339. doi:10.1145/98524.98598.
^ Jansen, Klaus; Solis-Oba, Roberto (2011). "A polynomial time OPT + 1 algorithm for the cutting stock problem with a constant number of object lengths". Mathematics of Operations Research. 36 (4): 743–753. doi:10.1287/moor.1110.0515. MR 2855867.
^ Lackenby, Marc (2021). "The efficient certification of knottedness and Thurston norm". Advances in Mathematics. 387: Paper No. 107796. arXiv:1604.00290. doi:10.1016/j.aim.2021.107796. MR 4274879. S2CID 119307517.
^ Demaine, Erik D.; O'Rourke, Joseph (2007). "24 Geodesics: Lyusternik–Schnirelmann". Geometric folding algorithms: Linkages, origami, polyhedra. Cambridge: Cambridge University Press. pp. 372–375. doi:10.1017/CBO9780511735172. ISBN 978-0-521-71522-5. MR 2354878..
^ Jurdziński, Marcin (1998). "Deciding the winner in parity games is in UP $\cap$ co-UP". Information Processing Letters. 68 (3): 119–124. doi:10.1016/S0020-0190(98)00150-1. MR 1657581.
^ Condon, Anne (1992). "The complexity of stochastic games". Information and Computation. 96 (2): 203–224. doi:10.1016/0890-5401(92)90048-K. MR 1147987.
^ Grohe, Martin; Neuen, Daniel (June 2021). "Recent advances on the graph isomorphism problem". Surveys in Combinatorics 2021. Cambridge University Press. pp. 187–234. arXiv:2011.01366. doi:10.1017/9781009036214.006. S2CID 226237505.
^ Karpinski, Marek (2002). "Approximability of the minimum bisection problem: an algorithmic challenge". In Diks, Krzysztof; Rytter, Wojciech (eds.). Mathematical Foundations of Computer Science 2002, 27th International Symposium, MFCS 2002, Warsaw, Poland, August 26-30, 2002, Proceedings. Lecture Notes in Computer Science. Vol. 2420. Springer. pp. 59–67. doi:10.1007/3-540-45687-2_4.
^ Gallian, Joseph A. (December 17, 2021). "A dynamic survey of graph labeling". Electronic Journal of Combinatorics. 5: Dynamic Survey 6. MR 1668059.
^ Nishimura, N.; Ragde, P.; Thilikos, D.M. (2002). "On graph powers for leaf-labeled trees". Journal of Algorithms. 42: 69–108. doi:10.1006/jagm.2001.1195..
^ Fellows, Michael R.; Rosamond, Frances A.; Rotics, Udi; Szeider, Stefan (2009). "Clique-width is NP-complete". SIAM Journal on Discrete Mathematics. 23 (2): 909–939. doi:10.1137/070687256. MR 2519936..
^ Gassner, Elisabeth; Jünger, Michael; Percan, Merijam; Schaefer, Marcus; Schulz, Michael (2006). "Simultaneous graph embeddings with fixed edges". Graph-Theoretic Concepts in Computer Science: 32nd International Workshop, WG 2006, Bergen, Norway, June 22-24, 2006, Revised Papers (PDF). Lecture Notes in Computer Science. Vol. 4271. Berlin: Springer. pp. 325–335. doi:10.1007/11917496_29. MR 2290741..
^ Papadimitriou, Christos H.; Yannakakis, Mihalis (1996). "On limited nondeterminism and the complexity of the V-C dimension". Journal of Computer and System Sciences. 53 (2, part 1): 161–170. doi:10.1006/jcss.1996.0058. MR 1418886.

외부 링크

복잡성 동물원: 클래스 NPI
기본 구조, 튜링 환원성 및 NP-경도
Lance Fortnow (24 March 2003). "Foundations of Complexity, Lesson 16: Ladner's Theorem". Retrieved 1 November 2013.

[1] Ladner, Richard (1975). "On the Structure of Polynomial Time Reducibility". Journal of the ACM. 22 (1): 155–171. doi:10.1145/321864.321877. S2CID 14352974.

[2] Grädel, Erich; Kolaitis, Phokion G.; Libkin, Leonid; Marx, Maarten; Spencer, Joel; Vardi, Moshe Y.; Venema, Yde; Weinstein, Scott (2007). Finite model theory and its applications. Texts in Theoretical Computer Science. An EATCS Series. Berlin: Springer-Verlag. p. 348. ISBN 978-3-540-00428-8. Zbl 1133.03001.

[3] Schaefer, Thomas J. (1978). "The complexity of satisfiability problems" (PDF). Proc. 10th Ann. ACM Symp. on Theory of Computing. pp. 216–226. MR 0521057.

[4] Adleman, Leonard; Manders, Kenneth (1977). "Reducibility, randomness, and intractibility". Proceedings of the 9th ACM Symp. on Theory of Computing (STOC '77). doi:10.1145/800105.803405.

[5] Papadimitriou, Christos H. (1994). Computational Complexity. Addison-Wesley. p. 236. ISBN 9780201530827.

[6] Eiter, Thomas; Gottlob, Georg (2002). "Hypergraph transversal computation and related problems in logic and AI". In Flesca, Sergio; Greco, Sergio; Leone, Nicola; Ianni, Giovambattista (eds.). Logics in Artificial Intelligence, European Conference, JELIA 2002, Cosenza, Italy, September, 23-26, Proceedings. Lecture Notes in Computer Science. Vol. 2424. Springer. pp. 549–564. doi:10.1007/3-540-45757-7_53.

[7] Kabanets, Valentine; Cai, Jin-Yi (2000). "Circuit minimization problem". Proc. 32nd Symposium on Theory of Computing. Portland, Oregon, USA. pp. 73–79. doi:10.1145/335305.335314. S2CID 785205. ECCC TR99-045.

[8] Eiter, Thomas; Makino, Kazuhisa; Gottlob, Georg (2008). "Computational aspects of monotone dualization: a brief survey". Discrete Applied Mathematics. 156 (11): 2035–2049. doi:10.1016/j.dam.2007.04.017. MR 2437000. S2CID 10096898.

[9] Sleator, Daniel D.; Tarjan, Robert E.; Thurston, William P. (1988). "Rotation distance, triangulations, and hyperbolic geometry". Journal of the American Mathematical Society. 1 (3): 647–681. doi:10.2307/1990951. JSTOR 1990951. MR 0928904.

[10] Skiena, Steven; Smith, Warren D.; Lemke, Paul (1990). "Reconstructing Sets from Interpoint Distances (Extended Abstract)". In Seidel, Raimund (ed.). Proceedings of the Sixth Annual Symposium on Computational Geometry, Berkeley, CA, USA, June 6-8, 1990. ACM. pp. 332–339. doi:10.1145/98524.98598.

[11] Jansen, Klaus; Solis-Oba, Roberto (2011). "A polynomial time OPT + 1 algorithm for the cutting stock problem with a constant number of object lengths". Mathematics of Operations Research. 36 (4): 743–753. doi:10.1287/moor.1110.0515. MR 2855867.

[12] Lackenby, Marc (2021). "The efficient certification of knottedness and Thurston norm". Advances in Mathematics. 387: Paper No. 107796. arXiv:1604.00290. doi:10.1016/j.aim.2021.107796. MR 4274879. S2CID 119307517.

[13] Demaine, Erik D.; O'Rourke, Joseph (2007). "24 Geodesics: Lyusternik–Schnirelmann". Geometric folding algorithms: Linkages, origami, polyhedra. Cambridge: Cambridge University Press. pp. 372–375. doi:10.1017/CBO9780511735172. ISBN 978-0-521-71522-5. MR 2354878..

[14] Jurdziński, Marcin (1998). "Deciding the winner in parity games is in UP $\cap$ co-UP". Information Processing Letters. 68 (3): 119–124. doi:10.1016/S0020-0190(98)00150-1. MR 1657581.

[15] Condon, Anne (1992). "The complexity of stochastic games". Information and Computation. 96 (2): 203–224. doi:10.1016/0890-5401(92)90048-K. MR 1147987.

[16] Grohe, Martin; Neuen, Daniel (June 2021). "Recent advances on the graph isomorphism problem". Surveys in Combinatorics 2021. Cambridge University Press. pp. 187–234. arXiv:2011.01366. doi:10.1017/9781009036214.006. S2CID 226237505.

[17] Karpinski, Marek (2002). "Approximability of the minimum bisection problem: an algorithmic challenge". In Diks, Krzysztof; Rytter, Wojciech (eds.). Mathematical Foundations of Computer Science 2002, 27th International Symposium, MFCS 2002, Warsaw, Poland, August 26-30, 2002, Proceedings. Lecture Notes in Computer Science. Vol. 2420. Springer. pp. 59–67. doi:10.1007/3-540-45687-2_4.

[18] Gallian, Joseph A. (December 17, 2021). "A dynamic survey of graph labeling". Electronic Journal of Combinatorics. 5: Dynamic Survey 6. MR 1668059.

[19] Nishimura, N.; Ragde, P.; Thilikos, D.M. (2002). "On graph powers for leaf-labeled trees". Journal of Algorithms. 42: 69–108. doi:10.1006/jagm.2001.1195..

[20] Fellows, Michael R.; Rosamond, Frances A.; Rotics, Udi; Szeider, Stefan (2009). "Clique-width is NP-complete". SIAM Journal on Discrete Mathematics. 23 (2): 909–939. doi:10.1137/070687256. MR 2519936..

[21] Gassner, Elisabeth; Jünger, Michael; Percan, Merijam; Schaefer, Marcus; Schulz, Michael (2006). "Simultaneous graph embeddings with fixed edges". Graph-Theoretic Concepts in Computer Science: 32nd International Workshop, WG 2006, Bergen, Norway, June 22-24, 2006, Revised Papers (PDF). Lecture Notes in Computer Science. Vol. 4271. Berlin: Springer. pp. 325–335. doi:10.1007/11917496_29. MR 2290741..

[22] Papadimitriou, Christos H.; Yannakakis, Mihalis (1996). "On limited nondeterminism and the complexity of the V-C dimension". Journal of Computer and System Sciences. 53 (2, part 1): 161–170. doi:10.1006/jcss.1996.0058. MR 1418886.

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

Search