Comments about "NP Complete" in Wikipedia

This document contains comments about the document "NP Complete" in Wikipedia
In the last paragraph I explain my own opinion.

Contents

Introduction

The article starts with the following sentence.
In computational complexity theory, a decision problem is NP-complete when it is both in NP and NP-hard.
The abbreviation NP refers to "nondeterministic polynomial time".
This definition of NP is in conflict, when you compare this which what is written in Wikipedia about: P versus NP problem .
Which reads: "The class of questions for which an answer can be verified in polynomial time is called NP."

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

1. Overview

2 Formal definition of NP-completeness

A decision problem "C" is NP-complete if:
  1. "C" is in NP, and
  2. Every problem in NP is reducible to "C" in polynomial time
"C" can be shown to be in NP by demonstrating that a candidate solution to "C" can be verified in polynomial time.
What means "C" is in NP ?
Why mention "every problem". Such a concept is not very realistic.
What are candidate solutions?
This definition is not clear

3. Background

Nobody has yet been able to determine conclusively whether NP-complete problems are in fact solvable in polynomial time, making this one of the great unsolved problems of mathematics.
This whole issue depents very much about an accurate definition of what are NP-complete problems and what means polynomial time

4. NP-complete problems

This paragraph contains a list of "known NP-complete problem"
The easiest way to prove that some new problem is NP-complete is first to prove that it is in NP, and then to reduce some known NP-complete problem to it.
This raises the same questions as above: IMO you has to establish that two problems in some way are identical, but what that is is not clear.

5. Solving NP-complete problems

At present, all known algorithms for NP-complete problems require time that is superpolynomial in the input size, and it is unknown whether there are any faster algorithms.
What has superpolynomial in the input size to do with the "NP-complete problem"?
Why mention: "and it is unknown whether there are any faster algorithms" etc ?
This whole sentence does not make sense?
The following techniques can be applied to solve computational problems in general, and they often give rise to substantially faster algorithms:
What has the whole list to do with the "NP-complete problem" ?
  • Approximation: Instead of searching for an optimal solution, search for an "almost" optimal one.
The most important constraint of the "Travelling Salesman problem" is to find an optimal solution i.e. the shortest. An "almost" optimal solution is not a solution.

For Further reading

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

Reflection

Feedback

Read: Nature News: Million-dollar problem cracked? At the end there is a comment by the author.

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