This is an archive of past discussions. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page. |
Archive 1 | Archive 2 | Archive 3 |
P = NP problem - Wikipedia, the free encyclopedia 1 Context of the problem; 2 Formal definitions for P and NP ... and tM(w) = number of steps M takes to halt on input w. ..... in polynomial time is b bits long, the above algorithm will try 2b-1 other programs first. ... The Journal of the Operational Research Society 34 (10): 927–934. doi:10.2307/2580891. ... http://en.wikipedia.org/wiki/P_%3D_NP_problem
The above is the 4th search result here:
link —Preceding
unsigned comment added by
64.183.31.242 (
talk) 00:28, 14 July 2009 (UTC)
I am adding to this topic,simply to say how wonderful this topic is and to give props to sexy minds collaberating together. myspace.com/Mixtressginger —Preceding
unsigned comment added by
68.108.27.43 (
talk) 18:45, 24 July 2009 (UTC)
And I am come to explain it is interesting me the name you have chosen with respect to this discussion. —Preceding unsigned comment added by 69.230.178.14 ( talk) 19:24, 30 July 2009 (UTC)
I'm reluctant to contribute to the Wikipedia and hack someone else's text, but I'd like to point out that prime factorization and NP-completeness don't have anything to do with each other (or at least, nobody to my knowledge has shown that they do). The article gives the misleading impression that if someone were to prove P=NP, cryto-algorithms that rely on the hardness of factorizing prime numbers would be in jeapordy. It would be better, IMO, to stick to propositional SAT to illustrate the difference between P and NP. (as per the article on NP-completeness, which, it seems to me could well be subsumed in the discussion of the two complexity classes.
BTW, I rather disagree that a proof that P = NP would have no practical consequences, but that's another discussion.
- Andre Vellino ([email protected])
At the risk of reviving old discussion, I'd like to set the record straight here: If someone proved P=NP then those crypto algorithms WOULD be in jeopardy. Factorization is in NP, even if it's not proven to be NP-Complete, if P=NP then everything in NP, NP-Complete or not, is poly-time solvable. A poly-time algorithm to factor would destroy the assumption that factoring is effectively a one-way problem that is made by public key cryptosystems. 74.12.143.44 ( talk) 08:14, 26 November 2007 (UTC)
Talk:P = NP problem - Wikipedia, the free encyclopedia—David Eppstein (talk) 07:24, 4 June 2009 (UTC) ... Per M.B.A. Matthew Cherian (backs claim by Musatov): First of all you notion that there are n! routes ...
link —Preceding
unsigned comment added by
99.18.215.162 (
talk) 06:34, 1 August 2009 (UTC)
No. 71.130.130.81 ( talk) 06:03, 14 August 2009 (UTC)
This question was asked on
http://www.slashdot.org a little while ago, and it seems relevant here: What, if any, would be the effects of a proof that P=NP, or that P≠NP, or indeed that the question is undecidable?
-
Stuart
The latter two wouldn't have any practical consequences, but it would be a big deal in the world of theoretical computer science (and the last also one in logic and mathematics). If somebody proves P=NP, then the practical consequences depend on the way they prove it. If they explicitly exhibit a polynomial algorithm for an NP complete problem, then we would know polynomial algorithms for all NP problems, and if the degrees of the involved polynomials are reasonable, that would be huge news in many fields, but is considered extremely unlikely. It's much more likely that either the polynomial has a ridiculously high degree, or that the proof wouldn't be constructive and just generally concludes P=NP without exhibiting any algorithm altogether. In those two cases, there wouldn't be any immediate practical consequences either. User:AxelBoldt
I agree with your conclusion. However, it isn't really possible for there to be a nonconstructive proof of P=NP with no known algorithm. That's because the construction has already been done. I could easily give you an algorithm for, say, Travelling Salesman, whose correctness is obvious, but whose asymptotic running time is unknown. It's easy to prove that if P=NP, then my algorithm is polytime. If anyone ever publishes a "nonconstructive" proof of P=NP, the construction will already exist. This is all academic, of course. The huge multiplicative constant means none of this would have any practical value. -- LC
That's very interesting. How does the construction work? User:AxelBoldt
Assume the goal is a program that, given a TSP instance, returns the certificate (if "yes") or fails to halt (if "no"). Assume you already have a program to check certificates. Let X=1. Consider the list of all possible programs, sorted first by size, then lexicographically. Run the first X programs for X steps each, with the TSP instance as an input. If any of them halts and returns a certificate, check it. If it's right, halt and return it. If not, continue. If none of them succeed, then increment X, and repeat. Clearly, this algorithm is correct, and its theta running time will be the optimal running time, plus the time to check a certificate. The constant hidden by the theta is exponential in the length of the first program that solves the problem. Totally impractical. I don't remember offhand which books cover this, though I could look it up if needed. It's been a while since I've visited Wikipedia; it's nice to see that it's still going strong. -- LC
The description is clear, I don't think we need a reference, but I think it's nice enough to put it in the main article. User:AxelBoldt
I've added it, in a form that's hopefully accessible to a wider audience. -- LC
Can you also concoct an algorithm which always gives the correct answer in polynomial time? User:AxelBoldt
Yes, if you can tell me the running time of the first algorithm (or give a polynomial upper bound for it). Otherwise, I doubt it's possible now. It's too bad that we can construct this algorithm for NP-complete problems, but not for co-NP-complete problems. -- LC
But then my original statement stands: if we find a non-constructive proof of P=NP, then we still wouldn't have a polynomial algorithm for NP problems, since a polynomial algorithm has to stop after p(n) steps. User:AxelBoldt
I should have said "accept" rather than "solve". Sorry for the confusion. If we could construct a particular algorithm, and prove that it is a polytime algorithm accepting a particular language in NP-complete, then we would have proved P=NP. That would be a constructive proof of P=NP. If we could prove P=NP without knowing any polytime algorithm accepting an NP-complete language, then that would be a nonconstructive proof. The latter is impossible. As soon as someone proves P=NP, we'll immediately know a polytime algorithm that accepts an NP-complete language. It's the algorithm I gave. Note that by the standard definition, an algorithm is a polytime algorithm accepting a language if it returns "YES" in polytime on strings in the language, and never halts on strings outside the language. I'll change the page to say it "accepts the language SUBSET-SUM", rather than "solves the problem SUBSET-SUM". Actually, I think I'll add a second algorithm too. This algorithm (under stronger conditions) yields a stronger result. If there are any algorithms that can be proved to solve (not accept) an NP-complete problem, then this is one of them. I think that's an interesting result too, so I'll write it up later tonight or tomorrow. -- LC
From the article:
an integer between 1 and y.
I think the previous example of simply deciding whether a given number is prime was simpler and more intuitive. The main point here is to get the point across that "solving is harder than checking". Was there a reason for changing it? (Also, not both x and y have to have n digits.) AxelBoldt
The problem of finding the best move in Chess or Go (on an n by n board) is EXPTIME-Complete
Is this right? Go has a strictly higher complexity class than Chess. Isn't Go PSPACE-complete and chess is EXPTIME-complete? - anonymous
I've also removed this:
P and NP and NP-complete only contain decision problems, and you can't approximate a decision problem. Approximations are only possible for problems in classes such as NP-equivalent. -- LC 18:11 Sep 13, 2002 (UTC)
What is non-P? This web site says non-P is different from NP. -Jeff
Non-P consists of all those decision problems that cannot be solved in polynomial time. That is indeed very different from NP. AxelBoldt 00:42 Jan 24, 2003 (UTC)
I'm a bit confused regarding NP-complete...is it purely a matter of probability? If P intersected with NPC yields the empty set (for certain) but it is uncertain whether P=NP, either NPC=empty set or P does not equal NP. Am i misunderstanding this?
I think the source of the confusion is the following pair of sentences: Theoretical computer scientists currently believe that the relationship among the classes P, NP, and NPC is as shown in the picture. The intersection of P and NPC equals the empty set.
The second sentence comes off as an assertion, when I think the intention was that most comp. scientists believe that. I suggest rewording, something like: Theoretical computer scientists currently believe that the relationship among the classes P, NP, and NPC is as shown in the picture, and that P and NPC are disjoint.
This statement has recently been added regarding quantum computers: ...none of the problems they are known to be able to solve are NP-hard.
Is this true?
So wouldn't that mean that quantum computers are known to be able to solve an NP-hard problem?
RSpeer 22:52, May 6, 2005 (UTC)
Before the article stated that EXPTIME-complete problems require exponential time. This is as incorrect as saying that NP-complete problems require nondeterminism to be solved in polynomial time; while this is believed to be true, it need not be (for example, it may be the case that all problems in EXPTIME can actually be solved in O(nlog n) time). The reason we know that EXPTIME-complete has no intersection with P is because P is not equal to EXP, which requires a proof by diagonalization and is not at all obvious. Deco 00:32, 8 Jun 2005 (UTC)
I followed the link to the P-versus-NP page, and though its content is fascinating, I'm worried by the author's wording.
Deco is right that this link needs at least a warning that the proofs are incorrect, because the author never bothers to say it. In fact, he says things like "In February 2005, Raju Renjit Grover proved that P is not equal to NP", and on the same page says that other people proved P=NP. Since, last I checked, true is not false and I am not the Queen of England, this must be an unconventional use of the word "prove".
What was the author's motivation for writing like that? Is he being tongue-in-cheek? Is he trying to trip up readers who aren't observant enough to notice that the "proofs" are contradictory? Is he hoping that every reader comes to the conclusion on their own that all the proofs are bunk?
I know the page can't be entirely serious, and I recognize that reading those papers can be a great test of your own skill at finding holes in arguments. But it still alarms me that Wikipedia is linking to false information. A freshman in CS might click quickly through a few links from Wikipedia, not noticing the entirety of the content on that external page, and then go around saying "But I read on Wikipedia that P=NP". That reflects badly on Wikipedia. Or someone might use this link as Wikipedia-endorsed evidence that mathematical logic is flawed.
I don't think stating next to the link that the proofs are incorrect is enough. Is the author of the page contactable? What I'd like to see is a version of the page that keeps all the links to papers, but says more explicitly that the arguments are unlikely to be sound, and does not falsely state that they are proofs.
RSpeer 05:09, Jun 15, 2005 (UTC)
I added a brief discussion of the oracle result regarding the problem. I tried to keep it simple, but if anyone thinks it can be made easier to understand, I welcome your changes. Deco 07:52, 15 Jun 2005 (UTC)
The inclusion of the "......" is interesting. 172.191.9.162 ( talk) 23:12, 4 May 2009 (UTC) The inclusion of the "......" is interesting. 172.191.9.162 ( talk) 23:12, 4 May 2009 (UTC)
Wait a minute has P Versus NP been 'resolved' as it says below here? —Preceding
unsigned comment added by
74.3.40.183 (
talk) 03:16, 24 July 2009 (UTC)
Please let me add I simply ask this comment remain here for discussion purposes ONLY for the improvement of this article. You see I really want this to be a great article and I see how complex and abstract the article is it is a bit dense and I would like this here just to show people how some non-traditional content for this article may look. There are so many cool ideas in P Versus NP like how it would revolutionize music potentially and I think someone should mention THIS at least in the article! Things like how it would automate poetry because of the potential mathematical origins of prose to Haiku's may apply to such abstract things as even paintings or scientific discoveries or maybe even movies! Imagine, you've heard the expression, "I thought the movie was a bit formulaic. Imagine if there was actually a FORMULA for movies and we could write it in an equation and plug it into an engine and have it spit out screenplays! This is the type of positive forward thinking content that SHOULD BE
> Sum 1. say: > Truth: what becomes true in its construction to be construction it is > a fact that constitutes. We may say it is a (fact) and the proof > constitutes truth. > Sum 1. I am, exist. > Sum sine regno: "I am without a kingdom." > Sic sum ut vides. "Thus I am as you see." > Cogito, ergo sum. "I think, therefore I am." > "Dixit duas res ei rubori fuisse." > He said that two things had abashed him > not equal (≠) (=) equal > Civis Romanus sum: "I am a Roman citizen." > Sum: present active sum, present infinitive esse, perfect active > fuī > "I am as you see." > Sum. (arithmetic) 1. A quantity obtained by addition or aggregation. > I am, exists > The sum of 3 and 4 is 7 > ≠ > I am, exists > 3+4=7 as you see." > I am, exists > 3+4=7 "I am as you see." > I > Sum (arithmetic) An arithmetic computation, especially one posed to a > student as an exercise (not necessarily limited to addition.) I am, > exists ≠ > 2. A quantity of money. > 3. A summary. > 4. A central idea or point. > 5. The utmost degree. > Cum veritate sum > "I am with truth." > Sum 1. Cum veritate sum > I am, exists with truth > = paene (not comparable) ≠ > verto: Latin > (vartayati), “‘he turns’”). > present active vertō, present infinitive vertere, perfect active > vertī, supine versum. > I turn, revolve. > I turn around. > I exchange. > I translate. > prīmō 1. at first > satis: 1. enough, filled, plenty > 1. adequately, sufficiently > Cum Veritate Sum paene primo satis > 1. "I am with truth (not comparable) at first to satisfy" > satis prīmō verto > 1. But I satisfy it sufficiently, because at first I turn, revolve. > prīmō 1. at first > Sum venip verto > 1. "Because in essence I begin in reverse" > P==NP > Q.E.D > Martin Musatov. (CC BY-NC)—Preceding unsigned comment added by 71.129.172.196 ( talk) 00:34, 23 July 2009 (UTC) —Preceding unsigned comment added by 74.3.40.183 ( talk)
The Caption for the pic at the top of the page says:"Diagram of complexity classes provided that P ≠ NP. If P = NP, then all three classes are equal." which is incorrect. If P=NP there will still be problems which are not NP-complete.-- SurrealWarrior 02:19, 19 Jun 2005 (UTC)
Again, it is obviously impossible to reduce a non-empty language to the empty language. Proof: If a language L is non-empty there exists x in L, and in order for a function f to be a reduction from L to the empty language, we must have f(x) in the empty language, which by definition is impossible. QED. So Papadimitriou's statement is not quite true, as there exist non-empty languages in P. Eric119 05:17, 24 August 2006 (UTC)
I realize this is over a year old, but this whole discussion is plain WRONG. NP-Complete is defined as everything within a poly-time bound of the hardest problem in NP. If P=NP then everything in NP is solved in poly-time, which means everything is trivially in a poly-time bound of the hardest problem. The poly-time reduction to 'always return false' and 'always return true' is also pretty easy when the problem can be solved in poly-time. 74.12.143.44 ( talk) 08:10, 26 November 2007 (UTC)
In the section "Polynomial-time algorithms", it writes:
"No one knows whether polynomial-time algorithms exist for NP-complete languages. But if such algorithms do exist, we already know some of them! For example, the following algorithm correctly accepts an NP-complete language, but no one knows how long it takes in general. This is a polynomial-time algorithm if and only if P = NP."
Then it gives a algorithm that accepts the SUBSET-SUM and claims that the algorithm is a polynomial-time algorithm if and only if P=NP.
But I think this conclusion is not very clear since the number of the program P which produces the suitable subset of S may depend on the size of S.
Furthermore, if we change the IF statement in the algorithm with
IF the program outputs a complete math proof AND each step of the proof is legal AND the conclusion is that S does (or does not) have a subset summing to 0 THEN OUTPUT "YES" (or "NO" if that was proved) and HALT
there is another problem: the length of the proof and the number of the program which produces the proof may also depend on the size of S.
ok, I have understood. The algorithm is correct.
If there is a polynomial time program to solve the decision problme SUBSET-SUM, let P_0 be the number of such program. Note that P_0 is independent of the size of input for the SUBSET-SUM problem.
We can use the program numbered P_0 to construct a polynomial time program which produce a subset of S which adds up to 0. Let P_1 be the number of this new program. Note that P_1 is also independent of the size of input.
Assume the input S does has a subset which adds up to 0. Let N_1 be the number of steps need for program numbered P_1 to produce the correct subset of S. Since program numbered P_1 is a polynomial-time program, N_1 is a polynomial of the size of S. Therefore the algorithm will halt when N = max(N_1, P_1), P = P_1, and clearly it runs in polynomial time.
The second algorithm is similar.
---
For the above algorithm, we really do two things: 1) Search for P_0, and 2) Use P_0 on an input string. We say the overall algorithm runs in polynomial time with respect to the length of the input because task 1 is a fixed cost, and we assume P_0 is polynomial. That said, it is infeasible to search for P_0, so the algorithm is useless to us.
It is interesting to note that for short inputs, the algorithm will likely find a machine that just outputs the answer rather than solving the problem. But because such machines are themselves polynomial on the length of the solution, for large problems, we will eventually find the correct algorithm before we encounter any of these degenerate programs.
---
"But because such machines are themselves polynomial on the length of the solution, for large problems, we will eventually find the correct algorithm before we encounter any of these degenerate programs." Let's say S has size 2^forty-bajillion but contains the element '0'. Then won't the program that simply outputs '0' surely turn up before the "correct" algorithm does? —Preceding unsigned comment added by 99.88.110.127 ( talk) 20:30, 7 November 2009 (UTC)
I think the example definitely shouldn't be PRIMES. It is quite confusing there. How hard would it be refer to the SAT problem there? -- Exa 00:05, 23 January 2006 (UTC)
Commonly stated, this is P = NP, which is an assignment statement in most programming languages. The result of the condition is true if NP is true. So:
if (P = NP) print TRUE else print FALSe
prints true if NP is true.
The article describes an algorithm that takes an enumeration of all programs, then runs programs 1..N for N steps each, for N = 1 to infinity. Then it says:
Perhaps I am mistaken, but I think this is complete nonsense. The "algorithm" is not an algorithm at all, since it is not guaranteed to halt, and in fact won't halt if there is no solution for the problem it is trying to solve.
I suggest that the entire section be deleted, and unless there is a serious objection in a few days, that is what I am going to do. -- Dominus 20:22, 5 April 2006 (UTC)
on the margins of 'concrete mathematics' by knuth, there is a 'proof' that P=NP; it says simply N=1 => P=NP! :)-- Aryah 18:02, 16 April 2006 (UTC)
IF the program outputs a complete math proof AND each step of the proof is legal AND the conclusion is that S does (or does not) have a subset summing to 0 THEN OUTPUT "YES" (or "NO" if that was proved) and HALT
There is no Turing Mashine, that can understand a "complete math proof".
Proof: If that there is the TM, we can solve Halting problem. We've got a TM, and we want to know if it stops. Let's search for complete math proofs and check them. Any TM either stops or not, so eventually we'll find a proof that TM stops or proof that TM doesn't stop. Hence we can solve the halting problem. But it is impossible.
I propose to delete this algorithm. —The preceding unsigned comment was added by 194.85.83.201 ( talk • contribs) 17:07, 8 May 2006 (UTC)
"Every 'function which would naturally be regarded as computable' can be computed by a Turing machine."( Church–Turing thesis). So if some program can check proofs, then there is a TM can doing it. It's very difficult to understand / can exist TM, for which there is no such proofs, but if they do exist, why every word for every language has to have a proof, that it is not in the language(or proof, that it is in the language)? I mean why the second algoritm hopes that it will find a proof?
I've deleted the algorithm. 194.85.82.254 05:04, 20 May 2006 (UTC)
The algorithm that decides subset-sum seems to rely on an unstated assumption: if P=NP, then there exists an algorithm that decides subset-sum and outputs a complete mathematical proof in polynomial time. This wasn't at all obvious to me, and it was fairly non-trivial to prove. Is it worth including a proof, or at least a pointer to one? -- Nate Biggs 21:07, 6 June 2006 (UTC)
This article should have a more easily-understandable pratical example for the less tech/math-savvy ones, such as this one.
I can't write one myself, if that's what you're thinking. -- Procrastinator 17:11, 31 July 2006 (UTC)
Isn't this the same as saying "given a randomly generated maze, is there a general algorithm for finding a route between entrance exit which does not involve taking every path" ?
Suppose I generate a random maze which has exactly one route between entrance and exit. If I then draw a line on it, you can easily verify if the line connects the entrance with the exit.
Now imagine I come up with an algorithm that finds that path without taking every possible route. So far so good. But what if I now move the exit so it lies on one of the unexplored routes. Now I must continue running the algorithm until the new route is found. At this point I again move the exit to another unexplored route. I continue doing this until all of the maze has been covered.
Thus there can be no general algorithm for finding the path between entrance and exit. QED.
Is this correct, or have I made a mistake somewhere ?
-- [email protected] 29 Aug 2006.
Thankyou. Your answers are helping me to understand the problem better. Reading it all through again it makes more sense. However there seems to be a contradiction on the page, it says:
'If P = NP, then this is a polynomial-time algorithm accepting an NP-Complete language. "Accepting" means it gives "YES" answers in polynomial time, but is allowed to run forever when the answer is "NO".'
I don't understand this. If there is an algorithm which finds a solution in polynomial-time, then surely it should just terminate after the maximum number of steps, and say that the answer is "NO". Why would it need to run forever if the answer is "NO" ? If it can't say "NO" in a finite time, then that means there could still be a solution left to find.
-- [email protected] 02 Sep 2006.
More importantly, I guess what I meant by the maze analogy, and moving the exits is, what about Godel's theorem ? What I mean by this is, consider the subset-sum problem. I conjecture that for any proposed solving algorithm you give me, I can construct an input set which you can't solve in polynomial time. For example, suppose the algorithm starts with the lowest numbers first. I can simply construct a set with a solution 1,000,000 and -1,000,000, and fill all the rest with small numbers. If the algorithm starts with biggest numbers first, I can construct a set with 1 and -1 and fill the rest with larger numbers. If the algorithm starts by considering pairs, then triplets, I construct a set where all the numbers must be summed to reach 0.
All I need do is look at the algorithm, and figure out a way to "break" that algorithm, i.e. construct a set where the solution will be the last possible combination tested.
-- [email protected] 03 Sep 2006.
I noticed THIS on arxiv.org: [1] and [2] 70.49.174.170 01:23, 5 September 2006 (UTC)
Returning to my "maze theory" above - somebody was asking for an example for non-mathematicians. Somebody suggested a breadth-first algorithm for finding the exit. A breadth-first search is an example of an NP-complete algorithm. My point, before I distracted myself (!), was this: Example for non-mathematicians: you are standing at the entrance to a maze. You know for a fact there is exactly one other exit from the maze. The challenge is this: can you walk to that other exit without trying each possible path through the maze, and without just stumbling on it ? Most people would say no, but can you prove it one way or the other ?
-- [email protected] 10 Sep 2006.
Just noticed this on arxiv.org [4], might be worth mentionning on the page after some review... -- anonymous —Preceding unsigned comment added by 129.88.57.2 ( talk) 12:49, 13 October 2009 (UTC)
Please could everyone look at the reverts in this article, I have been trying to revert some blatant opinion expressing but I'm having trouble with user:82.250.60.102, please check and make your opinion on the matter as I have little knowledge of the subject Ryanpostlethwaite 17:47, 23 November 2006 (UTC)
If you have little knowledge of the subject, please move on... 82.250.60.102
Please check over the history for a few edits ago. We have come to an agreement now and in my opinion his new propsal of the title (see edits) is no longer biased. But I am still erring on caution so please check and ammend appropriatly Ryanpostlethwaite 18:00, 23 November 2006 (UTC)
I'm sorry but this line IS an opinion which I've just removed as other people have different views on P=NP; 'However, holding such belief for such reasons is tantamount to believing that Higgs Boson does not exist' Ryanpostlethwaite 22:06, 23 November 2006 (UTC)
If you are not an expert then do not even think about anything as being soapboxing or not being soapboxing. Ryan could not be aware of three revert rule, he just arrived in town. The only big issue here is people like Ryan or Jammycakes expressing their opinion through reverts, supposedly in order to prevent violation of non-opinion policy. Ryan is the violator. user:82.250.60.102
This is your opinion about which you are confident. By the way, I know quite a bit about P=NP. 82.250.60.102
Neutrality is by no means a way of deciding what is the right thing for this Wikipedian entry. If you were talking about knowledgeable or competent people, then I guess one could listen to your "all means". 82.248.114.187
The original paragraph did say that "Most computer scientists believe that P≠NP". This is as much an opinion as saying "Some computer scientists may err in professing that P≠NP". What source do you have to backup this majority statement? How do you know "most" computer scientists believe that? Would any of us see this as a "belief"? ... Well, that's maybe the only point where this statement comes close to truth... P!=NP became a belief for some colleagues. You ask for "arguments". Did anyone bring up evidence that "most computer scientists" think so? If you knew just a bit about the subject, you would think twice before deleting the analogy with the existence of Higgs boson. 82.248.114.187
The only reasonable way by which you could change your paragraph (if you still believe that Wikipedia should defend this "original" opinion) would be to say: "Computer scientists of the Bill Gasarch type believe that P≠NP". He (and SIGACT) is your only source. Wake up. 82.248.114.187
The point that I am trying to make is that although you may think it is absurbed that some people believe that P≠NP, there are some people who think that this is correct. The analogy with the existence of Higgs boson suggests that the people that believe P≠NP are stupid and completely incorrect, this is an opionion that you are expressing as I am sure the people that believe P≠NP would have a far different opinion. The paragraph in question is showing why people believe that P≠NP and it is not trying to show that this is correct. Therefore the changes that you made are unhelpful and need reverting to keep the articles neutrality Ryanpostlethwaite 21:41, 25 November 2006 (UTC)
As already said... This poll just reflects what Bill Gasarch made it to reflect. Ryan's change for the title seems sound. As for relating Higgs Boson to this pure computer science result, Deco is clearly unaware of what's silly and what's not. "Some may err" is as strong as saying in the title "Why computer scientists think..." (which implies an absolute opinion of all computer scientists). I will propose a new version beyond Deco's dictatorship and my own stubbornness. 82.253.212.117
Go for "many", though the many may be wrong (but that's obviously not the problem of Wikipedia). 82.253.212.117
I think now that we have finally gained consesus! If all are agreed we will leave the heading 'most computer scientists believe that P≠NP' and the subsequent paragraph intact and revert (as already done so) all changes made to it. Many thanks for everyones contributions Ryanpostlethwaite 23:37, 26 November 2006 (UTC)
Hi all, not an expert but find the subject very interesting. The debate over this question has a lot of interesting elements at its core. Basically, I think this is one of the most philosophically unique debates in science. First, its resolution has important consequences for several fields. I also think the nature of the dispute is interesting, in that (at least, as the dispute is represented in this article,) the people who say P!=NP are making an empirical argument based on current failure despite lots of effort, while the proponents of P=NP are holding out for a theoretical proof. Thanks for all of your energetic and thoughtful development of the article.
Due to the nature of the dispute, I find myself jumping a bit into the future, and I have a couple of questions for people who really think about this stuff. Any discussion would be great, and if you could post your reply on my talk page so that I would see it I would be very appreciative. Again, these are just some questions, I profess very little previous exposure to the subject.
Questions: Given the differing nature that seems to be emerging among the two "camps" on this question, and given the way that the question is formulated, how would a theoretical proof that P<NP even look or work? It seems that the "proof" that P<NP would simply be a sufficiently long list of examples of things like subset-sum, at least if current approaches to the question continue. I know this question seems silly, in that we don't know what the proof will look like until we find it, but I'm asking more generally how a question like this could even be resolved. I don't understand fully the interactions between the question and challenging examples, such as subset-sum.
IF P=NP, does that mean necessarily that every question like subset-sum must have an expedient answer and we just haven't found it yet? Therefore, does it mean that in EVERY persisting example where seemingly P<NP, all parties have overlooked a stroke-of-brilliance way to answer the example question that is as quick as it is to verify it? This seems exceedingly unlikely, doesn't it? Another way to ask this question is to say: does P=NP have to hold for everything to be considered true? Thus, if P=NP, does that mean that it is IMPOSSIBLE to dream up a question which is long to answer but quick to verify?
It seems to me that the philosophy of P=NP, the underlying claim, is that there is a fundamental identity of both answering a question and verifying the answer, that they must by definition have such a close brotherhood that, when the issue is fully explored and properly understood, their computational requirements converge. Something like subset-sum is currently easier to verify than to prove. Let's say, for sake of argument, that we figured out THE fastest way to verify a subset-sum answer, and it's x amount of time. Does P=NP, if true, imply that we have also found the amount of time that the perfect method would require to answer a subset-sum question, even if we have no idea what that method is?
Thanks for your help! Gcolive 20:58, 13 January 2007 (UTC)
Hello all, I'm trying to understand the "Polynomial-time algorithms" section of the article. I'm not convinced that if P=NP, that in fact an algorithm for an NP problem must be polytime. I was under the impression that a proof that P=NP would imply that there existed an equivalent polytime algorithm, not that a particular algorithm must be polytime. Can someone explain this to me? Arkleseizure 21:48, 27 January 2007 (UTC)
Hello, I just read the entire article and I want to say good job to the people who wrote it. This is a very complex subject but you people have found a way to explain it in a simple, clear, easy to understand way. Good Job. 70.49.201.164 03:12, 4 February 2007 (UTC)
Why is (Note that the abbreviation NP stands for "Non-deterministic Polynomial" and not for "Non-Polynomial".) at the end of the Formal Definition section? It should be readily available in the introduction to this entry.
The article vividly explains the evidence, theoretical arguments, potential consequences, and history surrounding the statements P≠NP and P=NP. But Gasarch's poll found that some researches believe that the statements are independent of the accepted axioms. I feel that this article should give that viewpoint equal exposition as it gives the other two. Otherwise, terrific article. Thanks! -- 131.193.178.113 20:53, 13 February 2007 (UTC)
Independent of which accepted set of axioms? Peano arithmetic? ZFC? Something in between, or something stronger? It makes a difference -- "independent" is not a truth value, contrary to some people's vague notion of the idea. Those who responded in that way to the poll may have had viewpoints sufficiently disparate among themselves that no single coherent exposition will really be possible, and in any case we don't have a reference for just what it was that those who responded thus were thinking. (Or I assume we have no such reference -- if anyone does have it, of course please share.) -- Trovatore 22:07, 13 February 2007 (UTC)
Tim Cooper (
Tcotco (
talk)) agrees with Deco that this issue deserves more prominence on the main page. I added a pragraph, but this was partly reverted by David Eppstein.
Tim Cooper's note to David Eppstein:
"I noticed that you rearranged the text I inserted about the possibility that P=NP is undecidable.
I believe that this position deserves more prominence than it currently has, at the very least, a paragraph and section title on the P=NP Wikipedia page. It is a respectable 3rd option, notwithstanding the fact that - according to that study - only 8% of computer scientists hold this belief. I know many computer scientists who work closely with algorithms and yet don’t know much (or anything at all) about axiomatic systems and undecidability, and I just don’t think many computer scientists have really given it much thought. So I don’t really believe that 92% of computer scientists believe that we are mistaken. In fact I would like to expand the section to include another 1 or 2 paragraphs giving the reasons why our intuition tells us that the question is formally undecidable. By encouraging other computer scientists to take the time to consider the issue, I believe the 8% would quickly grow. Do you think we could enlarge this section?"
About the
current edit by David Eppstein, which added the following paragraph:
I think the facts stated are right, but the interpretation may not be. I'm not a logician, but here's my interpretation: The authors show that if P=NP is shown to be independent of PA_1 (an augmented version of PA) then NP has almost polynomial time algorithms. They say that this can be shown for ZFC too, so I assume they mean that if P=NP is shown to be independent of ZFC_1 (which is probably a similar "augmented" version of ZFC) then NP has almost polynomial time algorithms. However, this doesn't say much about what would happen if P=NP is proven to be independent of PA or ZFC directly. I think they do state in the paper that if someone shows P=NP is independent of PA using only currently known techniques, then it will imply NP having almost polytime algorithms. But, it is entirely conceivable that someone comes up with a brilliant new method of showing independence, which shows P=NP is independent of PA, but does not show that its independent of PA_1, and thus the results of this paper don't apply. -- Robin ( talk) 23:31, 3 September 2009 (UTC)
I published a proof that there is no proof that any decidable decision function in not in O(n). It can even be extended to O(1).
Any comments? Uri Even-Chen 19:57, 21 April 2007 (UTC)
I will try to express this in simple words:
1. every specific question with yes or no answer (1 or 0) can be computed in O(1) (there is no input, the input is included in the question itself). The question must be defined in a deterministic way.
2. for every n, in order to prove that the set of possible inputs of n bits (2^n possible inputs) cannot be calculated in less than c*n steps (for any constant) by any algorithm, at least one specific example of such an input needs to exist.
3. we come up with a sequence of inputs of size n (from one to infinity) for which it is known that it cannot be calculated in less than c*n steps (for any constant) by any algorithm.
4. for every n, we create a new algorithm that will check the input, if it is equal to this specific hard input then we can display the known answer, otherwise we can use another algorithm - whether efficient or not.
5. the result is a contradiction.
Which means, a deterministic proof doesn't exist.
But, a statistical or probabilistic approach might show that the chances to find such an algorithm who computes the function in O(n) are very low. It doesn't mean such an algorithm doesn't exist - maybe it does. We can't prove it doesn't exist, the only thing we can say is that we don't know it.
It's easier to understand when the size of input is specific. For example, if the size of the input is up to 50,000,000 bits - we need to prove that for every algorithm of size up to 50,000,000 bits, calculating the function in O(50,000,000) steps is not feasible. Can we check 2^50,000,000 algorithms? Probably not. But there are problems for which we can estimate that the chances to find such an algorithm are low.
An example of a specific problem is factoring numbers. If we receive a number of n bits, and we need to calculate its prime factors which can be represented together in m bits, then each bit of m is a decision problem, and the total calculation will not take more than O(m*n). If each bit is calculated in parallel, or if there is even a more efficient algorithm, O(n) can probably reached too. This can be easily verified because if we already know the prime factors for any specific input, calculating the function is very easy. It is a hard problem since a solution is not known to us, but we cannot prove that such a solution doesn't exist.
Uri Even-Chen 22:24, 25 April 2007 (UTC)
Please excuse my interjecting but I think I have something relevant to this topic which may result in bettering this article (IMHO):
I published a proof that there is no proof that any decidable decision ...... the concepts (although I would refrain from referring to randomness here). ...... Per M.B.A. Matthew Cherian (backs claim by Musatov): First of all you notion ...
The notion contained by the time hierarchy is ...
... = t i m e
I have taken a lot of the technical details out of the introductory paragraph to make it more accessible to people who aren't theoretical computer scientists. All the intro needs to do is introduce the flavour; the technical details are presented quite adequately in the body of the article. -- Robert Merkel 12:52, 5 May 2007 (UTC)
I would like to propose adding another reason to the list of reasons in this section of the article. I would like to add something like this:
Would it be OK to add that? Is it too long? I'm not sure if I should have a citation in there. I don't have a source for this; it just seems to be somewhat self-evident to me. Also, I'm not an expert in complexity theory or physics, so perhaps someone who knows more can edit what I wrote to make it more accurate. Navigatr85 23:44, 3 July 2007 (UTC)
This point argues against itself: any improvement in processor speeds gives more benefit to polynomial time algorithms than it does to exponential time algorithms. If you have a computer that goes 10^1000 times as fast, then you can solve an instance of a O(n^2) problem that's 10^500 times bigger, but an instance of a O(10^n) problem that's only 1000 times bigger. Similarly for reductions in speed: polynomial algorithms suffer less than exponential ones.
In any case, the point is already made in the article; there's no point in saying in ten different ways that complexity classes are all about asymptotic behaviour but in practice we have only finite resources. Gdr 15:14, 6 July 2007 (UTC)
That's a good point, Gdr.....But it depends on how fast memory sizes grow in comparison to CPU speeds. If you build a CPU that runs at 1010100 Hz, but if at the same time, the largest hard drive in the world can only store 1050 bits, then both exponential algorithms and polynomial algorithms would be fast for the largest possible input size. (I'm assuming fast hard drive read/write speeds.) I don't think the point is already made. This section doesn't seem to contain anything yet about exactly how large our real-life finite resources are. --Navigatr85 17:04, 10 August 2007 (UTC)
Since no one has raised any further objections, I'm going to add this to the article. However, I have a feeling that people WILL raise further objections immediately after I add this to the article. :) Feel free to post your further thoughts; I think it's a good discussion. --Navigatr85 19:20, 20 November 2007 (UTC) —Preceding unsigned comment added by Navigatr85 ( talk • contribs)
Considering that we already have articles on P and NP, this article appears at first glance to be redundant. Only after reading it is it clear that this article discusses the P = NP problem. I'd suggest we rename it to suggest this; maybe P=NP problem or something like that. What do you think? Dcoetzee 22:24, 24 July 2007 (UTC)
Writing P=NP with no spaces around "=" is generally regarded as incorrect according to Wikipedia conventions; it should by P = NP instead. I'd move the article to P = NP problem (now a redirect page) instantly if fixing all the links were not going to take a while. Michael Hardy 03:31, 15 September 2007 (UTC)
OK, I've moved it and fixed the resulting double redirects. The next problem is fixing all the links. Michael Hardy 16:17, 21 September 2007 (UTC)
What's all this stuff about P is impratical, it is better a low exponential, we have few resources and so on? I think that when you speak about P is impratical you make an hypothesys on the length of input, but this hypothesys is not justified!!!!! Why thinking that input is short? What if our x^(10^100) takes as input whole atoms in universe? Is it worse than e^(-10000*x)? I do not think so, not only, but all this stuff denotes an ignorance about the meaning of big O notation. If I say that e^(-10000*x) is not in O(x^(10^100)) I mean there is a constant after that ≈e^(-10000*x) is greater than x^(10^100), so on inputs that bigger we still prefer exponential? So not only this section is WRONG, but it also creates CONFUSION. I agree with Dcoetzee.
-- Nicolaennio 12:31, 21 September 2007 (UTC)
Another point should worth mentioning, by considering practicity as defined in my previous answer, P=NP problem can be seen as a practicity statement, that is, is it possible that every problem (also difficult) turn out to be practical? However in the explaination of the voice it seems that EVEN IF we demonstrate P = NP we did not gain anything because P can be also a 'bad' class (As you can see it does not intersect so much with PRACTICAL). I think this is misleading in the comprehension of the statement, and possibly does not allow the reader to make an own idea on its possible answer -- Nicolaennio 08:03, 26 September 2007 (UTC)
After all I think that to understand complexity classes it should be important to state, somewhere, that we do not consider hardware stuff, because with enough hardware we can break down any constant or lower exponent, and that any statement is input-lenght - free, that is we prefer a polynomial w.r.t. an exponential because after a certain length it is best. I do not think P=NP is the right place because it is an advanced statement and this is discussion about practicity is at an entry level of complexity theory, so it can only be deceptive for the reader to guess if P is 'good'. So I think that there should be a brief explanation of tape compression and linear speed up theorem in computational complexity theory that motivates O notation (actual motivation is incomplete) and effectively a discussion in P about the fact Dcoetzee and Blokhead say, that is it is usually considered a 'good' class not because it contains fast algorithms, but because it is better than other ones (P is strictly contained in EXP). -- Nicolaennio 09:37, 4 October 2007 (UTC)
Thanks for producing such a great page. As a complete novice in this area I found the level fairly accessible. I would like some discussion may be of concrete examples of common mistakes. Here is an idea you could maybe shoot down:
I am also interested in the concept of information loss on either side of equations xy = z If given z, xy is much harder to compute than the other way around one expects. The equation is not 'information symetrical', therefore one has to undertake a finding process to uncover that extra information, each side cannot be as easy as each other to compute. Let us say it is almost polynomial then go to wxy = z an increase in inbalance and computional time difference and so forth, eventually we must reach p does not equal NP??? 81.158.153.174 13:26, 20 October 2007 (UTC)
Sorry about that. I am constantly amazed by my ability to be stupid whilst feeling insightful. I really meant to say if we add more primes of an incrementally growing size to one side of the equation it looks as though we can create a growing complexity on one side in comparison to the other so at some stage we must reach P does not equal NP. As you rightly point out there is a problem with formalizing this difficulty which crashes the proof unless it could be successfully argued that a number does not reveal its factors without testing and that testing is inherently slow as it can only eliminate fractions of the total possible number of divisors. please contact me at piersnewberry at hotmail.com if you want to discuss this further. I eventually followed the QEDen link at the bottom of the page which provide further help for people at my level. Thanks again. —Preceding unsigned comment added by 81.158.153.174 ( talk) 19:02, 20 October 2007 (UTC)
Nicolaennio, I think the reason you're confused is because there's no example with actual numbers. Consider this: typical input lengths that users are interested in are between 100 and 100,000, approximately. Let's pick an input length of 100, i.e., n=100. Now, let's say we have a polynomial algorithm whose running time is n2. This is a typical polynomial algorithm. Also, let's say we have an exponential algorithm whose running time is 2n. This is a typical exponential algorithm. The number of steps that the first algorithm will require, for n=100, is 1002=10000. The number of steps that the second algorithm will require is 2100. Now, a typical CPU will be able to do 109 operations per second. To get the number of seconds that the algorithm will take, we take the number of steps and divide it by the number of steps per second. So the first algorithm will finish in (10000 ÷ 109) = .00001 seconds. A running time of .00001 seconds is reasonable, and that's why we call that a practical algorithm. The second algorithm will take (2100 ÷ 109) ≈ 1.3×1021 seconds. Now we can divide by the number of seconds in a year. The second algorithm will take about (1.3×1021 ÷ 31556926) ≈ 4.1×1013 years. Since it'll take 41 trillion years to complete, that's why we call the second algorithm impractical. --Navigatr85 21:20, 2 December 2007 (UTC)
The formal definitions in this Article are not formal at all. Take a look at the Official Problem Description of the Clay Mathematics Institute to see how P and NP are defined. ( The Clay Mathematics Institute Official Problem Description (pdf))
-- CBKAtTopsails 19:06, 24 October 2007 (UTC)
First, I believe that any formal definition should be short and brief and should not be as wordy as the one given in this Article. But the major problem really is a lot of things used in this Definition remain undefined and we cannot build a formal definition based on somethings which are not formally defined.
To name just a few:
1. The word algorithm is mentioned several times in the Definition but there is no formal definition for algorithm. At one point, it says "an algorithm A(w,C) which takes two arguments". At another point, it says "A produces a YES/NO answer". Now, you may argue that we can look at algorithm as a Turing machine in this situation. However, if you go back to the basic definition of a Turing machine, you will recall that both inputs and outputs to a Turing machine are strings. Therefore, you will need to have some explanation as to how this two arguments can be converted into strings that can then be input to the Turing machine. You also need to explain how the output string from this Turing machine can then be converted to a YES/NO answer.
2. The Definition contains the statement "w is a YES instance of the decision problem". This statement needs to be formally defined in terms of languages.
3. Finally, there is an important property about the Certificate that is missing from this Definition. That is, the size of the Certificate is polynomially bounded by the size of w.
-- CBKAtTopsails 16:54, 25 October 2007 (UTC)
Note: "There exists" must be changed back to "There exist" because 2 things must exist before conditions (i) and (ii). That is, the binary relation R and the positive integer k.
-- CBKAtTopsails 15:46, 9 November 2007 (UTC)
Although someone pointed out that the total number of divisions to go through to check if a given x is composite is [x1/2]-1 instead of x-2 where [x1/2] denotes the greatest integer less that or equal to x1/2, in the theory of computational complexity, two methods are considered the same if they both run in exponential time. Even if you can cut down the number of divisions to x1/2, the time is still exponential.
To see why, let's assume that x contains k digits.
We can then write
x=ak-110k-1+ak-210k-2+......a110+a0 ( For example, 323=(3)(102)+(2)(10)+3 )
Therefore, x1/2={ak-110k-1+ak-210k-2+......a110+a0}1/2 which clearly is exponential in k, the size of the input.
Although each division is polynomial-time, the total number of divisions is exponential. Therefore, the total time is exponential.
The question of P vs NP basically asks: "Is there a way to reduce the computation time from exponential to polynomial for all the NP problems?". Just reducing it from one exponential form to another is not good enough.
-- CBKAtTopsails 19:45, 9 November 2007 (UTC)
One of the quotes has a "[sic]" the way it's written:
"The resolution of Fermat's Last Theorem also shows that very simply [sic] questions may be settled only by very deep theories."
I don't know the quote at all, but it could have been:
"The resolution of Fermat's Last Theorem also shows that very simply—questions may be settled only by very deep theories."
Depending on if the "that" refers to the "space of algorithms" or "questions." 71.177.240.147 18:39, 10 November 2007 (UTC)
First of everything, I beleive that formal definitions are needed because people want to use them to establish theorems using rigorous mathematical arguments. Formal definitions therefore must be precise and cover all applicable situations.
Since this article is rated to be within the scope of WikiProject Mathematics and since you cannot talk about mathematics without talking about formal definitions, I see no reason why formal definitions have to be left out from this article.
I have checked out the articles on P (complexity), NP (complexity) and Karp reduction. Here are what I found:
(i) The articles on P (complexity) and Karp reduction do not themselves contain formal definitions for P and NP-complete. you have to navigate through many other articles spending a lot of time to sort out what information is needed and what information is not needed. People who do not want to spend a whole week or even a whole month to understand all these other articles in order to get to their original very simple objective (i.e. to find out how P and NP-complete are defined) would simply give up.
(ii) The article on NP (complexity) has a different way of defining NP. This different definition, although mathematically equivalent, originated from the concept of nondeterministic machines and is no longer the popular definition. Most importantly, it is not in tune with the concepts and and ideas talked about in the article of "P = NP Problem". For example, the concepts of checking relations, verifiers and certificates.
I believe that there are many people out there who became aware of the "P vs NP Problem" because of the $million prize offered by the Clay Mathematics Institute and I believe that what Clay Mathematics Institute is looking for is a settlement of this problem based on some kind of rigorous mathematical argument.
In summary, including a formal definition in this article will serve two important objetcives:
(a) Provide the convenience of one-stop shopping without having to navigate to many other articles.
(b) Provide additional flavors in the article for different people who come to search Wikipedia on the subject of "P vs NP" with different perspectives.
-- CBKAtTopsails ( talk) 16:47, 21 November 2007 (UTC)
So, are you suggesting all formal definitions in this article should be moved to the articles of P (complexity), NP (complexity) and Karp reduction? If so, why was there a section called formal definition from the beginning? Why didn't people see it a problem until someone puts up a real formal definition in it? Again, I want to stress the point that formal definitions have to be very rigorous and there is no such a thing as less detailed or more detailed formal definition. Section 2.1 of the article NP (complexity) talks about verified-based definition using the subset-sum problem as an example. This section is far from being called formal definition because formal definition cannot be built based on one specific example.
-- CBKAtTopsails ( talk) 00:19, 25 November 2007 (UTC)
The NTIME article is strictly concerned with nondeterministic TM. The so-called verified-based definition (i.e. the one included in this article) is defined in terms of deterministic TM. Therefore, I don't think it should belong to that article. The definition that you refer to in the "introduction" of the article NP (complexity) namely, , as I pointed out earlier, is not a popular definition. In fact, in many text books (including Sipser's), it is used as a theorem rather than a definition. Also, many theorems in time-complexity theory were proved using the verified-based definition. I don't know what objective you have in mind for this article. I do feel that there is one important subject that has not been discussed adequately in this article. That is, what kind of approaches people might take to tackle the P vs NP problem. Don't you think you need to lay down the fundamental definitions of P and NP (preferably the verified-based one) to get into the subject?
-- CBKAtTopsails ( talk) 05:38, 26 November 2007 (UTC)
There have been some talks about the practicality of the polynomial time definition on this page. The section "Is P really practical?" in this article states the following:
"All of the above discussion has assumed that P means "easy" and "not in P" means "hard". While this is a common and reasonably accurate assumption in complexity theory, it is not always true in practice, for several reasons:
According to the opinion of at least one expert in this field, all the known polynomial-time algorithms for solving any practical problems in the real world run in time O(n5) or less with reasonable constants. The following is a direct quote from Section 1.5.1 of Chapter 1 in the the textbook, "Computational Complexity: A Modern Approach" written by Sanjeev Arora and Boaz Barak of Princeton University (See
http://www.cs.princeton.edu/theory/complexity/modelchap.pdf)
"1.5.1 On the philosophical importance of P
The class P is felt to capture the notion of decision problems with “feasible” decision procedures. Of course, one may argue whether DTIME(n100) really represents “feasible” computation in the real world. However, in practice, whenever we show that a problem is in P, we usually find an n3 or n5 time algorithm (with reasonable constants), and not an n100 algorithm. (It has also happened a few times that the first polynomial-time algorithm for a problem had high complexity, say n20, but soon somebody simplified it to say an n5 algorithm.)"
In all fairness, I think the burden of proof lies on those who made the criticism to come up with a specific example to support their argument. In other words, you need to show that there is a practical problem which requires an n100 time algorithm to solve it and otherwise cannot be solved in any other more efficient way.
If you don't have a specific example, all you talk about is still speculation. It is not about practicality.
-- CBKAtTopsails 20:37, 4 December 2007 (UTC)
Can you provide more details on this? Keep in mind that even if you can find some other problems that can be solved easily but are not in P, you have not proved any thing wrong about P. The reason is that the intention of P is to say that everthing in P is easy-to-solve but it never guarantees that every easy-to-solve problem in the world must be in P.
If you can find any fixed-parameter tractable algorithms and approximation algorthms which can be used in practice, it's nice but it doesn't prove anything wrong about P.
The fact of the matter is there is no reason why we cannot have more than one class of problems which we can consider easy.
To sum up, you must find a problem that is in P but not easy to solve in order to ridicule P.
-- CBKAtTopsails ( talk) 04:53, 8 December 2007 (UTC)
"a Turing machine" and "a verifier" must be changed back to "the Turing machine" and "the verifier". The difference is the following:
When you use "a", you are not sure about the existence of such a Turing machine. Condition (ii) actually guarantees such existence.
-- CBKAtTopsails ( talk) 20:48, 7 December 2007 (UTC)
I think your argument is a little out of context here.
We need to get everything back on the table in order to straighten this mess.
First, you are given a binary relation R from which you construct LR. This LR is not an arbitrary language but one that specifically ties to certain given information.
Quote: "(1) Why is this an error, or even a logical error? If condition (ii) guarantees the existence, it is superfluous to also indicate the necessary existence grammatically, since it is already implied logically. (2) The definite article "the" implies, in normal English, not only the existence of a Turing machine with these properties, but also that there there is one Turing machine having these properties. This is false; there are many, some of which will not run in polynomial time even if another one does. Thus, the use here of the definite article "the" actually makes the sentence erroneous, unlike the article "a".".
Response: The definition of decidability guarantees the existence of at least one Turing machine that decides LR. Yes, sometimes, you can have more than one TM to decide LR for any given LR but sometimes you don't for another specific given LR. Since formal definitions have to deal with all situations, we cannot talk about those TM's that sometimes exist and sometimes don't. "The" Turing machine refers to the only one that is guaranteed to exist in all situations.
Quote: "In mathematics, a divisor of an integer n, also called a factor of n, is an integer which evenly divides n without leaving a remainder.
Response: This example simply is not a good analogy to our issue. The integer n is too arbitrary and too general unlike LR which is specifically tied to certain given information.
How does it sound to you if I say, "In mathematics, the divisor, 1 of the integer 1, also called the factor of 1, is the integer which evenly divides 1 without leaving a remainder."?
And, How does it sound to you if I say, "In mathematics, a divisor, 1 of an integer 1, also called a factor of 1, is an integer which evenly divides 1 without leaving a remainder."?
-- CBKAtTopsails ( talk) 19:23, 11 December 2007 (UTC)
Quote: ":I am sorry, but I cannot follow your argument. Given a Turing machine for deciding language LR that runs in time O(T(n)), I can construct a different Turing machine deciding the same language LR that runs in time O(T(n)2) – which preserves polynomial-time-hood – or even a TM that takes time O(2T(n)) – no longer polynomial. So if there is one verifier, there are in fact always several (even infinitely many) verifiers. Which of these is then "the" verifier?"
Response: In this case, you would have to take the most efficient one and throw the others into the garbage can. Theoretically, if you give me a Turing machine, M, which is a decider, I can always construct another Turing machine which moves its head back and forth 100 million times before it takes whatever steps M takes to get to the same destination and therefore this Turing machine I construct is still a decider although it takes 100 million more steps to do what M can do. The point is : Does this machine make any sense to you or does it serve any practical purpose in terms of developing an academic theory? Every academic theory is developed with an objective in mind and computational complexity theory is no exception. As I pointed out before, which may sound a little weird to you, the language = is the considered the same as the language = in the theory of computational complexity.
Quote: "As to the definition of divisor with "1" substituted for "n", to call 1 "the factor of 1" is definitely weird, even though it is the only factor (in positive integers). On the other hand, stating that 1 is "a factor of 1" is just fine. So I think this example actually works against your position."
Response: I don't see it that way. The reason I raised this example is to show that your example is out of context with the issue in which LR is something specific whereas n is very general. If you replace n with something more specific (which doesn't have to be '1'. You can make it something else), "the" sounds much better than "a".
-- CBKAtTopsails ( talk) 15:39, 12 December 2007 (UTC)
Quote: "Generally, the word "the" is thought to imply uniqueness as well as existence, which certainly does not hold in this case; nor does "a" imply non-existence (although you can make vacuously true statements such as "a composite prime is equal to 4"). In any case I favour the original wording."
Response: "The" integers which are divisible by 2 are also called "the" even integers. "The" doesn't have to mean uniqueness. It means something specific. I never said "a" implies "non-existence". I said "not sure about existence".
-- CBKAtTopsails ( talk) 15:52, 12 December 2007 (UTC)
Quote: "Your definition in the article does not mention anywhere that you "have to take the most efficient one and throw the others into the garbage can". Should the reader read this between the lines then?"
Response: First of all, this is not my definition. I am just reflecting what is being used in this field. Make no mistakes about this. I have never said things are now perfect in computational complexity theory. Computational complexity theory and even the entire theoretical computer science is a relatively new theory. Despite of all the significant discoveries in this field, some day, some one will have to write up expositions to unify the definitions and simpify or even correct eroneous arguments in proving theorems. This situation is not unique for computational complexity theory. It has happened before in the other branches of mathematics. I personally have had a lot of frustration experience in reading texts in theoretical computer science because I believe that most authors do not have the attitute to treat the subject using a very rigorous mathematical approach. Sometimes, you can find inconsistencies from definition to definition. Sometimes, you can find ambiguous definitions and sometimes, you can even find incomplete or false arguments in proving theorems. Nevertheless, let's get back to the subject. I think there can be a number of ways to fix a problem. In this case, I think it's ridiculous to use "a" to replace "the" simply for the purpose of including those useless TM's you constructed. One approach is not to use the concept of Verifier at all. This Verifier thing is just a matter of name calling and it is not needed to define NP. See for example how Stephen Cook defines NP in the Official Problem Description of P vs NP (page 2). He completely avoids the names of Verifier and Certificate by simply saying LRP. Another approach (if you believe that the concept of Verifier is still worth keeping because you can use it for some other purpose) is to define Verifier as the most efficient TM among the class of TM's which decide the same language. This would make good common sense to me because in reality, given a set of algorithms that all can solve the same natural problem, why is it wrong to use just the best one and ignore the remaining. Why would you want to wast time to construct a (T(M))2-time TM while you have a T(M)-time TM that can solve your problem with the same amount of resource given?
Quote: "And why is the implicit assumption warranted that the various Turing machines deciding the problem can be ordered according to efficiency? Perhaps they are incomparable."
Response: Your last statement does hit a valid point. We cannot rule out the possibility that there might be TM's which are not comparable just as in reality, there is the possibility of having two algorithms which cannot be ranked in terms of efficiency. My point is that if you do have a set of TM's (such as the one you constructed) in which one is clearly better than the others, then you should go by the best one in the set. In the event that there exist more than one TM's and they are not comparable, both of them can be called Verifier. However, as I pointed out before, the definition of decidabilty guarantees the existence of one TM in all situations. This the one that we should refer to.
Quote: "In giving a precise and formal definition, you cannot discount counterexample to a proposed definition by statements like "does it serve any practical purpose"? The counterexample serves the very practical purpose of exhibiting that the definition in its current form is broken and must be replaced by something else."
Response: The statement "does it serve any practical purpose?" is not put in there to discount the counterexample. It is put there to point out that the artificial TM's you constructed are totally counter-productive. In fact, I did have an answer to your counter-example. That is, you go by the most efficient one and ignore the others. I just have to ask you this question again, Why would any one want to wast time to construct a (T(M))2-time TM while there is clearly a T(M)-time TM that can solve the same problem with the same amount of resource given?
Quote: "I contest your claim that the languages R and R' are generally considered the same; as decision problems they are in the same complexity class, at least in the sense that each is polynomially reducible to the other, which makes them equivalent for the classes that are usually considered of interest, including P and NP. If some people truly consider them the same rather than in some sense equivalent, I find that sloppy rather than weird. In any case, the article is not written only for people who are aware of and familiar with some abuse of language traditional in some field, but also for people who haven't even heard of computational complexity theory before."
Response: This is not an abuse of language. It is a fact. Two languages are considered the same in terms of solving computational complexity problems if they belong to the same complexity class. Based on the way you make your argument on this issue, I think any reasonable person who understands Computational Complexity Theory has to come to the conclusion that either you don't fully understand the theory (including its objective) or you understand it but are twisting the facts to make an argument just for the purpose of making an argument. If you think you can put up a technical article of P vs NP on Wikipedia (with a B+ mathematical rating) without confining it to the context of Computational Complexity Theory, but only go by what you think or what other people (not familiar with Computational Complexity Theory) would think, I rest my case.
Quote: "Lack of uniqueness makes a referent not definite. There is only one set that is equal to {n ∈ Z | even(n)}, which is why we can call this "the even integers"."
Response: This is strictly a double-standard talk. In your previous example, you want to treat every divisor of n as different divisor and you therefore use "a". Here, you want to group all the integers which are divisible by 2 into one set and treat it as a single entity.
Quote: "How can you say "LR is something specific whereas n is very general"? Both are not fixed and can be instantiated in many ways, and I really don't see why one should be considered more specific than the other.
Response: I don't know how many times I have to go through this. But I'll do it one more time. LR is specific because it is uniquely tied to the binary relation R which I have no control of. In fact, if the existing R changes in another situation to R', I would have no choice but to come up with LR'. R is the first thing that comes into the picture and is not restricted by any other condition, therefore, I can use "a". LR comes out of R and therefore I use "the". In your example, n is the very first thing that comes into the picture. It is totally arbitrary just like R. Therefore, you can use "a". At any subsequent point, if you talk about something that comes out of n, then you can use "the".
-- CBKAtTopsails ( talk) 02:28, 13 December 2007 (UTC)
Quote: "Listen. You do not own this article."
Response: "Who owns this article?'
Quote: "I've read this over and I believe CBKAtTopsails's argument has no merit, as well. Changing "a" to "the" here makes the description less clear, and it has no basis in the way articles are used in English. So I've reverted that change again."
Response: Can you introduce yourself and explain what authority you have over this Wikipedia article? Why do you use "a" Verifier but still keep "the" Certificate? Do you understand these two things are tied to each other?
-- CBKAtTopsails ( talk) 17:33, 13 December 2007 (UTC)
Quote: "Once something specific has been introduced and posited to exist, it is afterwards correct to refer to it using "the", which makes it clear that it is referring to the specific aforementioned subject rather than any of them. However, when positing it in the first place, you always say "there is" or "exists a" rather than "the". This is just typical usage in mathematical language."
Response: You are making my point. "The" Turing machine in the last sentence refers to the polynomial time Turing machine mentioned in condition (ii). "A" Turing machine would be appropriate only if it is made a stand-alone (or separate) definition.
-- CBKAtTopsails ( talk) 21:43, 13 December 2007 (UTC)
Quote: "I've read this over and I believe CBKAtTopsails's argument has no merit, as well. Changing "a" to "the" here makes the description less clear, and it has no basis in the way articles are used in English. So I've reverted that change again. "
Response: The owner of this statement has not demonstrated he has any specific authority over this article. Due to a malicious change that has been made to the article, I have no choice but to reverse it.
-- CBKAtTopsails ( talk) 05:48, 14 December 2007 (UTC)
I have read the articles on
Assume good faith and
Consensus. Here's what happened.
rspeer suddenly jumped in acting like a big boss to shut down a debate and then moved on to make the change without offering his analysis of the issue. Since he does not have any specific authority over this article, his view does not have to be final and there is no reason why some one else cannot reverse his change. This kind of attitute cannot be considered as good faith.
I posted a polite question to him and waited for a reasonable amount of time for his response. This is good faith. He ignored the question and acted like his view should be final. This again is not a good faith.
With this bad faith of rspeer, I had no choice but came to the conclusion that his change is malicious.
As to the issue of Consensus, I quote this from the article:
"So in summary, wikipedia decision making is not based on formal vote counting (" Wikipedia is not a majoritarian democracy"). This means that polling alone is not considered a means of decision-making, and it is certainly not a binding vote, and you do not need to abide by polls per se. Polling is generally discouraged, except in specialized processes such as AFD."
Until you show some good faith to resolve this issue, I am going to discontinue this dialogue.
However, I will continue to make any edit so long as it is necessary to defend the truth.
-- CBKAtTopsails ( talk) 16:41, 14 December 2007 (UTC)
Quote "This is completely contrary to mathematical convention. If you hear "every complete graph has a Hamiltonian cycle", you interpret that as a tentative statement? that the writer is not sure if there really is a Hamiltonian cycle? If so, I'm afraid you would be alone in that interpretation."
Response "Your example is taken out of context. In the original discussion, what was being argued about was the language LR. You should know that a language is not a complete graph and it is not always decidable. When it is not decidable, the Turing machine does not exist. Condition (ii) guarantees the existence of such Turing machine, therefore, we should talk about the one that is guaranteed to exist.
Quote: "Your changes do the definitions imply many confusing things: First, that there is a unique verifier for each language (or that one verifier is somehow the "chosen one"). "
Response: This is your implication and it is wrong. Go back to read again what I said. I argued against "the" meaning uniqueness
Quote: "Furthermore, since the verifier is unique (or there is one chosen one), there is a unique (or chosen) encoding for certificates. This is very misleading."
Response: This is an erroneous statement. For any given string x, a certificate of x (which may not exist) is just another string y such that (x, y) R where R is a given checking relation. It does not depend on any verifier.
Quote: "The corresponding verifiers will have the same running time but induce different witness relations L_R."
Response: This is again another erroneous statement. LR is constructed from the given checking relation R. It is not induced by any verifier.
Quote: "Also, since you seem to really enjoy appealing to "technical" issues, I should mention that when dealing with Turing machines, there is no unique "most efficient verifier", thanks to the Linear speedup theorem. So please don't tell us that the definition for NP involves only considering "the most efficient verifier"."
Response: This is a distortion of what I said. Some one created an artificial set of Turing machines which were clearly inferior to the one he was given and asked me which one I thought should be the verifier. I said he should go by the one that is the best in that set. The definition does not tell you to look for the most efficient verifier.
-- CBKAtTopsails ( talk) 17:00, 15 December 2007 (UTC)
Quote: "As to the other stuff you quote, you must have misunderstood my example. The relation R is not unique given an NP language. Different Rs induce different witness sets (for each x, ) and thus different verifiers for these sets. I gave an example of two different relations R for SAT, in which the certificates (satisfying assignments) were respectively encoded in opposite order. You insist on defining something as "the verifier" for the language, implying that there is a unique or somehow distinguished verifier."
Response: I understand your example but they are erroneous in the context of what we are debating. Let me explain why.
First, let me first give a simple illustrative example to lay down a platform for resolving this issue.
In pure mathematics, a fundamental technique used for proving the universal truth of a statement concerning a set of given objects is first to make a general representation of these objects. For example, if I want to prove that a certain statement is true for all even integers, what I would do as the first step is to let x represent an even interger. Once I have done this, I can treat x as just one even integer without having to worry about there are in fact an infinite number of even integers in the world. Then I go through a series of logical arguments to come to the conclusion that the statement is true for x (That is, T(x) is true). Now, if in every step of my arguemnts, I did not make any reference to any particular even number such as 2, 4, 2002, etc... and if the only information I used is the property that x is an even integer, then at the end of my argument, I can safely conclude that the statement is also true for all integers because everything I've said about x is also true for any even integer. Since I am fixing my sight on one interger x, with the exception of the first introductory statement in which I used "a", everywhere in my proof process, I can say "the" integer x or "the" "anything" which came out of x.
Now, let's get back to our NP definition. Here's what you have to go through in your mental process:
Step 1. You are given a language L.
Step 2. You look for a binary relation. Let's say you found one and we call it R. You might have found more than one but it doesn't matter because R is a general representation of all such relations.
Step 3. You construct LR. Again, you use a general representation of the language that came out of R. You can use "the" because you fix your sight at one such R and hence one such LR.
Step 4. Here's a little more tricky. You have to find a TM that decides LR. Condition (ii) guarantees that that LR is decidable which means that you can find at least one such TM's in all situations. The second might exist but it is not guaranteed. Since you have to maintain your generality, you can only focus on the only one that is guaranteed to exist in all situations. "The" TM that you found is unique in that sense.
Step 5. You call this TM that you found "the" verifier.
Step 6. You have a formal definition for NP.
Throughout the entire process, you fix your sight on one L, one R, one LR, one TM but you did it without loss of generality. Therefore, you can safely conclude that the definition you establish can be used on all situations.
-- CBKAtTopsails ( talk) 18:57, 16 December 2007 (UTC)
Quote: "It would imply that 2 is the unique divisor of 6."
Response: Are you making a joke here?
I got a better one for you.
There is an argument that given a TM that runs in time T(n), one can always contruct another TM that runs in time (T(n))2 and even one in time 2T(n). On the basis of this theory, one can contruct the following algorithms and argue that they be treated legitimate and not be thrown into the garbage can:
Algorithm A
Step 1. You are given a number n.
Step 2. You look for a decomposition into two or more factors greater than 1. Let's say you found one and we call this multiset of factors F.
Step 3. You take the smallest factor of F.
Step 4. For n = 1 to 20
Step 4b. You take a deep breath.
Step 4c. Next n
Step 5. You call this factor that you found "the" divisor.
Step 6. You have a formal definition for composite.
Algorithm B
Step 1. You are given a number n.
Step 2. You look for a decomposition into two or more factors greater than 1. Let's say you found one and we call this multiset of factors F.
Step 3. You take the smallest factor of F.
Step 4. For n = 1 to 220
Step 4b. You take a deep breath.
Step 4c. Next n
Step 5. You call this factor that you found "the" divisor.
Step 6. You have a formal definition for composite.
Of course, a counter argument to this is after taking 220 deep breaths, it is highly questionable whether one can still move on to step 5.
-- CBKAtTopsails ( talk) 00:22, 18 December 2007 (UTC)
"A" is an indefinite article. "A" is used when a precise subject (e.g., "a verifier") is not identified/selected out of a set of such possible subjects.
"The" is a definite article. "The" is used when a precise subject (e.g., "the verifier") is identified/selected out of a set of such possible subjects.
Here, by a certain point in the logical construct, it may be known that verifiers exist, but as at that point, no specific single one of the verifiers is identified/selected for the contemplated purpose.
Accordingly, it is "a verifier" when first introduced for the contemplated purpose and, for each subsequent occurrence, it is "the verifier". —Preceding unsigned comment added by 24.141.184.190 ( talk) 03:34, 13 June 2008 (UTC)
In my opinion, the whole definition should be rewritten. It looks messy and is hard to understand. The concept of a verifier is logically independent of any notion of complexity. Shouldn't we first define the concept of verifier, and then next define NP-ness as the existence of a fast verifier? Sketch:
I wonder, why is this not actually dealt with in the article NP (complexity)? That seems a better spot for a precise definition; then we can refer to the definition there and give a perhaps less precise but more intuitive description here. -- Lambiam 02:27, 15 December 2007 (UTC)
This sketch looks pretty messy to me so far and it has taken 18 lines already. Why don't you write it up formally to see how it looks and let's have a civilized debate on this. I think you also need a formal definition for verifier before you get into the definition of NP according to your sketch (although I think it is unnecessary).
-- CBKAtTopsails ( talk) 04:33, 15 December 2007 (UTC)
That sketch seems fine except where on earth does this c(x) function come from? Again, the impression is that there is a unique certificate for each x in L (that would be UP) or that one particular certificate is special. Furthermore, one could easily read that and assume that c(x) is computable in polynomial time, which could not be true for languages in NP \ P. There would have to be a big disclaimer about that. Since we're suggesting things, how about:
Plus a more English-y interpretation of what this actually means. Perhaps:
In my opinion, this is as far as this article needs to go in terms of formality. Right now the article re-defines polynomial time, running time of a TM, language of a TM. Going all the way down to these first principles is really unnecessary for this article. The goal should be to let the reader understand the ideas, not drown them in notation. If they care enough to see the dirty details, we should lead them to more suitable complexity theory articles. Blokhead ( talk) 15:16, 15 December 2007 (UTC)
Quote: "Equivalently, a language L is in NP if it can be expressed in the following form: , where p is a polynomial and R is a binary relation that is decidable in polynomial time. A polynomial-time machine that decides R is called a verifier for L (note that there may be many very different verifiers, corresponding to different relations R). Given , a value y such that R(x,y)=1 is called a certificate for x (or a witness for x)."
Response: I have some serious problems about this proposal. First, the statement R(x, y) = 1 is erroneous. A relation is a set of ordered pairs and therefore cannot be equal to 1. Second, a relation is not a language and therefore cannot be decided by a Turing machine. Third, there is nothing said about where R is coming from.
In summary, there is not enough rigor and details in this proposal to be called formal definition. It might be OK if it is called something else in the article. You cannot assume that there is no one who would come to search Wikipedia to look for some real math stuff on this subject. Putting out a sloppy formal definition is just irresponsible.
-- CBKAtTopsails ( talk) 17:31, 15 December 2007 (UTC)
Quote: "As to "nothing said about where R is coming from", I don't understand this. A language is in NP if there exists such a suitable R, that's it. Where it "comes from" is irrelevant."
Response: This is exactly the point and is a very important point in mathematics. In theorem proving in mathematics, one has to distinguish between "for all" and "for some" all the time. In your original proposal, you did not make this point clear enough. Keep in mind that R depends on L. Given another L', there might exist another R' which is different.
Quote: "Someone looking for "real math stuff" can go to a more specific article, like NP (complexity)."
Response: If you want to suggest to move the entire section on formal definition to another place, I don't have a problem with that but I suggest you write up your idea in formal language and let's have a discussion on it.
-- CBKAtTopsails ( talk) 16:29, 16 December 2007 (UTC)
You are contradicting yourself. In your first statement, you have already said a lot about p and q. First, you said, "n = pq". Then, you said, "|p| > 1 and |q| > 1". These things basically tell people where they are coming from. So, please don't tell me that you don't have to say any thing about where p and q are coming from. In the original proposal of Blokhead, where did he say anything at all to tell R comes out of L.
-- CBKAtTopsails ( talk) 23:44, 17 December 2007 (UTC)
On the "the" vs. "a" thing, it seems to be a draw. How about saving two characters and going for "a"? --
Vaughan Pratt (
talk) 04:15, 13 March 2008 (UTC)
Only slightly more seriously, I would vote in favor of "a" independently of the length as it reads more naturally to me. As my credentials I cite (a) my willingness to expose my real name to ridicule in the unfortunate event that I'm wrong at the top of my voice, (b) my 1969 master's thesis was in computational linguistics, translating English into logic, so I know at least a little about English grammar, and (c) AFAIK my paper showing that the primes are in NP was the first publication to use the word "certificate" in connection with NP, so I have a certain vested interest in seeing to it that the language surrounding "certificate" reads naturally in English. Is CBKAtTopsails a native English speaker, and if so did he come top of his English class in high school? If not I suggest he listen to how others think the sentence sounds each way. -- Vaughan Pratt ( talk) 04:33, 13 March 2008 (UTC)
The relationship between the complexity classes P and NP is an unsolved question in theoretical computer science. It is considered to be the most important problem in the field - the Clay Mathematics Institute has offered a $1 million US prize for the first correct proof.
To understand the complexity and the importance of the problem, consider the problem of breaking a four digit number lock. Common sense dictates that without knowing the key, one must try at least 5,000 numbers before one can succeed in opening the lock, with probability at least 0.5. In fact, it can be rigorously proven that if the lock's secret key is picked at random, then one must try 5,000 combinations to succeed with probability at least 0.5. In general, to open an n-digit lock one needs to try exponential in n number of combinations to open it with probability 0.5. Although, in this case the complexity of the problem of unlocking is clear and provable, consider the case where the lock is transparent, and one can see all the inner workings of the lock. Now, all bets are off!
There are thousands of problems in Computer Science where the complexity of solving the problem is not that clear cut. In fact, they all seem to exhibit this exponential search quality. On the other hand, no one has ever managed to prove, for any of these problems, that it must require an exponential search. There is however, one quality common to all these problems, which is different from the breaking of the opaque number lock problem. There is a description of an "easy" method or program available, which can verify if a given potential solution solves the problem. By "easy" we mean the program runs in polynomial time. Such problems are said to be in NP. Note that in the opaque number lock problem, one does not have access to a program or method which verifies if a given key works -- we only have access to the lock as a black box.
Thus, the quintessential question of Computer Science is whether all problems in NP can be solved in polynomial time, or not. In short, NP ?= P.
As a more concrete example, consider the Hamiltonian path problem. Given a graph with n vertices, and m edges, the Hamiltonian path problem is to determine if there is a path in the graph which visits each vertex exactly once. The problem is in NP, because one can give an easy method to check if a given potential path is indeed Hamiltonian -- just check that it goes to each node exactly once. As for the complexity of the problem, intuitively it seems that one must try all paths (an exponential number) in the graph to determine if there is a Hamiltonian path. However, there is no proof known of such a claim. On the other hand, one might use the fact that this problem is in NP, and hence has additional properties, namely that there is a description of a polynomial time verification algorithm available, to solve it in polynomial time. There is no such method known either.
One major advance that has been made is that many of these problems have been shown complete for the complexity class NP. In ther words, if any of these complete problems can be shown to be in P, then all of NP is in P, and similarly if one can show any complete problem in NP to be not in P, then none of the complete problems can be in P. —Preceding unsigned comment added by Ustadny ( talk • contribs) 17:44, 13 December 2007 (UTC)
I agree with the idea of giving more examples but disagree with the presumption that every one who comes to search Wiki does not have a math ground to understand or not interested in looking at the subject from a math perspective. Does Wiki have any statistics to support this notion?
-- CBKAtTopsails ( talk) 18:29, 15 December 2007 (UTC)
I notice that the section "Is P really practical" contains some of the real important points. Unfortunately, those points are written rather tangentially, when they are of extreme significance. For example, if it is proven that NP = RP, the P=NP debate is over... no one is going to harp over the issue that it really hasn't proven P=NP. Similarly, proving P/=NP is not enough, and one must prove NP /= AvgP, for the result to be of any significance...this clearly brings in randomness in choosing the instances. Of course, I have cryptography in mind, which is the real motive for proving P /=NP.
So, what I am suggesting is that in this extremely important page "P vs. NP", there be less formalism, and more stress on the issues. The formal points should be relegated to the NP page itself.
So here is what I consider is important (in decreasing order of importance): (i) The notion of difficulty or ease of solving computer science problems...some idea of polynomial time vs super-polynomial or exponential time (ii) Are there examples in Computer Science where this can be proven (for both ease and difficulty) (iii) Pointing out that there are gazillion problems in Computer Science where it is not proven either way..so the field is in a limbo...a bad state of affairs since we do not understand the fundamentally important problem... it has consequences for Robotics, vision, for how our own brain works, many Wall Street optimization problems etc etc. A subsection on some examples.(iv) Do these problems share something in common? YES! (v) Non-determinism (vi) Completeness of many problems (vii) More detail on the notion of "difficultly" or complexity of problems ...(a) probabilistic polynomial time (b) Average Polynomial time. (viii) Recent Advances .. viz. PCP. i.e. hardness of approximating (ix) Incompleteness of certain proof techniques... relativizing proof techniques are not going to work for proving either way... rules out most common easy proof techniques which are commonly employed for proving such results. For proving NP /= P even more techqniues, like Natural Proofs (cite Razborov-Rudich), are not going to work. Ustad NY ( talk) 15:32, 16 December 2007 (UTC)
Hey I solved this problem and P=NP. There are too many patterns and underlying relationships that it could take exponential time (looking at every possible combination). Owell maybe one day this post here on wikipedia will be history :) I will explain it in detail once I get it notarized etc. —Preceding unsigned comment added by 74.33.52.72 ( talk) 21:50, 18 December 2007 (UTC)
{{RFCsci | section=Request for comments: "the" verifier or "a" verifier? !! reason=Should the definition of NP-complete use "the" verifier or "a" verifier? !! time=08:38, 22 December 2007 (UTC)}}
The discussion on the following burning question has stalled: should the verifier-based definition of NP-complete in the section Formal definitions for P and NP use the definite article (the verifier) or the indefinite article (a verifier)? For that discussion, see the section #It is "the" verifier rather than "a" verrifier on this talk page.
Please only respond if you understand the notion of non-deterministic polynomial time.
Use the definite article "the", as in "is called the verifier":
Use the indefinite article "a", as in "is called a verifier":
Comment/further discussion:
There's a section that refers to a trivial problem DUH but does not provide any description of it. Can someone look into it? Thanks. -- Uchchwhash ( talk) 14:23, 14 February 2008 (UTC)
I had started a discussion above, titled "Suggested addition to "Is P really practical"". I'd like to continue the discussion that discussion here, because it seems like people pay more attention to sections at the bottom of the talk page than sections in the middle of it. First, let me repost my last post from above:
So, Dcoetzee and everyone, please let me know what you think about moving that section out of this article and into the "Cobham's Thesis" article. Navigatr85 23:01, 6 March 2008 (UTC)
On January 12, Brianjd changed the wording in the second half of this section from
to
Removing the word 'provably' makes the sentence more readable, but I'm worried it might also make it incorrect. Can someone prove that the algorithm works with the current wording, or was this just an inadvertent mistake? Nate Biggs ( talk) 15:00, 10 March 2008 (UTC)
This seems to have fallen on the floor, and there's still a gap in Blokhead's argument above. Can anybody give a complete proof that the algorithm is correct? If not, I'll add the word 'provably' back in the next couple days. Nate Biggs ( talk) 01:15, 14 March 2008 (UTC)
Is this known to be trivial or should it be cited in this Article?
(* complete dictionary of words, one per row, number of rows is (alpha^word), using words of length "word" and an alphabet of "alpha" number of characters *)
alpha=4;word=3;dict=.;
dict=Partition[Flatten[Tuples[Reverse[IdentityMatrix[alpha]],word]],(alpha*word)]
PseudoInverse[dict]==((Transpose[dict])*((alpha)^-(word -1)))-((word - 1)/(alpha^word)/word)
True
There is nothing special for alpha=4;word=3 - The method works for all cases where word < alpha, but that is a more verbose loop, and the Mathematica PseudoInverse function takes too long to calculate for values of alpha and word that are large, whereas the transpose side of the equation is fast.
100TWdoug ( talk) 15:11, 27 March 2008 (UTC)
As discussed above, I moved most of the information out of this section and into the Cobham's thesis article. This was done because Dcoetzee and I agreed that the discussion was not very relevant to the P=NP problem. However, I ended up deleting some of the discussion of quantum computers, not moving it, because it was irrelevant to Cobham's thesis. Maybe that information could be added back into the P=NP article. I would consider adding something like this:
But then, If we added that, I think we might need a citation for the first sentence of that paragraph. On the other hand, maybe we don't need any discussion of quantum computers in this article. What does everyone think? Navigatr85 04:16, 1 April 2008 (UTC)
I believe it is relevent as motivation for why the question is important. At least a summary should go here, so I did this. LouScheffer ( talk) 04:54, 1 April 2008 (UTC)
One of the sections says:
The problem of deciding the truth of a statement in Presburger arithmetic requires even more time. ... [deciding] the truth of Presburger statements has a runtime of at least 2^{2^{cn}} ... the problem ... [needs] more than exponential run time. Even more difficult are the undecidable problems, such as the halting problem.
That bound is interesting, but it should definitely be noted in the article that the halting problem is not more difficult than the problem of deciding the truth of a statement. That problem is also undecidable. Unfortunately I'm new to all this so I don't want to make the change myself for fear of messing it up worse! Can someone take care of it? .froth. ( talk) 02:39, 6 June 2008 (UTC)
So it's possible I misunderstood Froth's comment -- I thought he was claiming an actual error in the current text, and I was explaining why it wasn't an error. After reading Lambiam's comment I'm not sure that's what Froth meant. As to mentioning the decision problem for arithmetical truth here, I'm not sure that makes too much sense -- the halting problem is not just the most widely known undecidable problem, but it's also sort of an almost "minimal" one (not literally; there are nonzero unsolvability degrees below 0', but they're complicated to describe). Arithmetical truth is much more undecidable than the halting problem. -- Trovatore ( talk) 20:26, 6 June 2008 (UTC)
This section, to the best of my knowledge, is incorrect. Whilst I'm not a descriptive complexity expert, to the best of my knowledge, nobody has come up with a logical characterisation of P in the way that Fagin did with NP. Rather, extensions to FOL, such as adding LFP, IFP, orderings and Peano arithmetic are proposed, then counterexamples are eventually found. This seems to be supported by a talk I attended recently by Dr. Anuj Danwar, a descriptive complexity theorist. DPMulligan ( talk) 20:52, 13 July 2008 (UTC)
I'll repeat that I have no formal training in descriptive complexity, so I may be talking rubbish, but...
To the best of my knowledge, Immermann-Vardi states FO+LFP captures P only on ordered structures. See, for example, here: http://www.mathematik.tu-darmstadt.de/~otto/talks/dagstuhl.ps (pg 12), and here http://research.microsoft.com/ero/phd/2007summerschool/Posters/Bjarki%20Holm%20-%2013%20June%202007%201434.pdf (bottom of first column and top of second, note his supervisor). Ultimately, I think an expert needs to examine this page. DPMulligan ( talk) 16:18, 14 July 2008 (UTC)
Actually, see the Wikipedia link on LFP for confirmation. DPMulligan ( talk) 16:22, 14 July 2008 (UTC)
No problem :-) DPMulligan ( talk) 13:55, 16 July 2008 (UTC)
Well, over finite (totally) ordered structures (as the removed section mentioned), FO + LFP does capture P (and the question of P = NP (= PH) is equivalent to that of FO + LFP = SOE (= SO) over those structures), so it seems reasonable to reinstate the section, and perhaps be a bit more explicit about the ordering requirement. Thus, I am doing so. - Chinju ( talk) 09:16, 11 September 2008 (UTC)
Any reason why there shouldn't be a "references in popular culture" section on the page, with a mention of the multiple references from the first series of Numb3rs? 4fthawaiian ( talk) 13:27, 17 August 2008 (UTC)
I see in the beginning of the section that Clay Mathematics Institute is offering a million dollars prize. But in the 'Results about difficulty of proof...", it says "A million-dollars prize...". This generate some confusion. I'm editing this to say "The Clay Mathematics Institute million-dollars prize..." This makes it clear to a specific prize and not some generic prize. 24.16.28.198 ( talk) 16:39, 2 October 2008 (UTC)
In the NP-complete section a sentence says:
Does this yes instance means that there is a solution for that instance and no instance means that there is no such solution? If that is the case, I think that we should rephrase it a bit because it is kind of confusing. -- Obradović Goran (talk 12:35, 21 October 2008 (UTC)
The following was added to the easy-vs-hard section:
Similarly, the graph on the right shows the empirical complexity for solving the knapsack problem, demonstrating a sub-linear (!) growth. The argument that an NP-Complete problem therefore is solveable only heuristically is false (but quite common) [1].
I think this is misleading for two reasons, one theoretical and one practical:
LouScheffer ( talk) 04:06, 11 December 2008 (UTC)
I have therefore re-instated the picture with some additional comments and pointing to the reference.
Cngoulimis ( talk) 10:22, 11 December 2008 (UTC)
Although the article hints to it by starting " It is considered to be the most important problem in the field" would it be possible to have examples of why, if it were to be solved, it is so important? I'm thinking particularly of the cryptanalysis perspective but there's a lot more to it. This would be an additional item to the computer science and maths content for less technical readers. —Preceding unsigned comment added by 81.153.145.240 ( talk) 06:06, 24 December 2008 (UTC)
Shouldn't this be P vs NP problem (or P ≠ NP problem)? That seems the more common name in the literature. Shreevatsa ( talk) 20:25, 21 February 2009 (UTC)
Agreed. This should be P versus NP or P vs NP, or something along those lines. This is what the Clay Mathematical Institute calls it. [6] -- Robin ( talk) 20:13, 10 August 2009 (UTC)
User:Shreevatsa changed "algebrization" to "arithmetization." He's correct - I think I accidentally added the word "algebrization." Quote: "In their STOC’08 paper [AW08], Aaronson and Wigderson present the concept of “algebrization barrier”: the arithmetizing techniques cannot resolve the main open questions in complexity." [7] Dcoetzee 13:53, 9 March 2009 (UTC)
I changed the first of these sentences to the second in this article:
This sort of thing is codified in WP:MOSMATH. There must be some people to whom the first form above does not appear conspicuously jarring. Michael Hardy ( talk) 13:20, 13 March 2009 (UTC)
I noticed this link: Qeden, a wiki that aims to solve the Millennium Prize Problems ("down for maintenance" as of 15th of July 2008)
on the external links section of the page is dead. There is no reason for it to be included on the page yet for some reason it has been defended like its a piece of the holy grail. It could be interferring with Musatov's proof. And since it's a dead link, it holds no reason or logic for it to be included. In fact the link points to a page for a domain that is not only NOT under construction, but is in fact EXPIRED. Can we arrange to have it deleted? —Preceding unsigned comment added by 172.190.234.231 ( talk) 01:54, 22 March 2009 (UTC)
http://www.knowledgerush.com/kr/encyclopedia/Big_O_notation/
Please reference this for some interesting p=np generated content. —Preceding unsigned comment added by 172.190.234.231 ( talk) 02:15, 22 March 2009 (UTC)
It has been noted that an attempt has been made to censor a reference to ArXiv because it is not a refereeable source. However, there exists several other pages across Wikipedia where ArXiv is used as a reference. We cannot pick and choose sources as this is not in equality aligned with the Five Pillars of Wikipedia. Additionally it must be considered and noted that there are several pages which exist as uncontested references on this page that are not refereaable sources. Specifically the works of Mr. Scott Aaronson on his blog and the other reference which exists under the heading Complexity Zoo. The reference to ArXiv cannot legally be excluded unless it is standardized by the Wikipedia communnity that all references must refereeable sources. If this is indeed the case the source should then rightfully be removed. However this is not the case as I am unaware of any instance where ArXiv requires all references to indeed be refereeable. In dubiously is the fact that there exists other references uncontested which do not come from referereeable sources that remain and are allowed to attempt to prove counterpoint to the established fact. I would like to raise this to discussion if need be but I default to the wisdom of the community to support this fair engagement on this page. Anonymousone2 ( talk) 04:54, 12 April 2009 (UTC)
Copyright infringing text deleted.
If the term Succinct Problem must indeed be included in the P=NP problem it should then be allowed to exist on Wikipedia. For clarification if Succinct Problem is insistently included in the P=NP page it the term Succinct Problem should be allowed existence on Wikipedia. It seems there may be a system glitch where the page Succinct Problem keeps getting flagged and deleted each time it is created. May we please investigate this.
I suggest these two alternatives/outcomes:
1) The term Succinct Problem is given a page on Wikipedia. 2) The term Succinct Problem is removed from the P=NP problem page.
Thank you. I look forward to continued cooperation and investigation! In the spirit of wholehearted academic truth and positivity!!! Anonymousone2 ( talk) 05:02, 12 April 2009 (UTC)
Mr. Aaronson's blog is not a refereeable source yet it makes claims with respect to the P=NP Problem. If it is required that all referenced sources be refereeable then Mr. Aaronson's claim must also be removed. We must make specific arguments for our actions and not be vague with respect to such careful complex and sensitive matters. Please reference where in the Wikipedia requirement for References does it say this article is not submissable. If you cannot produce this material then the argument remains valid. —Preceding unsigned comment added by Anonymousone2 ( talk • contribs) 05:23, 12 April 2009 (UTC)
Please note and reference:
Wikipedia:Reliable source examples arXiv preprints and conference abstracts
arXiv is the oldest and most popular e-print server for scientific publications. arXiv is owned by Cornell University and funded, in part, by the National Science Foundation. Although arXiv papers do not necessarily undergo peer review prior to publication, arXiv exercises several mechanisms of editorial control. Publishing at arXiv requires authors to obtain endorsements for the topic areas in which they publish. This ensures that authors have an appropriate background and that the paper is appropriate for the topic area. Papers which appear unscholarly are removed from arXiv.
Unless you wish to disagree or change this Wikipedia policy. The ArXiv reference has been stated explicitly by Wikipedia as acceptable by this policy. Therefore the reference should remain. If you have a problem with this I may suggest you take it up with the Wikipedia community as this discussion has now not become about the P=NP problem but rather you have shifted the discussion to Wikipedia:Reliable source examples. I would refer you to this page for further reference.
The ArXiv should then legally remain as an acceptable reference on the P=NP problem page unless this changes. Anonymousone2 ( talk) 05:34, 12 April 2009 (UTC)
You have specifically stated and I quote you from above:
":The requirement is only that they be reliable."
ArXiv meets this reliablity requirement. —Preceding unsigned comment added by Anonymousone2 ( talk • contribs) 05:41, 12 April 2009 (UTC)
BTW, I rather disagree that a proof that P = NP would have no practical ...... very formal proof that P < NP - it is being under review by Discrete Applied ...... you are probably a sock puppet
I found this while using a new search engine called MeAmI.
The inclusion of the "......" is interesting. 172.191.9.162 ( talk) 23:12, 4 May 2009 (UTC)
All of the above discussion has assumed that P means "easy" and "not in P" means "hard". This assumption...
The first line in P = NP problem#Does NP mean "hard" and P mean "easy"? is a little ambiguous. I can't tell if it is inferring NP means "not in P", or is saying problems that are not in the P space?
All of the above discussion has assumed that P means "easy" and NP means "hard". This assumption...
Is this better?
R.Vinson ( talk) 15:48, 3 June 2009 (UTC)
[1] The algorithm. [2] The numbers. [3] The proof. [4] P=NP if NP=P [5] TSP
Per M.B.A. Matthew Cherian (backs claim by Musatov): First of all you notion that there are n! routes for the TSP is wrong considering the posing of the problem. First of all there is a starting city so if there is n! routes then this assumption fails. There are lesser routes may be n2 routes. Here we don't go to the starting city again which violates again the description of the problem that one should touch only a city ones. So this reduces the number of tours for a 5 city tour to just 20 < n2. Then the algorithm is designed in such a way that just the presence of n2 doesn't make it o(n2). It is still O(n) for Quick sort. In case you need a psudo code which I developed for someone else on request I am cutting and pasting it below. It is difficult as it is for modern computer scientists, I don't know how you will cope with it. Any how try and see if you understand. {{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{
Psudo-code for the solution to NP=P ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Type city[C, H, B, M, P] Type Data Beg_city, End_city:city Cost: integer Tick:Boolean End data
Array tour_cost[1..5, 1..4] of Data Temp:city Start_city: city List:city; cost, mincost:integer
Begin Min_cost := 0 Start_city :=city[1] Tick = false Fill array with data Bubble or Quick sort each column of the array in ascending order List :=start_city; Temp:=start_city 1: Find end_city in data of the start_city
If it is ticked increment start_city to next in the column Increment till not ticked city is reached tick it and append to the list Start_city = end_city in data Go to 1 Do this till all cities are reached Add up the cost and place it in the cost If cost < min_cost then min_cost = cost Start_city = temp and repeat 1 again Do this 4 times Now after the 4th iteration increment start_city(column) and temp=start_city Initialize data except the start_city Repeat 1 Do complete all the tours by incrementing start_city after 4 steps At the end data in the min_cost is the minimal cost tour. ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ —Preceding unsigned comment added by 76.94.191.206 ( talk) 07:15, 7 June 2009 (UTC)
It is said in the text of the article: the computer is ... sequential (it performs actions one after the other). As of 2009, these assumptions are satisfied by all practical computers yet devised.
Strictly speaking multi-CPU/multicore computers (such as Core2Duo based systems) are not sequential. Well, it is true that these can be modeled as sequential. For example a Core2Duo system can be modeled as odd instructions executed by one core and even instructions executed by the other core. (This model could add additional certainty however.)
porton ( talk) 16:35, 18 June 2009 (UTC)
Sci.Math on USENET that 2SAT is in P, but Max-2SAT is NP-hard. There exists α s.t. given a 2- CNF formula ϕ, deciding if Opt(ϕ) α is NP-hard. ... Proof. Opt 1, m sets covering ..
2SAT is in P, but Max-2SAT is NP-hard => .... Proof. Opt 1, m sets. covering everything. ... possible performance guarantee for the Max. p- Cover unless P=NP. ...
Q.E.D. ?
Not the place for 'new solutions, I know, but is USENET Sci.Math citable for computation problems if the proof checks out? Thanks!
Thanks! —Preceding unsigned comment added by 71.130.130.81 ( talk) 06:05, 14 August 2009 (UTC)
This page is quite long now. Can we archive this talk page? (I'm not too sure how to do that.) -- Robin ( talk) 13:37, 16 September 2009 (UTC)
The result of the move request was move to P versus NP problem. David Eppstein ( talk) 19:12, 24 October 2009 (UTC)
P = NP problem → P versus NP problem — The renaming of this page has been discussed above ( Talk:P_=_NP_problem#Name). It seemed to me that "P versus NP problem" seemed like the favourite, and I like the name too. Furthermore, this problem is usually referred to as the "P versus NP" problem in the research literature and popular magazine articles. Examples: Lance Fortnow's blog, ACM article on P versus NP, Clay Institute's page on the problem, Scott Aaronson's paper entitled "Is P Versus NP Formally Independent?" and another ACM survey on the problem. Robin ( talk) 19:23, 16 October 2009 (UTC)
*'''Support'''
or *'''Oppose'''
, then sign your comment with ~~~~
. Since
polling is not a substitute for discussion, please explain your reasons, taking into account
Wikipedia's naming conventions.If you read # ^ Aaronson, Scott, Is P Versus NP Formally Independent?, http://www.scottaaronson.com/papers/pnp.pdf .
If P=NP was true, then this very problem itself must be easy, right? But it's obviously hard, so P ≠ NP, as it shows the difficulty of its own proof. Should we add this? I find it a bit funny. Money is tight ( talk) 04:13, 13 December 2009 (UTC)
"Therefore, if one believes (as most complexity theorists do) that problems in NP do not have efficient algorithms, it would follow that such notions of independence cannot be possible." (emphasis mine) "Notions" should be "proofs" there no? I don't see how the notions are threatened. Pcap ping 12:00, 14 December 2009 (UTC)