我们再从概念的“相对性”角度 [1][2][3]，解析基于“多项式时间可验证”的NP流行定义导致的关于NP的“歧义性”。
一，概念的“相对性”
概念用于指称事物，故需能够界定所指事物，使之与其他已知的相关事物区分开。在此意义上，概念具有“相对性”，即概念所指的事物总是相对于已知的相关事物。
自然语言存在“多义性”，即“一词多义”，指一个词可指称不同的概念。正是概念的“相对性”，使得说话的人能通过对所处的具体语境的认知来辨析词语所指，从而避免因语言的“多义性”而产生的“歧义性”。
形式语言却不容许自然语言那样的“多义性”，这是科学的严格性和逻辑的一致性所要求的，即所谓的“客观性”。然而，若无意识将自然语言的“多义性”带入科学领域，就会出现“歧义性”，导致概念偷换，产生难以察觉的认知偏差，NP概念的困难原因之一正出于此。
二，案例：英语词man
这里我们分析自然语言英语中man的“多义性”。man既可以指“人类”（human）也可以指“男人”（male 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与“不确定性”这个概念密切相关。对于“不确定性”，根据具体语境，人们既可以认为“确定性”是“不确定性”的特例，也可以认为“不确定性”与“确定性”相对。由概念的“相对性”可知，这是二个完全不同的“不确定性观念”！就像man指“人类”与“男人”不同一样，这样的“多义性”表达只能存在日常语言中。
在计算复杂性理论中，NP是一个严格的概念，不容许日常语言中那样的“多义性”。追本溯源，NP欲指“与P相对的NP”，即“P指易解的问题，而NP指难解的问题”，这样的“相对性（P versus NP）”决定了NP概念的定义。然而在现有的理论框架下，NP流行定义之一是基于“多项式时间可验证”，指NP问题的猜测解可在多项式时间验证，由于P也是多项式时间可验证的，故P包含在NP中，但“此NP非彼NP也”，于是把“歧义性”引入了计算复杂性理论中，从而P versus NP被偷换成P in NP，致“P vs 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)
＊＊＊＊＊＊
https://nptheory.blogspot.fr/2017/11/why-can-not-np-be-defined-as-polynomial.html
Why can not NP be defined as "polynomial time verifiable"? - Ambiguity of NP
In the current theory of computational complexity, NP is defined as the class of problems which solutions are verifiable in polynomial time. In this paper, from a view of concept cognition, we argue that this definition causes the ambiguity in understanding NP.
1. The polysemy of natural language and the consistency of formal language
Polysemy is the capacity for a word to refer to different concepts. The definition of a concept consists of properties that reflect the essence of a thing so that the concept can distinguish it from some other existing things. In this sense, a concept has the relativity, that is, it is defined relative to other concepts known.
It is the relativity of concept that enables speakers to recognize the context of a word and know which concept is referred to by a word, thereby to avoid the ambiguity of word due to its polysemy.
However, in formal languages, speakers are excluded in order to maintain 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.
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.
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 man actually 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, for 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
The essence of NP is related to nondeterminism. However, in natural language determinism can be considered as a special case of nondeterminism, or nondeterminism can be also considered to be relative to determinism, depending on the specific context. They are all different opinions about nondeterminism in natural language, referred as the polysemy of nondeterminism like the word man.
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. Consequently, the ambiguity of NP appears, and the P versus NP problem becomes a paradox, ...
Reference :
[1] Yu LI, What is NP? - Interpretation of a Chinese paradox "white horse is not horse" (https://arxiv.org/abs/1501.01906)
评论 (0)