1

While there are already lot of questions on this topics here on Mathematics (1,2, 3) and several (too many perhaps) Wikipedia pages on the subject (a, b, c), they all involve concepts that I am not familiar with (e.g. Turing machine, strings, Hamiltonian circuits, the concept of mathematical proof itself..), so I still have lot of confusion.

Let me see what I understood and what I still miss.

A problem is given by a set of rules that given an input returns true/false, i.e. the input satisfy or not the rules of the problem.

A problem is classified as of class P if it exists at least one algorithm that given some input and a set of rules, returns either an output that is guaranteed to satisfy the problem or a declaration that no feasible outputs are possible with that input, and this algorithm has a computational "cost" (whatever this is) that growths in polynomial way with the size of the inputs.

FIRST doubt: the problem or the algorithm itself is of "class P" ?

A problem is classified as of class NP if at least one algorithm exists that given an input (for example obtained as result of the algorithm above) and a set of rules it can verify if the rules are satisfied with a computational "cost" (whatever this is) that growths in polynomial way with the size of the inputs.

SECOND doubt: what is the relation with deterministic/non-deterministic here ?

So the "P = NP" or not refers to the possibility that problems exists whose rules can be verifies in polynomial time (NP), but no algorithm to provide solution to the rules (given an input) can exist in polynomial time (P ≠ NP) or at the opposite that all NP problems must have an (perhaps yet undiscovered) algorithm that find feasible solutions in polynomial time (P = NP).

THIRD doubt: what are "NP-complete" and "NP-hard" problems ?

The Wikipedia entry is a bit cryptic: "But NP contains many more problems,the hardest of which are called NP-complete problems. An algorithm solving such a problem in polynomial time is also able to solve any other NP problem in polynomial time." How can algorithm devised for a specific problem can be used to find solutions to any problem ?

Antonello
  • 261
  • 3
    I would recommend a book on complexity theory or some lecture notes from a course. It will give you clear and systematic answers to these questions, much better than bits and pieces of Wikipedia or other places online. These concepts are simple, but sufficiently "delicate" that it is easy to fall in various traps and therefore the internet is full of confusing, wrong or imprecise explanations. – Michal Adamaszek Mar 16 '23 at 09:32
  • @MichalAdamaszek: thanks, do you have any to suggest of introductory level ? – Antonello Mar 16 '23 at 11:01
  • Here is a nice explanation of "P, NP, NP-complete and NP-hard" by Kaveh. It is the most-upvoted answer on computer science. – Apass.Jack Mar 21 '23 at 16:30

1 Answers1

1

The slides in this link look quite reasonable as a very short and gentle introduction:

https://user.it.uu.se/~justin/Assets/Teaching/AD2/Slides/34-PversusNP.pdf

Short approximate answers to your questions:

FIRST doubt: the problem or the algorithm itself is of "class P" ?

It is the problem that is of class P, since you can always have a horrible non-polynomial complexity algorithm for solving an easy problem.

SECOND doubt: what is the relation with deterministic/non-deterministic here ?

The verification of a claimed solution is efficient (polynomial complexity) but it is also permissible to use a randomized algorithm for verification. For example, there are randomized algorithms for primality testing, e.g., Miller-Rabin (which can be used for checking a claimed prime) which for a long time were the only known polynomial time algorithms for that specific problem (i.e., no deterministic polynomial time algorithm was known).

How can algorithm devised for a specific problem can be used to find solutions to any problem ?

All this refers to is the following. Suppose a problem is hard, say NP-complete, thus of exponential complexity. Then there is a polynomial complexity reduction of this problem to another NP-complete problem, and since all such problems can be reduced to each other this way (the extra complexity added by the reduction is negligible) all such problems are "equally hard" in some theoretical sense.

These notes (on pages 4-7) have an example of such a reduction between vertex cover and satisfiability.

kodlu
  • 9,338