# 英语博文：解析“多项式时间可验证” － NP定义的歧义性 精选

NP当初作为新问题出现时，人们直觉到与P有别，而与“不确定性”有关。然而“不确定性”却是一个复杂的概念，在自然语言的表达中根据具体语境存在着不同的“不确定性观念”，既可以认为“确定性”是“不确定性”的特例（P包含在NP中），也可以认为“不确定性”与“确定性”有别（NP与P相对），类似man既可以指称“男人”也可以指称“人类”二个不同概念一样。

－最短路径问题：给定一系列城市和城市之间的距离，求解从一座城市s到另一座城市t的最短路径。

－旅行商问题（TSP）：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。

Reference :

[1] 概念的“相对性”

[3] Yu LI, What is NP? - Interpretation of a Chinese paradox "white horse is not horse" (https://arxiv.org/abs/1501.01906)

＊＊＊＊＊＊

### Analysis of "polynomial time verifiable" - Ambiguity of NP

In NP-completeness theory, NP is defined as polynomial time verifiable by TM. In this paper, from the view of concept cognition, we interpret this definition and argue that it causes the ambiguity in understanding NP [1].

1. The relativity of concept

Concepts are used to refer to things, so it is necessary for a concept to set limits for something new to be defined so that it can be distinguished from something already known, which is a basic principe of definition and also the starting point for recognizing something new. In this sense, a concept has the property of relativity, that is, it is defined relative to other known concepts.

In natural languages, polysemy is the capacity for a word to refer to different concepts. It is the relativity of concept that enables speakers to know which concept is referred to by a word through the context of a word, thereby to avoid the ambiguity of a word due to its polysemy.

However, in formal languages, speakers are excluded in order to keep the objectivity, which is required by the strictness of science and the consistency of logic, so the polysemy of natural languages is no longer permitted.

Therefore, if the polysemy is unconsciously brought into scientific domains, there would arise the ambiguity of concept. The confusion in understanding NP in the computational complexity theory is due to such ambiguity.

2. Study case: the word man in English

Let us analyze the polysemy of the word man in English to help to understand the ambiguity of NP.

The word man can refer either to the human or to males of the human, depending on the relativity of concept.

In relative to beast (animal), man refers to the human, then man can be defined by the properties such as rationality. For example, man as human can be said to be life having rationality.

In relative to woman, man cannot be defined by rationality, because rationality is a common property of human beings, of course women also have rationality. However, if one insists on defining males of the human by rationality, then manactually refers not to males of the human, but to the human. In other words, the concept as males of the human would disappears. In this case, we call it the disguised displacement which is the most common but tangled cognitive errors.

Therefore, concerning man versus woman, man must be defined by some properties like gender that can distinguish man from woman. For example, man is a human being with a male character.

In natural language, a speaker can recognize the context and avoid the ambiguity of language. For example, saying Protecting the Earth is the responsibility of man, nobody listening to this phrase would interpret man as males of the human in the context of the environmental protection which concerns the humanity.

Another example is, saying A man and a woman sitting on the boat are talking about their marriage. Likewise, nobody would interpret man as the Human.

3. NP in the computational complexity theory

Concerning NP, it can be traced to the 60’s when a great number of applicable and significant problems were discovered for which no polynomial algorithms could be found to solve them, people intuitively realized that such problems would be different from P, but related with the notion of nondeterminism.

However, nondeterminism is a complex concept and there exist different opinions about it according to specific contexts in natural languages. For example, determinism can be considered as a special case of nondeterminism (P in NP), and nondeterminism can be also considered as relative to determinism (P versus NP), which is similar to man that can refer to two different concepts as males of the human and human.

In the computational complexity theory, NP is a strict concept that does not allow the ambiguity. Initially, P refers to some problems easy to solve, while NP refers to some problems difficult to solve, that is, the relation between P and NP is P versus NP.

However, the above polysemy of nondeterminism in natural language has been introduced into the current theoretical framework, where NP is defined by the property of polynomial time verifiable. As P is also polynomial time verifiable, so P is included in NP, then P versus NP is disguisedly displaced to P in NP.

Let us look at two well known problems [2]:

- Path Problem: Give a directed graph G and two nodes s and t, find a path from s to t.
- Hamiltonian Path Problem: Given a directed graph G and two nodes s and t, find a path that traverses all nodes of G from s to t (Hamiltonian path).

We all know that the Path Problem is in P while the Hamilton Path Problem is in NP. According to the current definition of NP, normally one can say that the Path Problem is a special case of the Hamilton Path Problem  so the Path Problem is NP. However, if the Path Problem is said to be in NP, nobody would accept this opinion, moreover this opinion would be considered as cognitive error.

So why can the definition of NP which causes P to be in NP be accepted without any question?

Reference :
[1] Yu LI, What is NP? - Interpretation of a Chinese paradox "white horse is not horse" (https://arxiv.org/abs/1501.01906).
[2] Michael Sipser, Introduction to the Theory of Computation, Second Edition. International Edition (2006).

https://wap.sciencenet.cn/blog-2322490-1084941.html

## 相关博文

GMT+8, 2022-8-17 21:16

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社