Algorithms & Optimization

 

P NP NP-complete NP-hard

More of what we think the world looks like.

The P=NP? problem was emerged in 1971. This is one of the longstanding unresolved problems in computer science. Its solution is directly related to the determination of time complexity of NP-complete problems. Not all problems can be solved quickly.
So, it is very difficult to figuring out exactly which ones could be solved and which ones couldn’t.
Steve Cook and Dick Karp decided that any efficient algorithm is that which runs in polynomial time:

  • P – the class of polynomial-time problems
  • Time complexity of these problems is O(nc) for some constant c. Cook, Karp, and others, defined another class of so called NP-complete problems all of which exhibit precisely the same phenomena:

Stephen Cook. The complexity of theorem-proving procedures. In Conference Record of Third Annual ACM Symposium on Theory of Computing, pages 151–158, 1971.[Referat_on_P=NP]

  • no NP-complete problem can be solved by any known polynomial algorithm
  • if there is a polynomial algorithm for any NP-complete problem, then there are polynomial algorithms for all NP-complete problems
  • NPC-the class of NP-complete problems
  • Time Complexity of NP-complete problems has not decided yet

This is one of the most difficult unresolved problems in Computer Science.
It’s accepted that the problem Does P=NP? has been open since it was posed in 1971.

The nature of NPC Problems

More than 1000 diverse algorithmic problems in NPC exhibit precisely the same phenomena:

  • no NP-complete problem can be solved by any known polynomial algorithm;
  • if there is a polynomial algorithm for any NP-complete problem, then there are polynomial algorithms for all NP-complete problems.
  • NPC class problem contains around 1000 different algorithmic problems
  • The problem exists in following areas
    • Combinatorics
    • Operation Researches
    • Economics
    • Graph & Game Theory
    • Statistics
    • Logic
    • High- Energy Physics and X-Ray crystallography
    • Protein Design etc.

Any simple Timetable Problem is NP-complete. After about seventeen years of researches Karlen G. Gharibyan finally invented the Peaceful Coexistence Algorithm. This is a polynomial time algorithm that solves the General Timetable Problem (GTP) for any instances.

Karlen G. Gharibyan proved that P=NP. Nobody rejected it.

 Karlen G. Gharibyan, Does P=NP?, in Proceedings of the first international Arm Tech Congress 2007.[PDF]

This means, that each problem in NP may be solved in polynomial time, including 3SAT problem.
Here is the demo how works Peaceful Coexistence Algorithm®

Content on this page requires a newer version of Adobe Flash Player.

Get Adobe Flash player

Comments are closed.