概念的“相对性”是概念认知的最基本原理，我们再从概念的“相对性”角度 [1][2][3]解析基于“多项式时间可验证”的NP流行定义的“歧义性”。

一，概念的相对性

概念用于指称事物，故需能界定所指事物，使之与其他已知的相关事物区分开。在此意义上，概念具有“相对性”，即一个概念的定义须相对于已知的概念来进行。

自然语言存在“多义性”，即“一词多义”，指一个词可指称不同的概念，这既是自然语言的优势又是“歧义性”的主要根源。正是概念的“相对性”使对话者通过对所处的具体语境的认知来辨析词语所指，从而避免“歧义性”。

形式语言不容许自然语言这样的“多义性”，这是科学的严格性和逻辑的一致性所要求的，即所谓的“客观性”。所以，若无意识将自然语言的“多义性”带入科学领域，就会出现“歧义性”，导致概念偷换，从而产生难以察觉的认知偏差，NP概念的困难原因之一正出于此。

二，案例：英语词man

这里我们分析英语中man的“多义性”。man既可以指“人类”（the human）也可以指“男人”（males of the human），而man的具体所指取则决于其相对的事物。

当与“动物（beast, animal）”相对时，man指“人类”，可以用诸如“理性”这样的属性来定义“人类”，比如可以说“人是具有理性的生命体”。

当与“女人（woman）”相对时，man指“男人”，此时就不能用“理性”这样的属性来定义“男人”了，因为“理性”是人类共有的属性，女人当然也具有“理性”。但若仍坚持用“理性”来定义“男人”，那么这个man实际上已经不是指相对于woman的那个man，而是被偷换成指human的man了，换句话说，“男人”这个概念就消失了，概念认知中最纠结的错误经常就是这样产生的。所以，欲指与“女人”相对的“男人”，必须用诸如“性别”之类的、能与“女人”相区别的属性来定义“男人”，比如可以说“男人是具有男性特征的人”。

在自然语言中对话者具有“主体意识”，能通过对具体语境的认知来保持概念的“相对性”，避免“歧义性”。比如说“Protecting the Earth is the responsibility of man（爱护地球是人类的责任）”，对话者明白具体语境是环境保护，关乎整个人类，故不会将此理解为“爱护地球是男人的责任”。

再比如说“A man and a women sitting on the boat are talking about their marriage.（坐在船上的男女在谈论结婚的事）“，同样，对话者也不会将这里的man理解为“人类”。

三，计算复杂性理论中的NP

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

但是在计算复杂性理论中，NP却是一个严格的概念，不容许日常语言中那样的“多义性”。追本溯源，NP欲指“与P相对的NP”，即“P指易解的问题，而NP指难解的问题”，这样的“相对性（P versus NP）”决定了NP概念的定义。但在现有的理论框架下，NP流行定义之一是基于“多项式时间可验证”，指NP问题的猜测解可在多项式时间验证，由于“多项式时间可验证”是P的一个性质，故P问题就变成了NP问题！是有“P包含在NP”中，然而“此NP非彼NP也”，换句话说，由此在计算复杂性理论中就引入了“歧义性”。

为此，我们以大家熟知的二个问题来说明：

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

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

大家都知道“最短路径问题”是P问题，而“旅行商问题”是NP问题。若依NP的流行定义，照理可以说“最短路径问题和旅行商问题一样都是NP问题”，但是人们从来不会这样说。那么，为什么用“多项式时间可验证”定义NP将P也说成是NP，就被接受而毫不质疑？

Reference :

[1] 概念的“相对性”

[2] 我们为什么说“确定型图灵机”不是“非确定型图灵机”的特例？

[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).