The P Versus NP Problem

[ProKeymaster]

The P Versus NP Problem

coe – ‘Re: The P Versus NP Problem’

You are mistaken. All problems in both P and NP can solved in a finite amount of time. The P vs NP question is not about determining whether problems in NP can be solved in a finite amount of time, but whether they can be solved efficiently.

Please refer to any of the following standard textbooks on complexity theory or automata theory for an accurate definition of the problem you are attempting to resolve:

1) Introduction to the Theory of Computation. Michael Sipser.

2) Automata Theory, Languages, and Computation. John Hopcroft, Rajeev Motwani and Jeffrey Ullman.

3) Algorithm Design. Jon Kleinberg and Eva Tardos.

Pro – ‘Re: The P Versus NP Problem’

Hello and welcome to the forum :)I’m sorry my understanding of P versus NP is not perfect, and I thank you for correcting me here.

All I’m trying to do is get to the absolute crux of the Millennium Problems, namely trying to find the singular answer the problems ask for and then suggesting three answers in place of one as per Pro theory.

In view of your corrective suggestions here, what I’m trying to say is that in theory we can suggest that these problems can be solved efficiently, cannot be solved efficiently plus neutral.

Anh Pham – ‘Re: The P Versus NP Problem’

Every question must have an answer, it can be true, false and simultaneously.

In simultaneous cases the answer is true with a No.1 condition and is false with condition No.2, so every problem in NP must has an answer by using a NDM or a “super super…super machine”. So everything here is up to time factor no exactly is up to technology, right?

In your theory you said it requires infinite time to solve problems in NP is wrong, it should be ” greater finite time”. if P=NP then everything is possible to solve, it means your TOE is an existing theory. But what happens if P not equal to NP, I know the answer, but I don’t talk in here. :welcomesign:

consonaut – ‘Re: The P Versus NP Problem’

Out of interest, I developed an algorithm aimed at solving the PvsNP “Room mate” problem listed at the Clay Institutes’s site. The algorithm does find all possible compatible room mates (if any exist), for the set of 400, given any number of random pairs.

It arrives at the list of compatible room mates (with possible alternates) in about 1-2 seconds.After contacting Prof. Cook, I am a little confused at what exactly is to be proven. Based on Prof. Cook’s feedback, the solution must actually produce the complete list of all possible sets of 100 students within a limited timeframe.

While that would be easy to write, now that I have the full list of all mutually compatible room mates, it would obviously take forever to run.So finding the possible solutions turns out to be easy.

Printing (or otherwise recording) all possible combinations of the 100 mutually compatible students from the set of all possible mutually-compatible students seems a tad ridiculous, since, in testing, almost all cases result in a very large number of combinations (or result in less than 100 compatible room mates).

For example, in one test using 2000 randomly generated pairs, there were 110 mutually-compatible students. So we have 110 choose 100 combinations to start with. Furthermore, the compatible students may have alternates that can be substituted for them without invalidating the solution. In this case, there were 31 students with one alternate, 15 students with 3 alternates, and 1 student with 4 alternates.

The remainder had no alternates. So we end up with [110 choose 100] * 2**31 * 3**15 * 4 total possible ways to choose 100 compatible students from the set of 110 (including alternates). An equivalent problem would therefore appear to be “develop a proof that you can start at 1 and add 1 to the previous total 100000000**100000000 times and print it out”, or any other trivial task that would require a very long time to run. What am I missing?

AdamMedici – ‘Re: The P Versus NP Problem’

A buddy of mine used to work for Google doing algorithms, and we would get together to drink Guinness and talk binary code. The way I understand it after many a drunk night is like so: A computer so long as it’s able to do so, will compute any problem even one that takes an infinite amount of time, however not every computer will.

Some give up and some crash. To avoid crashing the machine could be programmed to calculate an infinite problem for a set amount of time predetermined by the programmer. After this set amount of time a variable can be given to the infinite set.

Kinda like Einstein just saying “c” as a constant for the speed of light. or pi instead of 3.141592653589793 and on and on and on and on…. ad infinitum. After a set time the computer can substitute a constant for all problems taking longer than X amount of time.

It’s not an exact answer but it does avoid the computer from crashing.

Pro – ‘Re: The P Versus NP Problem’

@ consonaut, welcome to the forum, thanks for joining us here :thumbup: All I know for sure, as it were, is that P versus NP asks us for a singular answer. All of the Claymath problems in their own ways uncover the fundamental ambiguity of the universe.

There comes a point in all study where we get so deep that it seems as if we only knew the one answer to a certain question or equation we would win the game. The problem comes when we try to ‘prove’ our answer.

All I can really say is that there is both a way of solving P/NP but also an opposite and neutral option in the mix. Pretty general at best isn’t it, but that’s often how it is when we deal with problems this massive. Ultimately the highest problems in math come down to asking whether a certain pattern holds true (i.e. doesn’t ever change) and whether the outcome of said pattern/process can be expressed singularly, meaning with no possible opposing statement or observation.

This classic approach of right and wrong works well in everyday life of course (we ignore neutrality usually) but all questions have three possible answers or outcomes, subject to change. My point is that no matter how infeasible it seems there will always be an opposing (literally an opposite) answer to every question, no matter how well proven it is. Err, yeah, think that’s what I meant :headscratch:

Pro – ‘Re: The P Versus NP Problem’

Computers crash or lock up simply because they are programmed to use two, not three, options. Many new languages may address this problem but they still run on hardware built for 1s and 2s so when something of a 3rd option occurs, from time to time as it is apt to do, they cannot process it and break as it’s not a 1 or a 2 directive simply put.

[Author]

Posts