CAJ | 학술논문

P vs. NP是理论计算机领域最重要的课题之一,而其中的核心是NP完全问题. 由于该问题所涉及的概念复杂抽象,对它们的理解存在不少谬误,许多已发表的研究论文都包含着这些谬误. 主要是:NP、NP完全概念理解谬误,确定性及非确定性图灵机的概念模糊不清,P与NP关系的误读,NP问题研究方向的误导等. 本文分析了这些谬误,并揭示了相关概念的实质. 通过不同角度多方位分析,对NP完全问题可能的解决途径和研究方向,提供了启发式思路.
P vs. NP시이론계산궤영역최중요적과제지일,이기중적핵심시NP완전문제. 유우해문제소섭급적개념복잡추상,대타문적리해존재불소류오,허다이발표적연구논문도포함착저사류오. 주요시:NP、NP완전개념리해류오,학정성급비학정성도령궤적개념모호불청,P여NP관계적오독,NP문제연구방향적오도등. 본문분석료저사류오,병게시료상관개념적실질. 통과불동각도다방위분석,대NP완전문제가능적해결도경화연구방향,제공료계발식사로.
P versus NP is one of the most important problems in theoretical computer science. Because the concepts about it are very abstract and complicated, some scholars and students in computer science often misunderstand them. A lot of published papers contain these misunderstandings. The main problems are: the defaults in understanding the concepts of NP and NPC, unclearly understanding the concepts of deterministic turing machine and non-deterministic turing machine, misreading the relationship of P and NP and mislead-ing in the study direction of NP, etc. Of all these concepts, the core concept is the NP-complete problem. In this paper, we analyzed the misunderstandings. By deeply studying the definitions, we revealed their essence. Specially, by analyzing a lot of questions in different fields, we gave some heuristic strain of thoughts for the possible ways to solve the NP-complete problem and the possible directions to study it.