Properties

In physics we have the idea of extensive and intensive properties. An extensive property. such as volume, is one that depends on the whole system. An intensive property, such as temperature, is one that depends on just a part of the system. In the same sort of way you can think of the property of being divisible as an extensive property that demands a search for a divisor whereas being prime is an intensive property that depends on something inherent in the number and needs no search.

So what does this mean for P=NP?

As prime testing is in NP, surely finding a polynomial solution means that it is in P, and hence NP=P. Not so, because prime testing is not NP complete. An NP complete problem is one that typifies the entire set of NP problems and a polynomial solution to an NP complete problem would provide a polynomial solution to all NP problems. If this were the case then indeed P=NP. 

The travelling saleman problem is NP complete and proving that there is a solution in P would also prove that P=NP. When you think about the task it seems very unlikely that there is a solution to the travelling salesman problem that doesn't involve a complete search. To prove that this is the case you would need to find an intrinsic property that indicates the size of the smallest tour to avoid the need for a search.

Conversely, if you can prove that there is no such property, then you have proved that P!=NP. 

The story about primality testing should suggest to you that either outcome is possible despite what seems obvious to you at this time.

However, it is worth noting that the lesson of primality testing might not be a good guide. It is not NP complete and its search is subtly different from the search involved in an NP complete problem. It may be that primality testing is a lesser problem that makes no suggestions as to what might happen for an NP complete problem.

Related Articles

P ? = NP

Proof of P≠NP?

Neural Networks Take On Traveling Salesman

Amoeba Solves Traveling Salesman Problem

The XY Traveling Salesman Problem Solved

Traveling Salesman Applied To DNA Synthesis

The Physical Travelling Salesman Challenge

Classic Nintendo Games Are NP Hard       

Physics Is NP Hard       

Pancake flipping is hard - NP hard       

A Programmers Guide To Theory

Now available as a paperback and ebook from Amazon.

Contents

1. What Is Computer Science?
   Part I What Is Computable?
2. What Is Computation?
3. The Halting Problem
4. Finite State Machines
   Extract 1: Finite State Machines
   Extract 2: Turing Thinking
5. Practical Grammar
6. Numbers, Infinity and Computation
   Extract 1: Numbers 
   Extract 2: Aleph Zero The First Transfinite
   Extract 3: In Search Of Aleph-One
   Extract 4: Transcendental Numbers
   
7. Kolmogorov Complexity and Randomness
   Extract 1:Kolmogorov Complexity 
   Extract 2: Random?  
8. The Algorithm of Choice
9. Gödel’s Incompleteness Theorem 
10. Lambda Calculus
    Part II Bits, Codes and Logic
11. Information Theory 
12. Splitting the Bit 
13. Error Correction 
14. Boolean Logic 
    Part III Computational Complexity
15. How Hard Can It Be?
    Extract 1: Where Do The Big Os Come From
16. Recursion
    Extract 1: What Is Recursion
    Extract 2: Why Recursion
17. NP Versus P Algorithms
    Extract 1: NP & Co-NP
    Extract 2: NP Complete

<ASIN:1871962439>

<ASIN:1871962587>

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info