"There is an algorithm such that..." and NP characterizations
in [Theory]
|
Prev: open all blocked sites in your country now
Next: Kurt Gödel PROVED that ALL math must be kept within certain
From: C. Nova on 7 Jan 2010 10:47 [ I posted the following to sci.math yesterday. No I realize that comp.theory might have been a more appropriate place. Since there were no responses yet, I give it a try here. ] Is there an agreement on what this statement "There is an algorithm such that.." means? My concern is for the following two alternatives: (1) We can write down an algorithm in enough detail that one could implement it on a computer, such that... (2) If we have some additional knowledge X, then we can [here the same statment as in (1)]. This question arose when I came across two slightly different characterizations of the NP complexity class. The common feature is the following statement: A language L belongs to NP iff there is a polynomial-time verifier for L. A verifier is an algorithm V taking two arguments with the following properties. There is a polynomial p such that: - If w is in L, then there is c with |c|<p(|w|) such that V(w,c)=1 (i.e., w is accepted). - If w is not in L, then for all c we have V(w,c)=0 (i.e., w is rejected). The difference lies in the understanding of "polynomial-time verifier". There are these two alternative definitions: (a) There is a polynomial q and the verifier runs in time q(|w|). (b) There is a polynomial q and the verifier runs in time q(|w|) if w is in L and for at least one c such that V(w,c)=1. In other words, (b) requires polynomial running time only for an accepting run, and even not for all accepting runs but only for at least one. Clearly, (a) implies (b). But what about the other direction? If we know the polynomial q, then we can construct a polynomial-time verifier in the sense of (a) from the polynomial-time verifier in the sense of (b): simply reject as soon as the running time exceeds q(|w|). But what if we do not know q? Exact knowledge of q corresponds to the additional knowledge X from (2) above. Since both, (a) and (b), occur in textbooks, I presume they are equivalent. But I'd like to know for sure and also what is the argument why they are equivalent. Thank you!
From: tchow on 7 Jan 2010 11:45
In article <hi4vmq$19l$2(a)news.albasani.net>, C. Nova <invalid(a)invalid.invalid> wrote: >Is there an agreement on what this statement "There is an >algorithm such that.." means? My concern is for the following two >alternatives: > >(1) We can write down an algorithm in enough detail that one >could implement it on a computer, such that... > >(2) If we have some additional knowledge X, then we can [here the >same statment as in (1)]. What I think you're groping for here is the distinction between classical mathematics and constructive or intuitionistic mathematics. Roughly speaking, the distinction is that in classical mathematics, existence proofs don't require explicit constructions, whereas in constructive mathematics they do. To prove classically that (for example) an equation has finitely many solutions, it is enough to derive a contradiction from the assumption that the equation has infinitely many solutions. You don't need to exhibit an algorithm for constructing the set of solutions. But a constructivist would avoid saying that the set of solutions is finite unless a construction were available; instead, the constructivist would say that the set is "not infinite" and would distinguish "not infinite" from "finite." In particular, the constructivist's rules for logical inference are different from the classical mathematician's. The dominant viewpoint today is classical. Any textbook you pick up or any lecture you attend where people don't explicitly say that they are using a constructivist framework is tacitly assumed to use a classical framework. Thus when you read "There is an algorithm such that..." you should not assume that it means (1). (2) is correct, where the knowledge X is simply the knowledge of what the algorithm is. If you know what the algorithm is then of course you can write it down in principle. In the explicit example you gave, not knowing q isn't relevant in classical mathematics. If q exists, then its existence can be used to deduce the existence of other things. The assumption is that things exist independently of whether anybody is aware of them. If a tree falls in a forest then it generates sound waves even if nobody is listening. To drive the point home further, consider the following extreme case. Classically, I can prove the following theorem: Theorem. There is an algorithm that takes the statement "P = NP" as input and correctly outputs its truth value. The proof is easy. Algorithm A always outputs "true" and Algorithm B always outputs "false." Either P = NP, in which case Algorithm A does the job, or P != NP, in which case Algorithm B does the job. Q.E.D. The fact that we have no clue whether Algorithm A or Algorithm B is the one that the Theorem is talking about is irrelevant. Classically, the above proof is completely correct. If you find that this account of classical mathematics makes you uncomfortable with it, then you may want to learn more about constructive or intuitionistic mathematics. In the meantime, however, you'll need to get used to classical reasoning because that's the dominant mode of thinking among mathematicians and computer scientists today. -- Tim Chow tchow-at-alum-dot-mit-dot-edu The range of our projectiles---even ... the artillery---however great, will never exceed four of those miles of which as many thousand separate us from the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences |