Exploring The Relationship Between P=Np And Membership In Ph

The P versus NP Problem

The P versus NP problem is a major unsolved problem in computer science and mathematics. It asks whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer.

P refers to the complexity class containing decision problems that can be solved in polynomial time by a deterministic Turing machine. Polynomial time means the time taken grows at most as a polynomial function of the input size n, such as n2 or n3.

NP refers to the complexity class containing decision problems where the solutions can be verified in polynomial time by a deterministic Turing machine, even if the problem itself cannot be solved in polynomial time.

Table of Contents

Examples of P and NP Problems

Here is an example of a problem in P:


Function is_prime(n):
  For i from 2 to sqrt(n):
    If n mod i == 0:
      Return false
  Return true

This primality testing algorithm runs in polynomial time O(sqrt(n)), so prime number detection is in P.

Here is an example of a problem likely to be in NP:


Function traveling_salesperson(graph):
  For each possible tour of all nodes in graph:
    If tour length <= threshold:
      Return true
  Return false

Checking if a traveling salesperson route meets a certain length threshold can be done in polynomial time O(n) where n is number of nodes. But there are (n-1)! possible routes, so exhaustive search takes exponential time. This problem is likely NP-complete.

Implications of P=NP

If P=NP, it would have staggering implications both for computer science and mathematics. Technically, it would mean every problem with verifiable solutions can be efficiently solved by an algorithm that runs in polynomial time.

Practical implications would include:

Faster algorithms for complex optimization tasks like protein folding, scheduling, and more
Better predictions for stock prices, election outcomes, and other forecasting
Ability to easily break cryptographic protocols like RSA that rely on certain problems being computationally difficult

Relationship with Polynomial Hierarchy

The polynomial hierarchy (PH) is a hierarchy of complexity classes containing problems more difficult than NP, but still solvable in polynomial time with an oracle capable of solving NP problems instantly.

If P=NP then the polynomial hierarchy collapses completely, meaning PH = P = NP. So the relationship between P vs. NP can be viewed through the lens of PH.

Membership in PH

We now drill deeper into what it means to have a problem reside within PH.

Definition of PH

PH consists of an infinite hierarchy of complexity classes:

PH = {Σp0, Σp1, Σp2, ... Σpi, ...}

Where:

ΣP0 = P
ΣP1 = NP
ΣPi+1 = NP(ΣPi)

For higher levels i > 0, ΣPi refers to the set of decision problems solvable by a nondeterministic polynomial time Turing machine, with access to an oracle for solving problems at the previous level ΣPi-1.

Levels Examples of PH

Here are some examples of problems complete for different levels of PH under polynomial time reductions:

ΣP1 = NP - Satisfiability testing, traveling salesperson
ΣP2 - Validity problem for quantified Boolean formula’s with 2 alternating quantifiers
ΣP3 - Subgraph isomorphism problem for 3 colorable graphs
ΣP4 - Validity problem for quantified Boolean formulas with 4 alternating quantifiers

As you go up the hierarchy, you use quantifiers to alternate between existential questions (is there some x that satisfies...) and universal questions (is it true for all y that...). Higher classes capture more complex nuances in logical statements.

Consequences if P=NP

If P=NP, then the entire polynomial hierarchy collapses to just P (or NP). That would effectively mean NP = PH, since all the higher complexity classes would disappear and be equivalent to just polynomial time.

This would be a shocking development, implying that any type of logical statement involving quantifiers and relationships between objects becomes easy to evaluate, given an NP oracle. But most experts believe PH forms an infinite hierarchy of strictly harder complexity classes, not reducible to P.

Current State of Research

There remains much interest yet no definitive resolution to whether P=NP. We summarize some key facts in the debate.

Evidence For and Against

For:

No proof yet that P≠NP
Many resolved problems turned out to have efficient algorithms, defying expectations (linear programming)

Against:

Problem stumped finest minds for decades
No fundamental hardness-based cryptography schemes found yet if P=NP
P=NP seems inherently counterintuitive to how computation and verification work

Approaches

Some promising approaches researchers are taking:

Connecting complexity to physics ideas through Hamiltonian complexity
Using logic identity testing and interactive proof systems
Leveraging approximation and conditional hardness to rule out algorithms
Exploring if cryptographic one-way functions can exist only if P≠NP

There are also prizes offered for resolving P vs. NP, including the $1 million Clay Millennium Prize.

Conclusion

In summary, the relationship between P vs. NP has close connections to the polynomial hierarchy PH in computational complexity theory. A proof that P=NP would collapse PH and lead to stunning algorithmic breakthroughs in optimization and logic domains. After decades no consensus has emerged and the problem remains outstanding among mathematicians and computer scientists around the world.