## Comments about "NP (Complexity)" in Wikipedia

This document contains comments about the document NP (Complexity) in Wikipedia
• The text in italics is copied from that url
• Immediate followed by some comments
In the last paragraph I explain my own opinion.

## Index

### Introduction

The article starts with the following sentence.
In computational complexity theory, NP is one of the most fundamental complexity classes.
By reading the article I get the impression there 4 complexity classes.
The full list is: P, NP, NP-Complete and NP-Hard ?
The abbreviation NP refers to "nondeterministic polynomial time."
To use the word "nondetermistic" is misleading.
Intuitively, NP is the set of all decision problems for which the 'yes'-answers have efficiently verifiable proofs of the fact that the answer is indeed 'yes'.
Total unclear sentence
More precisely, these proofs have to be verifiable in polynomial time by a deterministic Turing machine. In an equivalent formal definition, NP is the set of decision problems where the 'yes'-instances can be recognized in polynomial time by a non-deterministic Turing machine.
Concepts like "deterministic Turing machine" and "non-deterministic Turing machine" can not be used to explain something clearly
See also my comments in Comments about "Non-deterministic Turing machine" in Wikipedia
The equivalence of the two definitions follows from the fact that an algorithm on such a non-deterministic machine consists of two phases, the first of which consists of a guess about the solution, which is generated in a non-deterministic way, while the second consists of a deterministic algorithm that verifies or rejects the guess as a valid solution to the problem.
Totally unclear. You can not mix deterministic with non-deterministic.
The complexity class P is contained in NP, but NP contains many important problems, the hardest of which are called NP-complete problems, whose solutions are sufficient to deal with any other NP problem in polynomial time.
In this sentence two different complexity classes are mentioned.
The most important open question in complexity theory, the "P = NP problem", asks whether polynomial time algorithms actually exist (1) for NP-complete, and by corollary, (2) all NP problems.
Why all?
It is widely believed that this is not the case.
For (1) or for (2) or both ?
Before invastigating this claim it is important to make a list of all programs which belongs to each set (and inditify the differences)

For comments about Euler Diagram see: Euler diagram for P, NP, NP-Complete and NP-hard set of problems

### 1. Formal definition

This paragraph starts with the text:
The complexity class NP can be defined in terms of NTIME as follows: NP = some function of NTIME
Totally unclear.
Alternatively, NP can be defined using deterministic Turing machines as verifiers.
Please explain in detail.

### 2.1 Verifier-based definition

Many natural computer science problems are covered by the class NP. In particular, the decision versions of many interesting search problems and optimization problems are contained in NP.
Why using such unclear language.

### 2. Introduction

Many natural computer science problems are covered by the class NP. In particular, the decision versions of many interesting search problems and optimization problems are contained in NP.
Why using such unclear language.

### Euler diagram for P, NP, NP-Complete and NP-hard set of problems

• The Euler diagram at the left side defines the relation between decision problems and the comlexity classes.
The full list of complexity classes is: P, NP, NP-Complete and NP-Hard ?
There are 4 types of problems:
1. which are strictly NP
2. which are both NP and P
3. which are NP and NP hard. They are called NP-Complete
4. which are strictly NP Hard
What the diagram shows that there are no problems with are both P and NP-Complete
• The Euler diagram at the right side makes a bold assumption. The first three types of problems are all combined in one. i.e P = NP = NP-Complete.
• Why this paradigm shift?
• Why all?

### For Further reading

See the following documents which show comments about different Wikipedia documents:

### Feedback

None

If you want to give a comment you can use the following form Comment form
Created: 9 December 2014

Back to my home page Index