What is the P versus NP problem?

http://en.wikipedia.org/wiki/P_versus_NP_problem

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

There is a US$ 1,000,000 prize to be won:

It is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute to carry a US$ 1,000,000 prize for the first correct solution.

Consequences of the resolution of the problem

If P = NP

1. Problems for cryptography:

Cryptography, for example, relies on certain problems being difficult. A constructive and efficient solution to an NP-complete problem such as 3-SAT would break most existing cryptosystems including public-key cryptography, a foundation for many modern security applications such as secure economic transactions over the Internet, and symmetric ciphers such as AES or 3DES, used for the encryption of communications data. These would need to be modified or replaced by information-theoretically secure solutions.

2. Positive breakthroughs for logistics and biology:

Efficient solutions to these problems would have enormous implications for logistics. Many other important problems, such as some problems in protein structure prediction, are also NP-complete; if these problems were efficiently solvable it could spur considerable advances in biology.

3. Revolution in mathematics:

According to Stephen Cook,

  ...it would transform mathematics by allowing a computer to find a formal proof of any theorem which has a proof of a reasonable length, since formal proofs can easily be recognized in polynomial time. Example problems may well include all of the CMI prize problems.

If P ≠ NP

A proof that showed that P ≠ NP would lack the practical computational benefits of a proof that P = NP, but would nevertheless represent a very significant advance in computational complexity theory and provide guidance for future research. It would allow one to show in a formal way that many common problems cannot be solved efficiently, so that the attention of researchers can be focused on partial solutions or solutions to other problems. Due to widespread belief in P ≠ NP, much of this focusing of research has already taken place.

In other words, If P ≠ NP, it means that there are many common problems whereby there is no universal algorithm for an exact solution and brute force or creativity is the only way to try and arrive at an approximate solution whether by humans, computers or nature with finite resources of space and time.

Why is the N versus NP problem relevant to philosophy?

In this paper by Scott Aaronson: http://arxiv.org/pdf/1108.1791v3.pdf

From the abstract:

One might think that, once we know something is computable, how efficiently it can be computed is a practical question with little further philosophical importance. In this essay, I offer a detailed case that one would be wrong. In particular, I argue that computational complexity theory—the field that studies the resources (such as time, space, and randomness) needed to solve computational problems—leads to new perspectives on the nature of mathematical knowledge, the strong AI debate, computationalism, the problem of logical omniscience, Hume’s problem of induction, Goodman’s grue riddle, the foundations of quantum mechanics, economic rationality, closed timelike curves, and several other topics of philosophical interest. I end by discussing aspects of complexity theory itself that could benefit from philosophical analysis.

From the conclusion:

The purpose of this essay was to illustrate how philosophy could be enriched by taking computational complexity theory into account, much as it was enriched almost a century ago by taking computability theory into account.

And from the criticisms of Complexity Theory:

(3) Complexity theory focuses on only a limited type of computer—the serial, deterministic Turing machine—and fails to incorporate the “messier” computational phenomena found in nature.

With so much at stake, resolution of the P verses NP problem and it’s relevance from a computational complexity perspective (with it’s strengths and weaknesses), is certainly a fertile realm for philosophical investigations.

And there is the chance of winning US$ 1,000,000 as well. 

programmers can see and calculate toward an event horizon but cannot reach it   mathematical language has limits   should P vs NP people propose a philosophy for mathematicians

arnoldg - 03 January 2013 10:29 AM

programmers can see and calculate toward an event horizon but cannot reach it   mathematical language has limits   should P vs NP people propose a philosophy for mathematicians

The event horizon is infinity which cannot be reached as it is without any limit.

The P versus NP problem is akin to a supertask.

http://en.wikipedia.org/wiki/Supertask

In philosophy, a supertask is a quantifiably infinite number of operations that occur sequentially within a finite interval of time. Supertasks are called “hypertasks” when the number of operations becomes innumerably infinite.

Philosophy of mathematics:

If supertasks are possible, then the truth or falsehood of unknown propositions of number theory, such as Goldbach’s conjecture, or even undecidable propositions could be determined in a finite amount of time by a brute-force search of the set of all natural numbers. This would, however, be in contradiction with the Church-Turing thesis.

Super Turing machines:

The impact of supertasks on theoretical computer science has triggered some new and interesting work (see Hamkins and Lewis — “Infinite Time Turing Machine”).

Davies’ super-machine:

This is a machine that can, in the space of half an hour, create an exact replica of itself that is half its size and capable of twice its replication speed. This replica will in turn create an even faster version of itself with the same specifications, resulting in a supertask that finishes after an hour. If, additionally, the machines create a communication link between parent and child machine that yields successively faster bandwidth and the machines are also capable of simple arithmetic, the supertask can be used to perform brute-force proofs of unknown conjectures.

Can such a machine be physically possible, with finite resources?

my first reading of the above seems to allow me to stay   my questions are about questions like N vs NP premises of time and space   as the only statement needed for a line of reasoning   this makes it more difficult to propose an axiomatic philosophy of time and space (N vs NP problem)  informal   has our thought progressed enough to state   observation space and time   as first principle when considering the boundaries of our dimension   rationale   time and space does not exist without observation   thanks

What does it mean for a solution to be ‘verified’ by a computer?

TromboneAndrew - 04 January 2013 11:58 AM

What does it mean for a solution to be ‘verified’ by a computer?

It means using a computer to determine whether a proposed solution is correct or incorrect.

arnoldg - 04 January 2013 10:50 AM

my first reading of the above seems to allow me to stay   my questions are about questions like N vs NP premises of time and space   as the only statement needed for a line of reasoning   this makes it more difficult to propose an axiomatic philosophy of time and space (N vs NP problem)  informal   has our thought progressed enough to state   observation space and time   as first principle when considering the boundaries of our dimension   rationale   time and space does not exist without observation   thanks

The assumption in the P versus NP problem is that there are finite resources of space and time to solve any P or NP problem which is a traditional realist position in the ontology of space and time.

Nevertheless, an axiomatic philosophy of space and time is not so clear-cut.

http://en.wikipedia.org/wiki/Philosophy_of_space_and_time

The subject focuses on a number of basic issues, including whether or not time and space exist independently of the mind, whether they exist independently of one another, what accounts for time’s apparently unidirectional flow, whether times other than the present moment exist, and questions about the nature of identity (particularly the nature of identity over time).

kkwan - 04 January 2013 11:35 PM

TromboneAndrew - 04 January 2013 11:58 AM

What does it mean for a solution to be ‘verified’ by a computer?

It means using a computer to determine whether a proposed solution is correct or incorrect.

Ah, okay. So, I take it that no one has ever found a case where a computer cannot possibly calculate a solution where a solution is known? Given what little I know of computer science, yeah, that does sound like a tough thing to actually prove that P=NP for all cases. It reminds me of a different computational problem, that of finding an algorithm that will always find the simplest logic circuit that will generate a specific output for a specific input.

establishing a philosophy   for limits of   the   time and space we live in (N vs NP)  proposes we will see questions without answers and answers without questions   at any time   our minds can understand and progress as will computers adapt   the role of observation for philosophy is different than the minds   is   (we = N vs NP)  progressional or transformational   what would transformational complexity be   thanks

TromboneAndrew - 05 January 2013 01:28 AM

Ah, okay. So, I take it that no one has ever found a case where a computer cannot possibly calculate a solution where a solution is known?

Not quite so. From the wiki on the P versus NP problem:

.....it asks whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer.

Quickly verifying a solution by a computer does not imply that the problem can be quickly solved by a computer.

Generally, quickly verifying a solution is relatively easy, whereas solving a problem is not so.

For instance, we can quickly and easily verify that a Sudoku or a jigsaw puzzle is solved by looking at the completed puzzle, but it would have taken many hours of trial and error to solve the puzzle.

If P = NP, then verifying the solutions to puzzles efficiently would imply the ability to find the solutions efficiently.

OTOH, if P ≠ NP, then verifying the solutions efficiently do not imply the solutions can be found efficiently.

arnoldg - 05 January 2013 03:51 PM

establishing a philosophy   for limits of   the   time and space we live in (N vs NP)  proposes we will see questions without answers and answers without questions   at any time   our minds can understand and progress as will computers adapt   the role of observation for philosophy is different than the minds   is   (we = N vs NP)  progressional or transformational   what would transformational complexity be   thanks

The P versus NP problem is about problems which can be solved in polynomial time (P) versus problems which can be solved in exponential time (NP).

http://en.wikipedia.org/wiki/Cobham’s_thesis

Cobham’s thesis, also known as Cobham–Edmonds thesis (named after Alan Cobham and Jack Edmonds), asserts that computational problems can be feasibly computed on some computational device only if they can be computed in polynomial time

Reasoning:

The thesis is widely considered to be a good rule of thumb for real-life problems. Typical input lengths that users and programmers are interested in are approximately between 100 and 1,000,000. Consider an input length of n=100 and a polynomial algorithm whose running time is n^2. This is a typical running time for a polynomial algorithm. (See the “Objections” section for a discussion of atypical running times.) The number of steps that it will require, for n=100, is 100^2=10000. A typical CPU will be able to do approximately 10^9 operations per second (this is extremely simplified). So this algorithm will finish on the order of (10000 ÷10^9) = .00001 seconds. A running time of .00001 seconds is reasonable, and that’s why this is called a practical algorithm. The same algorithm with an input length of 1,000,000 will take on the order of 17 minutes, which is also a reasonable time for most (non-real-time) applications.

Meanwhile, an algorithm that runs in exponential time might have a running time of 2^n. The number of operations that it will require, for n=100, is 2^100. It will take (2^100 ÷ 10^9) ≈ 1.3×10^21 seconds, which is (1.3×10^21 ÷ 31556926) ≈ 4.1×10^13 years. The largest problem this algorithm could solve in a day would have n=46, which seems very small.

in this search   polynomial time leaves little room for philosophical (exponential) time   but   is   N vs NP problem a challenge that requires a human response   always proposing new values and limits   for math and computers   thanks

arnoldg - 07 January 2013 03:27 PM

in this search   polynomial time leaves little room for philosophical (exponential) time   but   is   N vs NP problem a challenge that requires a human response   always proposing new values and limits   for math and computers   thanks

Polynomial time does not imply there is no conceptual room for exponential time or other categories of time.

http://en.wikipedia.org/wiki/Time_complexity

In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the string representing the input.

The challenge of the P versus NP problem is to show convincingly or prove:

1. P = NP

2. P ≠ NP

3. It cannot be shown or proved either 1 or 2, i.e. it is unprovable

4. It is undecidable

From this website: http://www.win.tue.nl/~gwoegi/P-versus-NP.htm

Note: The following paragraphs list many papers that try to contribute to the P-versus-NP question. Among all these papers, there is only a single paper that has appeared in a peer-reviewed journal, that has thoroughly been verified by the experts in the area, and whose correctness is accepted by the general research community: The paper by Mihalis Yannakakis. (And this paper does not settle the P-versus-NP question, but “just” shows that a certain approach to settling this question will never work out.)

Undecidable?

[Undecidable]: Nicholas Argall proved on 25 March 2003 that P=NP is undecidable. His main line of argument is that a provable answer to the P=NP question requires a complete and consistent formal statement of the question. Then he invokes Goedel’s theorem and deduces that P=NP is undecidable. The proof is actually quite short: ascii file

http://www.win.tue.nl/~gwoegi/P-versus-NP/argall.txt

There has been much debate surrounding answers to the question of P=NP. The problem is that we cannot answer the question until we have successfully asked the question.  The question is impossible to ask, that it why it will never be answered.

Comment: A conclusion which is not only proven in this paper, but supported by the years of argument between mathematicians regarding the relevance of proposed answers to the problem.

QED?

Goedel would be disappointed that we are so easily barred from a possible solution.

t

Is N dimensional (determined) in limits, answers in time and space (where it is)—-Is NP non-dimensional (nondetermined) in limits, questions in time and space (where is it);

another choice should be considered -  equal -  not equal -  unproveable -  undecideable   -  decideable, N vs. NP becomes an expression of relativity,  decideable relativity.
 
What’s interesting is time`s relevance in this,  we see quite clearly answers are the past while questions are the future,  observable verifiable in the present only;
  ,
answers become questions then questions become answers this is a the way nature works.  N vs. NP is not a problem in nature it’s an expression of nature’s way and observable,

a philosophy for computer science has-is-will be possible, as observation becomes the search engine of objective science,

  Wikipeadia helps:  Predicate—- predicate transformer semantics (either by weakest-preconditions or by strongest-postconditions——

    while:  Predicate Variable—-affirms the nature of relativity for variables and constants effected by time—-

thanks

Could you please tell me if the problem of the 400 students in 50 rooms, the one in the Clay web page, is an NP-C or not?