P = NP?

[Agamemnus]

Ok, I understand, but in the most efficient case for each of these, there are still more computations going on. Parallel computations means that more information travels back and forth...

So basically, anyways, the P=NP? problem is really:

"Is there a method which could be used to convert a linear-time-n algorithm from infinitely parallel computer to algorithm in a deterministic computer, using the same amount of time?"

And I say "no" because the transfer of information within the computer increases as the amount of parallel processors increase. 2 parallel processors <> 3 processors and so on.

Analogy time!

Case 1:
According to some fundamental law of the universe, one photon travels through space-time in the universe, back and forth to every possible space and time location and we perceive it as many but it is actually one.

Case 2:
According to some fundamental law of the universe, there are many photons that travel through space-time and each photon has a life-span.

The result is the same but the idea, the "law" is different. The only difference in these cases is the definition of the photon. The analogy is 99.999% the same. The same amount of computations are performed, but differently, and a different amount of "space" and "time" is used to solve the problem. One assumes infinite time, the other infinite space (infinite photons?).

[LooseCaboose]

Ok, I understand, but in the most efficient case for each of these, there are still more computations going on. Parallel computations means that more information travels back and forth...

Non-deterministic turing machines are a bit different than normal parallel computers, when a non-determinisitic turing machine encounters a problem that requires multiple tests, in my previous example it takes multiple tests to determine if Y is a multiple of 1..X, the non-deterministic turing machine does all of these tests together (even if there are infinitely many of them) and picks the correct one in linear time. Therefore to run it on a deterministic machine in polynomial time we need to know the answer ahead of time, this is the idea of 'certificates' or the 'right information'.

So basically, anyways, the P=NP? problem is really:
"Is there a method which could be used to convert a linear-time-n algorithm from infinitely parallel computer to algorithm in a deterministic computer, using the same amount of time?"

Yes, the conversion algorithm must take polynomial time, but thats is the basic gist of the problem. If you can prove it for a single NP-Complete problem (the hardest NP problems) then it can be followed that it is true for every NP problem.

Currently it cannot be proven that N = NP and it cannot be proven that it isnt. I believe that most proofs, such as the code I posted above will be useless anyway because they will need a nondeterministic turing machine to run on and they dont actually exist.

Turing/Infinity/Halting theory makes my head hurt ;-)

[Agamemnus]

ok, so let's try this problem:

n inputs that consist of integers and n2 inputs that consist of integers. The task is to figure out whether the n1 set has all the numbers that the n2 set has.

Here is one way to do it in a deterministic machine:
Compare each of these inputs with an output set by sequentially checking each of the n inputs in each slot. If there is a match, return YES and end.

ex:
comparison set: 7 7 7
input numbers: 5 7 6
test goes like this:
(load with first input #)
5 5 5
6 5 5
7 5 5
5 6 5
6 6 5
7 6 5
5 7 5
6 7 5
7 7 5

5 5 6
6 5 6
7 5 6
5 6 6
6 6 6
7 6 6
5 7 6
6 7 6
7 7 6

5 5 7
6 5 7
7 5 7
5 6 7
6 6 7
7 6 7
5 7 7
6 7 7
7 7 7 ------ return YES and end

This takes 3*3*3 steps for n1=3 and n2=3. n = n1 + n2. It takes (n/2)^(n/2) steps.

For a non-deterministic machine, this takes a linear amount, n, of steps. It can be checked in n steps.

Now, replace this problem with any NP complete problem.

And now I will give you a more efficient algorithm for a deterministic machine:

Create a binary tree to hold all n1's.
Run through each n2 and report on whether an n1 is found. If even one time an n1 is not found return NO. Otherwise, at the end, return YES.

It takes log2(n1) (linear) amount of time to create the binary tree. (even if it is different, it's not a^n, though!!)
It takes log2(n1) time for each n2, and therefore n2(log2(n1)) time to compare.

The total time is log(n/2) + (n/2)*log2(n/2), which is clearly a non-exponential amount of time. It is not as fast as n steps, but it is not as slow as n^2.

[Mango]

I want to solve the greatest mystery in computer science, but I can't if I don't know what it means!

what [does] the question "Is P = NP?" mean.

PLEASE!

The guys at the sci.crypt newsgroup discuss this regularly...They may be willing to whack you over the head with a 2x4, if you are in need of a sound whacking. Loose Caboose gave you some of his valuable time and very nice explainations, if you are not in need of a 2x4 whacking.

[LooseCaboose]

Okay, heres an example of an NP-Hard problem.
http://en.wikipedia.org/wiki/Traveling_salesman_problem

Given a number of cities n, each with a link to every other city and and an associated cost, determine the cheapest round trip route that visits every city. The only known algorithm for solving this with the correct answer, is to try every single route, of which there are n!, a number of heuristic algorithms are known that can produce a low cost route (not necessarily the best, but close) in polynomial time.

The problem is, say you have 10 cities, you have 9 choices for a city to visit next. You could pick the one with the lowest cost, but that may lead to a high cost in the long run. The only way to know for sure is to follow all routes, this is where the non-deterministic turing machine comes in, we follow all routes simultaneously, then at the next step, we follow all routes (8 of them for each of the 9 cities we just visited). At the end, which we reach in polynomial time on the non-determinisitic machine, we simply pick the correct answer. You cannot do this on a deterministic machine.

[Agamemnus]

I know about the salesman, but you didn't comment on mine....

[LooseCaboose]

I really dont understand what you example is about, here is an implementation of your problem in C:

Code:

#include <stdio.h>

int main() {
  int i, j, found;
  
  int n1[] = {7, 7, 7};
  int n2[] = {5, 7, 6};
  
  for(i = 0; i < sizeof(n1) / sizeof(int); i++) {
    found = 0;
    for(j = 0; j < sizeof(n2) / sizeof(int); j++) {
      if(n1[i] == n2[j]) found = 1;
    }
    if(found == 0) {
      printf("No\n");
      exit(0);
    }
  }
  printf("Yes\n");
  exit(0);
}

The algorithm determines whether all of the elements in n1 are also in n2. If we say that the size of n1 = n and the size of n2 = m, then the complexity of this algorithm is O(nm) which is linear time, ie it belongs to the P class of problems. How is this relevant to the problem at hand?

In order to solve the N = NP problem, you need to work with the exist NP-Hard or NP-Complete problems, such as the travelling salesman problem, not make up some problem and then show that you can solve it on a deterministic machine.

Now, replace this problem with any NP complete problem.
And now I will give you a more efficient algorithm for a deterministic machine:

I did replace it with an NP problem, I replaced it with the travelling salesman problem, now can you show me the more effecient algorithm for solving this in polynomial time on a deterministic machine. Hint, if you can then you will be 99% of the way to solving the P = NP problem.

[Agamemnus]

The original algorithm is not linear, and neither is yours. Your example is (n^2/2).

The original example takes (n/2)^(n/2) steps because it checks things the stupid way. It keeps replacing numbers until it gets the right string on the whole. Now, you can't say "But there's a more efficient algorithm" because that makes the whole argument of trying to find a more efficient algorithm to prove N=NP pointless.

The next example, again, takes log2(n/2) + (n/2)*log(n/2)

[LooseCaboose]

The original algorithm is not linear, and neither is yours. Your example is (n^2/2).

Sorry, typo. If both of the arrays are the same length, then the complexity is O(n^2), which is /polynomial/ time on a deterministic machine.

Now, you can't say "But there's a more efficient algorithm" because that makes the whole argument of trying to find a more efficient algorithm to prove N=NP pointless.

No, that /is/ the whole argument. The P = NP problem cannot be solved because there are no more effecient algortithms known for any of the problems in NP. If you discover an algorithm for an NP (preferably NP-Complete) that allows you to solve it in polynomial time on a deterministic machine then you have solved the problem and can collect your million dollars: http://en2.wikipedia.org/wiki/Millennium_Prize_Problems

You /cannot/ solve the P = NP problem by creating your own ineffecient algorithm, showing that it belongs to the NP class, re-writting the algorithm so that it belongs to the P class and then claiming that it follows that all NP problems must also be in P. Thats ludicrous.

There are two main ways that you can answer the greatest open question in computer science, one is to show that an P-class algorithm exists for one of the NP-Complete problems (ie the travelling salesman problem), remembering that NP-Complete means the hardest problems in NP and the least likely to be in P, or you could disprove that P = NP by way of a logical contradiction, ie by assuming that there is some program that can convert NP problems to P problems and then proving (conclusively) that such an program is impossible by definition.

Why do you have this desire to solve problems that are /way/ out of your league, your first post stated that you wanted to solve the problem but you didn't really know what it meant, now a few days later you seem to believe that you have ammased enough knowledge on the subject to solve one of computer sciences great mysteries. Start by learning about problems (ie reading more than one source of information on them) and asking questions about why the problems haven't been solved yet.

[Agamemnus]

I read the problem description in the Clay Mathmatics Institute website, but I couldn't make much sense out of it. Neither can I make sense of this:

Code:

There are two main ways that you can answer the greatest open question in computer science, one is to show that an P-class algorithm exists for one of the NP-Complete problems (ie the travelling salesman problem), [b]remembering that NP-Complete means the hardest problems in NP and the least likely to be in P[/b], or you could disprove that P = NP by way of a logical contradiction, ie by assuming that there is some program that can convert NP problems to P problems and then proving (conclusively) that such an program is impossible by definition.

You are subjectively defining what a hard or easy problem is. Now, see, by your logic, if I figure out a way to solve the traveling salesman problem with dimension greater than 2, and everyone slaps themselves, then it's not a hard problem anymore. You would therefore apply the same argument as you just did against my example again.