CDR: Minesweeper and defeating modern encryption technology
http://digitalmass.boston.com/news/daily/11/01/minesweeper.html from the article: "Proving the conjecture false would mean that modern encryption technology, the foundation of electronic commerce, would be open to easy attack." Isn't that a little general? Possibly jumping to some hasty conclusions about P versus NP as well? ok, Rush
Perhaps someone could explain this P vs. NP stuff to a normal not-yet-student? And, this program, what features are required to prove his theory? Thanks in advance, Olav On Thu, 02 Nov 2000, you wrote:
http://digitalmass.boston.com/news/daily/11/01/minesweeper.html
from the article: "Proving the conjecture false would mean that modern encryption technology, the foundation of electronic commerce, would be open to easy attack."
Isn't that a little general? Possibly jumping to some hasty conclusions about P versus NP as well?
It's been a long time since my computer science classes. But I'll give it a shot. The general name for this topic is complexity theory, the study of how inherently difficult certain classes of problems are to solve. Perhaps a not unreasonable summary would be problems in the class "P" can be solved in deterministic polynomial time. Some of these would include problems like simple sorting of strings that your OS does whenever it displays files in a directory. "NP" problems, on the other hand, are those that can be solved in nondeterministic polynomial time (think only by guessing). NP includes P. Of relevance to our discussion is that factoring is a NP problem. Much of modern cryptography relies on factoring being a "hard" problem. If it is not, things will get interesting quickly. :) Arnold Reinhold has another view here, saying P=NP is not relevant to crypto: http://world.std.com/~reinhold/p=np.txt -Declan (PS: don't use the toad.com address) On Fri, Nov 03, 2000 at 07:40:51PM +0100, Olav wrote:
Perhaps someone could explain this P vs. NP stuff to a normal not-yet-student? And, this program, what features are required to prove his theory?
Thanks in advance, Olav
On Thu, 02 Nov 2000, you wrote:
http://digitalmass.boston.com/news/daily/11/01/minesweeper.html
from the article: "Proving the conjecture false would mean that modern encryption technology, the foundation of electronic commerce, would be open to easy attack."
Isn't that a little general? Possibly jumping to some hasty conclusions about P versus NP as well?
On Sat, 4 Nov 2000, Declan McCullagh wrote:
"NP" problems, on the other hand, are those that can be solved in nondeterministic polynomial time (think only by guessing). NP includes P.
Actualy any time that can't be described using a polynomial (i.e. a0 + a1x + a2x^2 + ...) is NP. For example something that executes in factorial or exponential time is NP. If it is found that all NP can be reduced to P then I'd expect to see somebody be able to express a factorial (for example) as a polynomial. I ain't holding my breath. The 'nondeterministic' part simply means it's unknown if the problem can be reduced to a polynomial representation. As to 'guessing', some processes are polynomial and some aren't. ____________________________________________________________________ He is able who thinks he is able. Buddha The Armadillo Group ,::////;::-. James Choate Austin, Tx /:'///// ``::>/|/ ravage@ssz.com www.ssz.com .', |||| `/( e\ 512-451-7087 -====~~mm-'`-```-mm --'- --------------------------------------------------------------------
On Sat, 4 Nov 2000, Jim Choate wrote:
On Sat, 4 Nov 2000, Declan McCullagh wrote:
"NP" problems, on the other hand, are those that can be solved in nondeterministic polynomial time (think only by guessing). NP includes P.
Actualy any time that can't be described using a polynomial (i.e. a0 + a1x + a2x^2 + ...) is NP. For example something that executes in factorial or exponential time is NP.
I'm sorry - by the definitions I know, Declan has it closer. I'm not sure what you're getting at with "any time that can't be described..." or "something that executes in factorial or exponential time." As far as I know, NP is a class of *problems*, not a class of running times or even a class of algorithms. It doesn't make sense to say "x^2 is in NP", strictly speaking. It doesn't make sense to say "Ford-Fulkerson is in NP", strictly speaking. It makes more sense to say "primality testing" is in NP, if that refers to the problem of "Given a number n, is n prime?" NP can be defined as the class of problems for which there exist "succint certificates". That is, given a problem instance, there is some string S which a) is "succint" - its size is bounded by some polynomial in the size of the problem instance, b) can be verified as a "real" solution to the problem in polynomial time. i.e. the solution has a "certificate" which will convince you beyond doubt that this really is a solution. By the way, I don't recall if anyone's defined polynomial time yet in this thread. "Polynomial time" means that a computer will take a number of "steps" bounded by some polynomial which takes as parameter the length of the problem instance. Here "steps" mean what you think they mean; pinning them down precisely requires specifying your model of computation precisely, which can be time-consuming. NP is the class of all problems for which these "succint certificates" exist. Once you've found an answer, you can check it easily. But you are *not* guaranteed anything about finding the answer. Finding the answer might be "hard." This is one way of thinking about NP. Declan seems to have in mind an alternative (but equivalent) definition, in which we consider NP as the class of problems solvable by machines which have the magic ability to always know the "right" way to go at every branch point of a computation. This is another way to think about it; I personally prefer the "succint certificate" definition. Then P is the subset of NP -- problems for which finding the certificate is "easy." That is, there is a polynomial-time algorithm for finding a solution to the problem in the form of one of these "succint certificates." The P vs NP question is then whether P is a proper subset - i.e. is there some problem in NP but not in P? Factoring in in NP. A succint certificate that you've factored a number n are its factors, because you can just multiply them together to check. Finding the factors is another thing entirely... There are many more isssues here, of course. One such issue is the average case hardness of a problem. In the case of RSA, we actually have that RSA is "randomly self-reducible" -- the ability to solve even a small fraction of instances (say 1%) of all RSA instances would imply the ability to solve every RSA instance. This gives some evidence that RSA is "uniformly hard." But this is not known for many other problems in NP, for which the average case complexity is unclear. More fun on that subject may be found at Russell Impagliazzo's page http://www-cse.ucsd.edu/users/russell/ in the paper "A Personal View of Average Case Complexity." -David
At 2:20 PM -0500 11/4/00, dmolnar wrote:
On Sat, 4 Nov 2000, Jim Choate wrote:
On Sat, 4 Nov 2000, Declan McCullagh wrote:
"NP" problems, on the other hand, are those that can be solved in nondeterministic polynomial time (think only by guessing). NP includes P.
Actualy any time that can't be described using a polynomial (i.e. a0 + a1x + a2x^2 + ...) is NP. For example something that executes in factorial or exponential time is NP.
I'm sorry - by the definitions I know, Declan has it closer. I'm not sure what you're getting at with "any time that can't be described..." or "something that executes in factorial or exponential time." As far as I know, NP is a class of *problems*, not a class of running times or even a class of algorithms.
And I'm going to give a completely informal, but I hope useful, introduction. Though formalism is very important, and jargon is useful, I suspect that all the talk of "succinct certificates," "oracles," "reducibility," "nondeterministic polynomial time," "Co-NP," etc., isn't very useful to someone just coming to this stuff for the first time. I figure understanding math comes from thinking about specific problems, drawing pictures, mulling things over, drawing more pictures, and basically just "becoming one with the problem." Formal definitions then begin to make a lot more sense. While Bourbaki may favor only the tersest of explanations, I think they are dead wrong. (Fair warning: I knew a lot more about this stuff in 1992 when I was reading Garey and Johnson, Harel, etc. and trying to figure out the zero knowledge papers of Goldwasser and her colleagues. These days, terms like "Co-NP" are not in my daily repertoire of concepts I have a good handle on. But the basic ideas don't need such formal definitions. It's more important to have some _intuition_ about common problems and then see the obvious connections with crypto. David Molnar and others are much better versed in the current lingo.) So, the German guy, Olav, who asked about what P and NP and all that stuff means should think of a specific problem. The "Travelling Salesman Problem" is one problem that's a lot of fun to think about, for complexity issues (and also for specific algorithms, like "simulated annealing," "heuristic search," "genetic programming," etc.). However, I'm going to pick the "Hamiltonian Path" (or Hamiltonian Circuit) problem for most of my discussion. It's equally fun, and is one of the canonical "NP-complete" examples. It turns out that these problems are all similar in a deep way to each other. Though there may not be obvious links between Hamiltonian paths, tiling problems in the plane, Go problems on generalized Go boards, grammar problems, "Monkey puzzles," the Minesweeper game mentioned in this thread, and so on, it turns out that they share deep similarities. In fact, with some effort ("polynomial time effort," so to speak) one problem can be converted to another. Hence the notion that if one could find an "easy" algorithm to solve one, one would have solved all of them. (And always keep in mind that these problems are considered in their _general_ forms, with something like N cities, M x N tile arrays, a Go board of N x N grid points, and so on. Any _specific_ instance is not the essence, though of course a specific instance may still be hideously complicated to solve. And slight factors of 2 or 20 or even 20 million, or, indeed, anything short of "exponential in N," are not important. This is often called "Big O" notation, e.g, the complexity/effort goes as "O (N^3)" or "O (N!)". For exact definitions of these kinds of terms, consult any of the many books on this stuff; I'm just trying to provide the motivation and basic ideas here.) TRAVELLING SALESMAN PROBLEM Take 10 cities in Europe. For example: Berlin, Paris, Madrid, Rome, Marseilles, Hannover, Geneva, Amsterdam, Warsaw, and London. The TSP (Travelling Salesman Problem) would be to find the shortest path that connects all cities. Exhaustive search finds the shortest path on the order of (N -1)! calculations, where N is the number of cities. Actually, (N -1)! divided by two. Neither the direction of the path (the factor of 2) nor the starting city (the N -1) matters. For 10 cities, this is trivial to solve exhaustively: a mere 180,440 paths to be computed. However, for 20 cities the number of paths to be computed is about 6 x 10^16. For 50 cities, 3 x 10^62 paths. Whew. Are their better algorithms than exhaustive search over all paths? There may be many algorithms which give "pretty good" results. Dividing the cities into regions and optimizing each one, then stitching the results together works pretty well. (Used in a lot of algorithms, developed at Los Alamos for bomb designs...the Metropolis algorithm, for example.). Simulated annealing works pretty well. And so on. But these are all just approximations, not actual solutions. Good enough for engineering, and evolution (which is why a rabbit trying to get from his burrow to a food source to another food source doesn't die of starvation while he's trying to solve the Travelling Rabbit Problem exactly). One of the characteristics of this kind of problem is that there is often/usually no way to really measure "convergence on a solution." In a maze, for example, as one travels down various maze passages one may know that the goal is "just a few meters away," but this does little good: one may have to backtrack, or undo, ALL moves all the way back to the beginning of the maze search to take another branch point! "Close doesn't count." (The similarities with most modern crypto should be getting obvious. Most modern crypto only falls to "brute force" -- exhaustive search, trying all the paths, trying to factor a modulus, etc. There is no "getting closer" in most modern ciphers.) HAMILTONIAN PATH PROBLEM Find a path or cycle on a graph which passes through each node once and only once. (Or demonstrate whether any such cycle exists, a slightly different form.) I said I would also use the Hamiltonian Path Problem, HPP. This one is worth spending an hour or two drawing pictures and trying to find clever solutions. It will make the ideas much clearer, I think. And will also lead to a good understanding of "zero knowledge proofs" and the applications of them to things like pass phrases and security systems which don't leak information to wiretappers or even to the system being accessed! (Quite a feat, that.) OK, go back to those 10 cities in Europe. As we know, some of those cities have direct rail connections to other of the cities, some don't. Berlin and Paris are connected (ignore trivial issues of their perhaps being intermediate cities and towns...). Madrid and London are not connected directly by rail lines. The HPP is to take a graph, the set of cities and the links between them, and find a path or cycle which passes through each node (city) once and only once. And returns to the starting node. For example, one such path might look like: Rome to Marseilles to Madrid to Geneva to Warsaw to Berlin to Hannover to Amsterdam to Paris to London...whoops, London is only connected to Paris, so we're stuck in London. (This isn't the essence of a HPP, and one could stipulate that all cities must be connected to at least two other cities.) Let's throw London out and only consider N cities with connections to at least two other cities. How many possible paths need to be calculated depends on the number of interconnections. Some time spent with a pencil and paper will be invaluable. As the number of cities increases, the number of paths to consider goes up roughly as N! (N factorial, as above with the TSP). This is not polynomial in the number of cities. (Hence, for newcomers, one starts to get the idea of "nonpolynomial time," though there are some nuances and quibbles to deal with.) However, suppose someone presented a purported Hamiltonian cycle for a graph? That is, a claimed path through the N cities that passed through each city once and only once? This could be verified in practically no time, just by eyeballing the purported cycle. And thus one gets at the idea of an "oracle," a machine or god which can "guess" the solution. (Hence the idea behind "nondeterministic polynomial time." Again, there are nuances and formal issues, but this is the general idea.) (The intuition goes like this: For a large graph, of, say, 100 cities, the calculations required to compute the O (100!) paths would be vastly greater than all the computers that will ever be built could ever do in a billion universes, blah blah. If someone presents a solution, they must have "oracular" powers. Well, not really, as we shall see.) ZERO KNOWLEDGE--APPLYING THIS TO PASS PHRASES "I am Tim May and I present my proof of this: I know a Hamiltonian cycle for this particular graph which is my signature graph." So I present a graph with 100 cities on it, linked in various ways, and show a Hamiltonian cycle. Proof. Except that now I've given this proof to anyone watching, including the system or person I just showed the proof to. Is there a way to prove beyond any doubt that I know the Hamiltonian cycle without actually revealing it. There is. Wow. Trippy stuff. I'll wait a day or two to explain. However, related to our above discussion of HOW FREAKING HARD it is to compute such a Hamiltonian cycle on a reasonably large graph, HOW DID I EVER FIND ONE? Well, I have no oracular or magical abilities to "guess" ("non-deterministic polynomial time"). Instead, I constructed the Hamiltonian cycle from scratch! I took N cities, with no specified links, and connected them in some Hamiltonian cycle. Very easy to do. Just draw N cities or nodes and draw lines connecting them, satisfying the once and only once criterion. Ah, but then draw in a bunch of _other_ links between the nodes. The full graph, nodes and links, is VERY HARD for anyone else to find a Hamiltonian cycle for, but trivial for _me_ to find a Hamiltonian cycle for! So I can use the fact that I know a Hamiltonian cycle for "my" "signature graph" as a pass phrase, or other proof of identity. The trick to be able to prove that I know it without actually revealing it. As I said, I'll describe the trick later today or tomorrow. By the way, my favorite book on this is David Harel's "Algorithmics." Not exactly intended for a beginning student, but much more descriptive and basic than _most_ of the books on complexity theory. Lots of pictures, lots of descriptions of actual problems (tiling puzzles, my favorites). I confess that I only skimmed the sections on "Presburger arithmetic" and why it is "beyond NP" in some weird sense. Have fun, --Tim May -- ---------:---------:---------:---------:---------:---------:---------:---- Timothy C. May | Crypto Anarchy: encryption, digital money, ComSec 3DES: 831-728-0152 | anonymous networks, digital pseudonyms, zero W.A.S.T.E.: Corralitos, CA | knowledge, reputations, information markets, "Cyphernomicon" | black markets, collapse of governments.
Mr. May:
<x-flowed>At 2:20 PM -0500 11/4/00, dmolnar wrote:
On Sat, 4 Nov 2000, Jim Choate wrote:
On Sat, 4 Nov 2000, Declan McCullagh wrote:
"NP" problems, on the other hand, are those that can be solved in nondeterministic polynomial time (think only by guessing). NP includes P.
Actualy any time that can't be described using a polynomial (i.e. a0 + a1x + a2x^2 + ...) is NP. For example something that executes in factorial or exponential time is NP.
I'm sorry - by the definitions I know, Declan has it closer. I'm not sure what you're getting at with "any time that can't be described..." or "something that executes in factorial or exponential time." As far as I know, NP is a class of *problems*, not a class of running times or even a class of algorithms.
And I'm going to give a completely informal, but I hope useful, introduction. Though formalism is very important, and jargon is useful, I suspect that all the talk of "succinct certificates," "oracles," "reducibility," "nondeterministic polynomial time," "Co-NP," etc., isn't very useful to someone just coming to this stuff for the first time. <snip>
I confess that I only skimmed the sections on "Presburger arithmetic" and why it is "beyond NP" in some weird sense.
Have fun,
Thank you. -- A quote from Petro's Archives: ********************************************** "Despite almost every experience I've ever had with federal authority, I keep imagining its competence." John Perry Barlow
On Sat, 4 Nov 2000, dmolnar wrote:
I'm sorry - by the definitions I know, Declan has it closer. I'm not sure what you're getting at with "any time that can't be described..." or "something that executes in factorial or exponential time." As far as I know, NP is a class of *problems*, not a class of running times or even a class of algorithms.
Actualy it's all of them. Where the question comes from is when one looks at what it different instances of a given problem (e.g. the number of closed loop paths with no double crossings of a set of bridges, or the number of sequences that a set of cities can be visited without repeats). The goal is to find a solution in a fewer number of steps. There seem to be two major categories P and NP. So for the travelling salesman problem the question becomes how to describe the way the resources and problem space grow with relation to the number of cities. Were that relation to be describable in a polynomial then it would be a P. It looks like the problem is not describable by a polynomial and is therefore NP.
It doesn't make sense to say "x^2 is in NP", strictly speaking.
Stripping context removes meaning for anything. It's also changing the rules in the middle of the game. Well, if we're going to speak strictly then you're wrong. Strictly speaking we're talking of the relative complexity to resolve certain classes of problems. And in that case it DOES make sense to word statements like this. One can say that a given problem is "x^2" (which can't be NP since x^2 is a monomial, a class of polynomial and therefore P) with relation to resources or number of potential solutions with respect to going from n to n+1. So, if I have 10 of something and manipulate them and it takes me x amount of time and y resources. And I know the problem is "x^2" then I know that even small changes will drasticaly increase the number of solutions that I have to resolve. In fact I know that if I go to 20 of them things then I'll have to deal with a run time of approx. x^2 and require about y^2 resources. The point is to find an algorithm that uses those resources more sparingly.
It doesn't make sense to say "Ford-Fulkerson is in NP", strictly speaking.
It depends on it's complexity. And it does make sense of speaking to a particular algorithm (e.g. Seive of Aritoshanese) as being NP (which it is).
It makes more sense to say "primality testing" is in NP, if that refers to the problem of "Given a number n, is n prime?"
No, because 'primality testing' has a host of algorithms. It appears they are NP, but if somebody were to find a NEW algorithm that did it in P then primality testing, at least with respect to that algorithm, would be a P class problem. Another aspect of the N=NP is that the assumption is that if we can resolve a single NP to a P then that should resolve ALL NP to P. That's a pretty big leap with no real analysis behind it. A canon of faith rather than proof or fact. So the question does in fact effect isues of problem class, algorithm selection, and execution resource requirement. ____________________________________________________________________ He is able who thinks he is able. Buddha The Armadillo Group ,::////;::-. James Choate Austin, Tx /:'///// ``::>/|/ ravage@ssz.com www.ssz.com .', |||| `/( e\ 512-451-7087 -====~~mm-'`-```-mm --'- --------------------------------------------------------------------
On Sat, 4 Nov 2000, Jim Choate wrote: [much material elided - apologies for not going through everything precisely at this time. this point particularly struck me.]
Another aspect of the N=NP is that the assumption is that if we can resolve a single NP to a P then that should resolve ALL NP to P. That's a pretty big leap with no real analysis behind it. A canon of faith rather than proof or fact.
I'm sorry. I've been talking about the class "NP" as I've seen it defined in class and as in books such as Papadimitriou's _Computational Complexity_ or Garey & Johnson's _Computers and Intractability: A Guide to NP-Completeness_. This is only partly an appeal to authority; it's primarily to clarify what I mean when I'm writing and so try to avoid confusion. For the class NP as defined there (and I can give the definition here in a separate message if you want, but they do it with more skill and care than I would), it is *not* the case that "if we can resolve a single NP to P then that should resolve ALL NP to P." We *can* identify particular problems for which we can prove "if we can solve this problem P in polynomial time, then P = NP." Then P is called an "NP-hard" problem. If the problem P is also itself in NP, then P is called an "NP-complete" problem. We can prove these theorems by giving explicit methods to convert a solution algorithm for one such problem into a solution algorithm for any problem in NP. The original problem for which this was shown was formula satisfiability: "given a boolean formula, does there exist an assignment to all of its variables which makes the formula evaluate to true?" If you can solve formula satisfiability in polynomial time, you can solve any NP problem in polynomial time. The proof is due to Cook (or independently Levin in the USSR). You can look it up, or I can try to explain it. If you don't believe it just on my assertion here, fine. Please say what you need in order to be convinced. But if you deny that the Cook theorem is proved or take it to mean something different, please say so. You seem to believe that an NP-hardness result is a "pretty big leap with no analysis behind it. A canon of faith rather than proof or fact." Why do you think this? How does it resolve with the Cook result? Where are you getting your definition of NP? Is every problem in NP NP-complete? Now, if P = NP, then every single problem in NP is "NP-hard" trivially. Because we can solve them ALL in polynomial time. But if P != NP, then the question "are all problems in NP NP-hard?" becomes interesting. Not every problem in NP is known to be NP-hard, however. For instance, factoring is not known to be NP-hard. If factoring is found to be polynomial time, then P ?= NP is still open. We seem to have different definitions of "the class NP" at work here, and so we're going to talk past each other until this is resolved. Is it clear to you what I'm using now? if not, what more do you need? Thanks, -David
On Sat, 4 Nov 2000, dmolnar wrote:
Another aspect of the N=NP is that the assumption is that if we can resolve a single NP to a P then that should resolve ALL NP to P. That's a pretty big leap with no real analysis behind it. A canon of faith rather than proof or fact.
I'm sorry. I've been talking about the class "NP" as I've seen it defined in class and as in books such as Papadimitriou's _Computational Complexity_ or Garey & Johnson's _Computers and Intractability: A Guide to NP-Completeness_. This is only partly an appeal to authority; it's primarily to clarify what I mean when I'm writing and so try to avoid confusion.
For the class NP as defined there (and I can give the definition here in a separate message if you want, but they do it with more skill and care than I would), it is *not* the case that "if we can resolve a single NP to P then that should resolve ALL NP to P."
We *can* identify particular problems for which we can prove "if we can solve this problem P in polynomial time, then P = NP." Then P is called an "NP-hard" problem. If the problem P is also itself in NP, then P is called an "NP-complete" problem. We can prove these theorems by giving explicit methods to convert a solution algorithm for one such problem into a solution algorithm for any problem in NP.
I accept that. A point of clarity, I'm not claiming that N=NP for a single problem means I can solve all of them. I believe that to say that if a problem isn't polynomial then it must fit into NP and that ALL NP are equivalent is just silly. It's like saying N! and be reduced to e^x, though neither can strictly be reduced to a polynomial. However, especialy in the press, there seems to be exactly this sort of view. It seems to be that the impression they leave is that if we find a P solution to primality we'll as a consequence have a solution avenue to all other NP problems. It's that 'all other' that I object too. With respect to your statement above, it just seems they use your wording and leave the 'particular problems' part out. ____________________________________________________________________ He is able who thinks he is able. Buddha The Armadillo Group ,::////;::-. James Choate Austin, Tx /:'///// ``::>/|/ ravage@ssz.com www.ssz.com .', |||| `/( e\ 512-451-7087 -====~~mm-'`-```-mm --'- --------------------------------------------------------------------
On Sat, 4 Nov 2000, dmolnar wrote:
The original problem for which this was shown was formula satisfiability: "given a boolean formula, does there exist an assignment to all of its variables which makes the formula evaluate to true?" If you can solve formula satisfiability in polynomial time, you can solve any NP problem in polynomial time.
Which we now know to be impossible given Godels Incompleteness Theorem, it's also a form of Turings Halting Problem. It should be worded something like: "given SOME boolean formula,..." ____________________________________________________________________ He is able who thinks he is able. Buddha The Armadillo Group ,::////;::-. James Choate Austin, Tx /:'///// ``::>/|/ ravage@ssz.com www.ssz.com .', |||| `/( e\ 512-451-7087 -====~~mm-'`-```-mm --'- --------------------------------------------------------------------
On Sat, 4 Nov 2000, dmolnar wrote:
The original problem for which this was shown was formula satisfiability: "given a boolean formula, does there exist an assignment to all of its variables which makes the formula evaluate to true?" If you can solve formula satisfiability in polynomial time, you can solve any NP problem in polynomial time.
The proof is due to Cook (or independently Levin in the USSR). You can look it up, or I can try to explain it. If you don't believe it just on my assertion here, fine. Please say what you need in order to be convinced. But if you deny that the Cook theorem is proved or take it to mean something different, please say so.
You seem to believe that an NP-hardness result is a "pretty big leap with no analysis behind it. A canon of faith rather than proof or fact." Why do you think this? How does it resolve with the Cook result? Where are you getting your definition of NP?
See the last sentence in para 1 above. You are in fact saying if I can resolve one NP -> P then I can resovle ALL NP as P. Yet in your earlier email you said the opposite, that you didn't believe that saying the solution of one NP in a P format meant that all NP could be solved in a P format. You are in effect saying that primality, travelling salesman, etc. are reducible to a single algorithm with respect to resolution. To word the assertion differently, "All problems can be reduced to a sum of products such that no single monomial has a factor more complicated than a power." I really doubt reality is that simple. As to Cooks assertion, it is possible to create logical statements which are irresolvable, irrespective of time or algorithm. So it is clear that there are in fact statements which can't be resolved so there must be at least some class of NP that are not resolvable to P. But you're welcome to your own opinion. ____________________________________________________________________ He is able who thinks he is able. Buddha The Armadillo Group ,::////;::-. James Choate Austin, Tx /:'///// ``::>/|/ ravage@ssz.com www.ssz.com .', |||| `/( e\ 512-451-7087 -====~~mm-'`-```-mm --'- --------------------------------------------------------------------
On Sat, 4 Nov 2000, Jim Choate wrote:
You are in fact saying if I can resolve one NP -> P then I can resovle ALL NP as P. Yet in your earlier email you said the opposite, that you didn't believe that saying the solution of one NP in a P format meant that all NP could be solved in a P format.
I was trying to make a distinction between two kinds of problems. I'm sorry if I wasn't clear. 1) The first kind are NP-hard problems. These are problems for which knowing an algorithm to solve the problem *would* allow you to solve every problem in NP. These are the kinds of problems I was referring to in the paragraph I snipped from this message. 2) The second kind are problems which are not known to be in P, which ARE in NP, but which are not known to be NP-hard. Factoring is an example of one such problem. So is discrete log. Knowing a solution algorithm for one of these types of problems does not necessarily tell you anything about solutions for any other problem in NP. These are the kinds of problems I was referring to in "the previous e-mail." I agree with you that the popular press often ignores this distinction, and it's annoying as all get out.
You are in effect saying that primality, travelling salesman, etc. are reducible to a single algorithm with respect to resolution.
It's not a single algorithm, per se. It's a combination of the "reduction" from primality, salesman, etc. to satisfiability + the algorithm for solving SAT. The reduction can be thought of as "reformatting" the problem in terms of SAT; it is specific to each problem. Suppose I have an efficient algorithm FINDSAT(F) which takes a boolean formula F and returns "Y" if it's satisfiable, "N" if it is not. Now my algorithm for factoring looks rougly like this: 1) Run my reduction algorithm from factoring --> SAT. This reduction algorithm is specially tailored to the factoring problem, but one can always be found. Why? 1.1) Because factoring can always be expressed as a program on a nondeterministic TM 1.2) Cook's proof shows how to mechanically express the computation of a nondeterministic TM as a formula which is satisfiable iff the TM halts and accepts on a given string. 2) Take the big weird formula generated from step 1) and feed to FINDSAT(F). You now have a way to solve the problem using FINDSAT(F).
As to Cooks assertion, it is possible to create logical statements which are irresolvable, irrespective of time or algorithm. So it is clear that there are in fact statements which can't be resolved so there must be at least some class of NP that are not resolvable to P.
What I would say, according to my understanding of the definitions, is that there is no succint certificate for unsatisfiability known. So the problem of recognizing irresolvable = unsatisfiable formulas is not a problem in NP.
But you're welcome to your own opinion.
As are you, but the hope is that in mathematical matters we can come to some kind of agreement. -David
On Sat, 4 Nov 2000, dmolnar wrote:
On Sat, 4 Nov 2000, Jim Choate wrote:
You are in fact saying if I can resolve one NP -> P then I can resovle ALL NP as P. Yet in your earlier email you said the opposite, that you didn't believe that saying the solution of one NP in a P format meant that all NP could be solved in a P format.
I was trying to make a distinction between two kinds of problems. I'm sorry if I wasn't clear.
1) The first kind are NP-hard problems. These are problems for which knowing an algorithm to solve the problem *would* allow you to solve every problem in NP. These are the kinds of problems I was referring to in the paragraph I snipped from this message.
Let's start with a set of sentences. Each of those sentences is a sequence of connective, operators, and values that reduce to binary values. Our job is to determine the truth or falsity value of each sentence in that set. I further see no reason to suspect that the sentence set itself is even countable (and even if it is it is still infinite in extent). What you propose isn't possible. There are logical statements in the P & NP class which are not provable. There is no way that you can say that a set of sentences can at the same time contain insoluble members (and there isn't a way to tell them apart since the test may itself be unprovable) and have an algorithm which will solve all of them because you can solve one of them. Now if you restrict the problems to specific domains (since NP contains P I'll talk only to NP) then we are injecting a distinction of class in the NP and there goes our "if I can prove one of them I can prove all of them". ____________________________________________________________________ He is able who thinks he is able. Buddha The Armadillo Group ,::////;::-. James Choate Austin, Tx /:'///// ``::>/|/ ravage@ssz.com www.ssz.com .', |||| `/( e\ 512-451-7087 -====~~mm-'`-```-mm --'- --------------------------------------------------------------------
On Sat, 4 Nov 2000, Jim Choate wrote:
of connective, operators, and values that reduce to binary values. Our job is to determine the truth or falsity value of each sentence in that set. I further see no reason to suspect that the sentence set itself is even countable (and even if it is it is still infinite in extent).
OK. This seems to be a point where the definitions are a crucial issue. Let me define the set SAT = { B | B is a Boolean formula, and B has a satisfying assignment} You're quite right in noticing that this set is infinite. In particular, it has all sentences of the form (P or NOT P) OR (Q or NOT Q) OR ... i.e. all tautologies ORed with themselves. To show SAT is in NP, we only need to show how to construct a succint certificate that B has a satisfying assignment. We only need to know how to answer "yes" to the question "Is the formula F in SAT?" If a formula has no satisfying assignment, then we don't care about it. I assume that "has a satisfying assignment" is equivalent to "true" is equivalent to "provable" in your lexicon. Please let me know if I'm off base, because that will screw up the following discussion. Then "false" is equivalent to "not provable" is equivalent to "has no satisfying assignment." Please let me know if that's off base as well. By the way -- you mentioned Goedel's Theorem at one point. I'm not clear how that is relevant. It seemed to me that you wanted to invoke the theorem to guarantee the existence of sentences which are somehow neither true nor false, or cannot be checked as being true or false. But for ANY finite Boolean formula, and for ANY assignment, there is ALWAYS a way to *check* whether the assignment satisfies the formula or not. Replace the variables with the values from the assignment. Evaluate the formula according to the usual laws of Boolean algebra. This always works. So the formula assignment can always be checked and the question "Is F in SAT?" is therefore in NP. The problem is finding the satisfying assignment if one exists. Notice that a Turing Machine which is allowed to take exponential time is capable of trying EVERY assignment and then finding a correct assignment if one exists, or rejecting the formula if one does not exist. So determining the satisfiability of Boolean formulae is always computable in exponential time. There does not seem to be a question of "unprovability" or "uncomputability" involved. Give me a finite Boolean formula (and those are the only kind we're considering, aren't we?), I give you a computable algorithm for finding the satisfying assignment: try all the possibilities. Sure it's exponential-time, but it's computable and provably so. Are you invoking Goedel's theorem to say that there exist sentences which have no satisfying assignment? or have I completely misunderstood what you are getting at with the term "sentences" ?
What you propose isn't possible. There are logical statements in the P & NP class which are not provable. There is no way that you can say that a set of sentences can at the same time contain insoluble members (and there isn't a way to tell them apart since the test may itself be unprovable) and have an algorithm which will solve all of them because you can solve one of them.
Now I'm confused. What are these sentences? Are you taking these sentences as each representing some problem in the class NP? or are they just members of all the possible boolean formulae? What's going on? What do you mean by "a logical statement in the P & NP class"? I'm having trouble here because I tend to regard "NP" as a class of decision problems only, and you seem to argue for an "NP" which allows for equivocation between a) the statement of a problem - "MAXFLOW is in NP" b) an algorithm used to solve a problem - "Ford-Fulkerson is in NP" and c) the computational complexity of an algorithm - "2^n is in NP" so I am not sure if this is a new extension of "NP" to include d) a Boolean formula encoding the statement of a problem. I suspect it is, but I'm not sure.
Now if you restrict the problems to specific domains (since NP contains P I'll talk only to NP) then we are injecting a distinction of class in the NP and there goes our "if I can prove one of them I can prove all of them".
I can't understand this until we clear up the previous point. I'm sorry. :-( Thanks, -David Molnar
On Sun, 5 Nov 2000, dmolnar wrote:
OK. This seems to be a point where the definitions are a crucial issue.
Let me define the set
SAT = { B | B is a Boolean formula, and B has a satisfying assignment}
You're quite right in noticing that this set is infinite. In particular, it has all sentences of the form (P or NOT P) OR (Q or NOT Q) OR ... i.e. all tautologies ORed with themselves.
Infinite? It isn't even countable. It's of class Aleph 1, not Aleph Null. The problem is the last conditional of your definition. It's impossible even in principle to create such a universal set and define an operator to say if a particular sentence does or doesn't resolve, never mind it's actual value. Godel disallows a universal sentence consistency verifier, as distinct from a universal resolver which it also prohibits. Your conditional assumes axiomaticaly the existance of such a beast. In effect Godel says you can't have a universal translator (i.e. Translate the Boolean sentence into a 0 or 1 depending upon if it is consistent or 'has a satisfying assignment'). You are, with that conditional, in effect saying that even though Godel's Incompleteness Theorem says that I can create Boolean sentences that are not resolvable you can resolve all of them. Clearly paradoxical. I feel safer giving up 'has a satisfying assignment' over Godel's. The reality is that if you have a problem set such that all members are resolvable you are using a sub-set of the actual problem set. In other words you've found a 'distinction'. It is my assertion that there are many such 'distinctions' in the NP set that in fact mean there are different classes of NP problems which are not resolvable to one another and whose solution algorithms are completely indipendent. The first such distinction, per Godel's, is that there are some problems I can't resolve. So, why should there be only a single distinction? I can certainly think of no reason to limit it. So, unless somebody can demonstrate that NP problems break down only into solvable and unsolvable problems (which isn't possible via Godel's) I feel pretty safe that P<>NP (I'm pretty sure nobody can build a universal tester for that either). While P may be in NP, there are some NP that won't resolve to P's. I've unexpectedly run into this exact same sort of problem with Goldbach's recently. Additive Number Theory of class h=2 and degree 1 are fun! When one speaks of 'cosmological' sets (i.e. sets that contain all possible arrangements) it isn't possible even in theory to actualy resolve all of the individual members. ____________________________________________________________________ He is able who thinks he is able. Buddha The Armadillo Group ,::////;::-. James Choate Austin, Tx /:'///// ``::>/|/ ravage@ssz.com www.ssz.com .', |||| `/( e\ 512-451-7087 -====~~mm-'`-```-mm --'- --------------------------------------------------------------------
On Sat, 4 Nov 2000, Jim Choate wrote:
As to Cooks assertion, it is possible to create logical statements which are irresolvable, irrespective of time or algorithm. So it is clear that there are in fact statements which can't be resolved so there must be at least some class of NP that are not resolvable to P.
You are talking about two very different problems, here. Gödel/Turing sorta things are about problems where quantifiers over an infinite set are permitted. Gödel is about verifying a given formula for all natural numbers (a countable infinity), Turing about deciding whether any given algorithm (there are a countable infinity of these) halts. An instance of SAT, on the other hand, quantifies only over a sequence of fixed length vectors of truth values (the list of all the possible combinations of truth values to be assigned to the variables of the boolean function being tested). If you think of these vectors as binary words, there are always a finite number of these. This number is exponential in the number of variables of the function. So a valid exp-time algorithm to solve SAT is to list all the possible combinations of input values to the multivariate boolean formula, feed them through it (I seem to think that around n^2 time is needed for this) and see whether one of them really satistified it. The latter strategy does not work for Turing/Gödel-kinda situations because the computation would not halt, regardless of the function chosen. It is easy to see that the logic structure of Gödel's and Turing's theorem is far deeper than that of SAT, while SAT is the only one which admits any kind of computational complexity analysis. Sampo Syreeni <decoy@iki.fi>, aka decoy, student/math/Helsinki university
On Wed, 8 Nov 2000, Sampo A Syreeni wrote:
You are talking about two very different problems, here. G�del/Turing sorta things are about problems where quantifiers over an infinite set are permitted.
No, it is exactly the same thing. Godel applies to ANY set of axioms and conjectures. It is universal. Godel clearly applies to Boolean algebra. The theorems we are speaking of are applied to Boolean algebra. The theorems require either a universal consistency or evaluator, either is prohibited by Godel's. In the particular case we are speaking of we are talking about the situation where the language consists of "all consistent/valid/evaluatable/assignable boolean sentences". Hence, somebody did a naughty... ____________________________________________________________________ He is able who thinks he is able. Buddha The Armadillo Group ,::////;::-. James Choate Austin, Tx /:'///// ``::>/|/ ravage@ssz.com www.ssz.com .', |||| `/( e\ 512-451-7087 -====~~mm-'`-```-mm --'- --------------------------------------------------------------------
On Thu, 9 Nov 2000, Jim Choate wrote:
On Wed, 8 Nov 2000, Sampo A Syreeni wrote:
You are talking about two very different problems, here. G�del/Turing sorta things are about problems where quantifiers over an infinite set are permitted.
No, it is exactly the same thing. Godel applies to ANY set of axioms and conjectures. It is universal.
Godel clearly applies to Boolean algebra. The theorems we are speaking of are applied to Boolean algebra. The theorems require either a universal consistency or evaluator, either is prohibited by Godel's.
In the particular case we are speaking of we are talking about the situation where the language consists of "all consistent/valid/evaluatable/assignable boolean sentences".
Hence, somebody did a naughty...
If you have a 'language' that is provably consistent then you know that that language is not complete or 'universal'. There MUST!!! be sentences which are not included in the listing. ____________________________________________________________________ He is able who thinks he is able. Buddha The Armadillo Group ,::////;::-. James Choate Austin, Tx /:'///// ``::>/|/ ravage@ssz.com www.ssz.com .', |||| `/( e\ 512-451-7087 -====~~mm-'`-```-mm --'- --------------------------------------------------------------------
At 06:12 PM 11/9/00 -0500, Jim Choate wrote:
If you have a 'language' that is provably consistent then you know that that language is not complete or 'universal'. There MUST!!! be sentences which are not included in the listing.
This sentence is false. Big deal. Only self-referential statements run into lying-cretin problems. Go:del is neat but overblown in popular culture.
On Thu, 9 Nov 2000, David Honig wrote:
At 06:12 PM 11/9/00 -0500, Jim Choate wrote:
If you have a 'language' that is provably consistent then you know that that language is not complete or 'universal'. There MUST!!! be sentences which are not included in the listing.
This sentence is false.
Your proof. I refer you to, http://www.miskatonic.org/godel.html ____________________________________________________________________ He is able who thinks he is able. Buddha The Armadillo Group ,::////;::-. James Choate Austin, Tx /:'///// ``::>/|/ ravage@ssz.com www.ssz.com .', |||| `/( e\ 512-451-7087 -====~~mm-'`-```-mm --'- --------------------------------------------------------------------
At 05:16 PM 11/9/00 -0600, Jim Choate wrote:
On Thu, 9 Nov 2000, Jim Choate wrote:
On Wed, 8 Nov 2000, Sampo A Syreeni wrote:
You are talking about two very different problems, here. Gödel/Turing sorta things are about problems where quantifiers over an infinite set are permitted. In the particular case we are speaking of we are talking about the situation where the language consists of "all consistent/valid/evaluatable/assignable boolean sentences".
Hence, somebody did a naughty...
If you have a 'language' that is provably consistent then you know that that language is not complete or 'universal'. There MUST!!! be sentences which are not included in the listing.
That's fine. The Satisfiability problem, and in particular 3-SAT, doesn't claim to be complete or universal. It's just a very large and versatile class of Booleans, but it doesn't pretend to contain Booleans that describe encodings of their own truth values (unlike this discussion :-) Just things of the form (A1 or A2 or A3...) AND (B1 or B2 or B3...) AND .... Thanks! Bill Bill Stewart, bill.stewart@pobox.com PGP Fingerprint D454 E202 CBC8 40BF 3C85 B884 0ABE 4639
On Sat, 4 Nov 2000, dmolnar wrote:
The original problem for which this was shown was formula satisfiability: "given a boolean formula, does there exist an assignment to all of its variables which makes the formula evaluate to true?"
Wasn't it that quite a number of actual instances of this particular problem fall easily to heuristics? Is this connected to the concept of "uniform hardness" that was brought up? Sampo Syreeni <decoy@iki.fi>, aka decoy, student/math/Helsinki university
At 11:02 AM 11/4/00 -0600, Jim Choate wrote:
On Sat, 4 Nov 2000, Declan McCullagh wrote:
"NP" problems, on the other hand, are those that can be solved in nondeterministic polynomial time (think only by guessing). NP includes P.
Actualy any time that can't be described using a polynomial (i.e. a0 + a1x + a2x^2 + ...) is NP. For example something that executes in factorial or exponential time is NP.
If it is found that all NP can be reduced to P then I'd expect to see somebody be able to express a factorial (for example) as a polynomial. I ain't holding my breath.
The 'nondeterministic' part simply means it's unknown if the problem can be reduced to a polynomial representation.
As to 'guessing', some processes are polynomial and some aren't.
Jim, you're misunderstanding the class NP, though you're correct in not holding your breath. It's not "all problems that can't be solved in polynomial time." It's "all problems that can be solved in polynomial time by a non-deterministic Turing machine." A non-deterministic Turing machine is allowed to guess answers (or at least, to guess a polynomial number of answers). Answers to NP problems can be verified in polynomial time - the hypothetical machine guesses the answer, and verifies it in a polynomially bounded time. There are lots of problems that are outside of NP - they're known to take exponential amounts of time to solve, regardless of whether you've got a NTM which can pull correct bits out of /dev/oracle. There are also lots of problems for which the complexity is unknown, such as factoring. Until ~20 years ago, linear programming was believed to be part of NP, but Karmarkar's algorithm (which I think was based on Shor's work?) demonstrated a way to solve it in polynomial time, though with an annoyingly large polynomial. NP-complete problems are a certain set of problems for which it can be proven that if you can solve one problem in that set in polynomial time, you can use only polynomially more work to solve any other problem in that set. Usually people reduce things to the Satisfiability problem, though sometimes others are more convenient. When I was studying complexity theory from Karp back in grad school, one thing I didn't understand was the issue of whether there might be other sets of problems that are similarly hard but not reducable to each other, e.g. a set NP1 of hard problems including satistiability, Hamiltonian paths, etc., a set NP2 of hard problems including Foo and Bar that are reducable to each other but haven't been proven to solve or be solved by NP1 (or at least not both.) Perhaps it's a definitional thing, or perhaps there are proofs that were beyond the scope of a first-year grad course, or perhaps the problems that appear to be that hard just keep turning out to be members of the well-known NP-complete set, or perhaps there was something obvious I was just missing... Thanks! Bill Bill Stewart, bill.stewart@pobox.com PGP Fingerprint D454 E202 CBC8 40BF 3C85 B884 0ABE 4639
Hi Bill, On Sat, 4 Nov 2000, Bill Stewart wrote:
Jim, you're misunderstanding the class NP, though you're correct in not holding your breath.
It's not "all problems that can't be solved in polynomial time." It's "all problems that can be solved in polynomial time by a non-deterministic Turing machine." A non-deterministic Turing machine is allowed to guess answers (or at least, to guess a polynomial number of answers). Answers to NP problems can be verified in polynomial time - the hypothetical machine guesses the answer, and verifies it in a polynomially bounded time.
Which is mathematicaly equivalent to having an algorithm that solves the problem directly in polynomial time. One only has to add to the solution time the factor that represents the 'walk time'. Let's consider a prime seive. The numbers are the positive integers and they're a line. So we take the time to check the solution for any given guess and add to it an 'mx+b' factor to represent the time to generate your guesses (in this cases the positive integers). Last time I checked a polynomial plus a polynomial was just another polynomial. We're not talking about absolute magnitudes but rather the relative magnitude differences of the algorithms. How one pronounces 'tomato' isn't relevant. In fact, it is clear that if the algorithm necessary to generate your 'guess' is itself non-polynomial then you've demonstrated the sum (i.e. time to generate guess plus time to check) can't itself be polynomial. In the case where a random number is used to generate a guess then the factor is a simple constant (i.e. '+c') added to the solution time. Iterations by constant value will also consist of the 'loop time' to execute the sum, again a simple constant. So, in most cases the effort needed to generate the guess or walk sequentaly through a state space or through a random proceess is inconsequencial. ____________________________________________________________________ He is able who thinks he is able. Buddha The Armadillo Group ,::////;::-. James Choate Austin, Tx /:'///// ``::>/|/ ravage@ssz.com www.ssz.com .', |||| `/( e\ 512-451-7087 -====~~mm-'`-```-mm --'- --------------------------------------------------------------------
At 08:42 PM 11/4/00 -0600, Jim Choate wrote:
Hi Bill,
On Sat, 4 Nov 2000, Bill Stewart wrote:
Jim, you're misunderstanding the class NP, though you're correct in not holding your breath.
It's not "all problems that can't be solved in polynomial time." It's "all problems that can be solved in polynomial time by a non-deterministic Turing machine." A non-deterministic Turing machine is allowed to guess answers (or at least, to guess a polynomial number of answers). Answers to NP problems can be verified in polynomial time - the hypothetical machine guesses the answer, and verifies it in a polynomially bounded time.
Which is mathematicaly equivalent to having an algorithm that solves the problem directly in polynomial time.
No - it gives you a direct solution that takes exponential time, because there are exponentially many answers the thing could guess, each of which takes a polynomial time to validate. The "then a miracle occurs" step is that the NTM guesses the _correct_ answer - that's why it's hypothetical, rather than real. The reason that it's interesting mathematics is partly that many NP-complete problems, or NP problems in general, are useful or interesting to mathematicians, and sometimes to real people as well (:-), and that it tells us about the complexity of the problem, and about the difficulty of finding answers, and whether to go for optimal solutions to the problems or to look for heuristics that give pretty good answers most of the time. Thanks! Bill Bill Stewart, bill.stewart@pobox.com PGP Fingerprint D454 E202 CBC8 40BF 3C85 B884 0ABE 4639
On Sat, 4 Nov 2000, Bill Stewart wrote:
No - it gives you a direct solution that takes exponential time, because there are exponentially many answers the thing could guess, each of which takes a polynomial time to validate. The "then a miracle occurs" step is that the NTM guesses the _correct_ answer - that's why it's hypothetical, rather than real.
There is no guarantee that a NDTM will guess the correct answer at any stage. The question the NDTM answers over a DTM is "Is there a statistical algorithm that is more efficient than a deterministic one?". The answer seems to be "No". It has been shows for example that a NDTM can address no additional languages over a DTM. But to address the point I was trying to make, Since at each step of a NDTM there are k choices in a space of n, k/n. Assuming the odds of any individual member of the set n being chosen is 1/n. So, if this probablity space grows faster than P then it must be NP. Even if the algorithm used to check the result is P itself. Since the average time to get the correct answer will be k/n there is no significant efficiency over simply steping through 1 to k which would be k/n (assuming the resources per n were 1/n). So, even if you have a P algorithm to test solutions with, there are still issues like 'solution space' that are not limited by the constraints of the solution algorithms P-ness. The problem can be made even more complicated by requiring that no potential answer is ever checked more than once. This requires a string matching operation that depending on syntax could be quite complicated, even NP itself. So, there are possibly three facets to P-ness: 1. Solution Algorithm resource use (effects both DTM & NDTM) 2. Solution space complexity (effects both) 3. String matching resource use (usualy only NDTM because the potential for re-issuing a solution using a RNG is always there since the odds are 1/n for each poll of the RNG.) ____________________________________________________________________ He is able who thinks he is able. Buddha The Armadillo Group ,::////;::-. James Choate Austin, Tx /:'///// ``::>/|/ ravage@ssz.com www.ssz.com .', |||| `/( e\ 512-451-7087 -====~~mm-'`-```-mm --'- --------------------------------------------------------------------
On Sun, 5 Nov 2000, Jim Choate wrote:
On Sat, 4 Nov 2000, Bill Stewart wrote:
No - it gives you a direct solution that takes exponential time, because there are exponentially many answers the thing could guess, each of which takes a polynomial time to validate. The "then a miracle occurs" step is that the NTM guesses the _correct_ answer - that's why it's hypothetical, rather than real.
There is no guarantee that a NDTM will guess the correct answer at any stage. The question the NDTM answers over a DTM is "Is there a statistical algorithm that is more efficient than a deterministic one?".
Um, the definition of "nondeterministic Turing machine" implies such a guarantee. You seem to be thinking of a probabilistic Turing machine - a machine which can flip coins and use the results in an algorithm. They are **not** the same thing.
On Sun, 5 Nov 2000, dmolnar wrote:
There is no guarantee that a NDTM will guess the correct answer at any stage. The question the NDTM answers over a DTM is "Is there a statistical algorithm that is more efficient than a deterministic one?".
Um, the definition of "nondeterministic Turing machine" implies such a guarantee. You seem to be thinking of a probabilistic Turing machine - a machine which can flip coins and use the results in an algorithm. They are **not** the same thing.
??? A NDTM has a stage which if given correct input will cause the result to have one of several states (e.g. A Turing machine that holds both roots of a quadratic at the same time). However, we're right back to 'provably correct' which can't occur, even in principle because there are some legitimate input states that can't be resolved as 'correct'. I wasn't the one who injected 'guessing' in there (which a NDTM doesn't do, ever. It takes the next state only after a 'proof of correctness' step.). When the 'guess' factor is injected then you get a probabilistic NDTM. Which is what I was addressing. As to your assertion that they aren't the same thing, they can certainly be combined. Which was my interpetation of the 'guess an answer and prove it' and 'using a NDTM'. To me that implied a probabilistic NDTM, and that is what I ran with. Within the context of a universal set such as "all Boolean equations" it is clear that the distinction between a NDTM and a DTM is irrelevant. It goes back to the fact that NDTM can be shows to handle no languages that a DTM can resolve. So injecting a NDTM into the mix does nothing to change the results. In addition a NDTM has little worth in a world where we postulate all possible Boolean sentences are resolvable. It, after all, allows a state to be both 1 and 0, clearly contrary to our assertion. What one would want is to show that a DTM was all that is required to resolve any of those Boolean equations. Which can't be done if we accept the NDTM <-> DTM proof. ____________________________________________________________________ He is able who thinks he is able. Buddha The Armadillo Group ,::////;::-. James Choate Austin, Tx /:'///// ``::>/|/ ravage@ssz.com www.ssz.com .', |||| `/( e\ 512-451-7087 -====~~mm-'`-```-mm --'- --------------------------------------------------------------------
At 06:04 PM 11/5/00 -0600, Jim Choate wrote:
On Sun, 5 Nov 2000, dmolnar wrote:
There is no guarantee that a NDTM will guess the correct answer at any stage. The question the NDTM answers over a DTM is "Is there a
statistical
algorithm that is more efficient than a deterministic one?".
Um, the definition of "nondeterministic Turing machine" implies such a guarantee. You seem to be thinking of a probabilistic Turing machine - a machine which can flip coins and use the results in an algorithm. They are **not** the same thing. ???
A NDTM has a stage which if given correct input will cause the result to have one of several states (e.g. A Turing machine that holds both roots of a quadratic at the same time). However, we're right back to 'provably correct' which can't occur, even in principle because there are some legitimate input states that can't be resolved as 'correct'. I wasn't the one who injected 'guessing' in there (which a NDTM doesn't do, ever. It takes the next state only after a 'proof of correctness' step.). When the 'guess' factor is injected then you get a probabilistic NDTM. Which is what I was addressing.
Dave's right, Jim. The NDTM obtains The Right Answer by using a process you could call "guessing" or you could call "an oracle". That's not "Oracle" like "Larry Ellison telling you what you WILL buy next", it's "Oracle" like "Stoned priestess telling you that if you attack today, a great kingdom will fall", and the polynomial-time part is where you crank that through and find out that yes, it's correct. (Unfortunately it's *your* kingdom, but it's correct.) The reason the NDTM is hypothetical is because always guessing the right answer isn't a technology that's really available, unless quantum computers can do that with a sufficently useful precision. (Looks like QCs will at best guess the right answer some of the time, not all the time, and you'll still have to check it.)
In addition a NDTM has little worth in a world where we postulate all possible Boolean sentences are resolvable. It, after all, allows a state to be both 1 and 0, clearly contrary to our assertion. What one would want is to show that a DTM was all that is required to resolve any of those Boolean equations. Which can't be done if we accept the NDTM <-> DTM proof.
The NDTM doesn't allow the state to be both 0 and 1, it tells you which. The DTM part verifies that the answer from the oracle is correct, even though obtained by non-deterministic magic. Thanks! Bill Bill Stewart, bill.stewart@pobox.com PGP Fingerprint D454 E202 CBC8 40BF 3C85 B884 0ABE 4639
On Sun, 5 Nov 2000, Bill Stewart wrote:
Um, the definition of "nondeterministic Turing machine" implies such a guarantee. You seem to be thinking of a probabilistic Turing machine - a machine which can flip coins and use the results in an algorithm. They are **not** the same thing.
Dave's right, Jim. The NDTM obtains The Right Answer by using a process you could call "guessing" or you could call "an oracle". That's not "Oracle" like "Larry Ellison telling you what you WILL buy next", it's "Oracle" like "Stoned priestess telling you that if you attack today, a great kingdom will fall", and the polynomial-time part is where you crank that through and find out that yes, it's correct. (Unfortunately it's *your* kingdom, but it's correct.)
Dave's right, you're not. While it is true a NDTM has a guessing module before that 'guessed' state causes the NDTM to change to the resultant state there is a level of PROOF involved. It is required to prove the answer is right. There is NO magic in an NDTM, it doesn't pull the correct answer out of the air. The distinction at this level between a NDTM and a probabilistic TM is that a PTM doesn't check the result at time of selection but after. It's the algorithm that the Turing machine is running that does the checking. In a NDTM it is the 'guessing module'. The real question related to a NDTM is 'if you have a algorithm that allows you to guess answers and verify them before submission for execution' why are you executing the algorithm? You already know the answer is correct. See: http://www.hissa.nist.gov/dads/HTML/nondetrmtur.html "Definition: A turning machine which has more than one next state for some combination of contents of the current cell and current state. An input is accepted if any move sequence leads to acceptance." In other words you have to have a 'input verifier' that verifies the data is good before the next state(s) are entered. Note this means your verification function can't be NP. This is all really moot since NDTM's don't handle a single language that a DTM can handle, and determining whether all Boolean sentences are valid (irrespective of their actual result) is dealing with a language. It most assuradely has NOTHING to do with the question of how one builds a 'universal sentence parser' that can return a verifiable yes/no as to validity when Godel's says all sentences don't necessarily have a valid result (ie they aren't provably consistent). ____________________________________________________________________ He is able who thinks he is able. Buddha The Armadillo Group ,::////;::-. James Choate Austin, Tx /:'///// ``::>/|/ ravage@ssz.com www.ssz.com .', |||| `/( e\ 512-451-7087 -====~~mm-'`-```-mm --'- --------------------------------------------------------------------
At 07:34 AM 11/6/00 -0600, Jim Choate wrote:
Dave's right, you're not. While it is true a NDTM has a guessing module before that 'guessed' state causes the NDTM to change to the resultant state there is a level of PROOF involved. It is required to prove the answer is right.
There is NO magic in an NDTM, it doesn't pull the correct answer out of the air.
The distinction at this level between a NDTM and a probabilistic TM is that a PTM doesn't check the result at time of selection but after. It's the algorithm that the Turing machine is running that does the checking. In a NDTM it is the 'guessing module'.
The real question related to a NDTM is 'if you have a algorithm that allows you to guess answers and verify them before submission for execution' why are you executing the algorithm? You already know the answer is correct.
See:
It's actually http://hissa.nist.gov/dads/HTML/nondetrmtur.html with no www.
"Definition: A turning machine which has more than one next state for some combination of contents of the current cell and current state. An input is accepted if any move sequence leads to acceptance."
In other words you have to have a 'input verifier' that verifies the data is good before the next state(s) are entered. Note this means your verification function can't be NP.
You're still not getting what the non-deterministic Turing machine does. The problem is structured as a decision-making problem, where an input is "accepted" if the Turing machine halts in an accept state, meaning the set of input is a valid solution to the problem (sometimes leading to ugly convoluted problem definitions if you're really trying to find an optimum rather than a yes-no problem like a Hamiltonian or 3-SAT), or rejected if it halts in a rejection state (where the proposed answer is not a valid solution), or doesn't halt (if it's an annoying problem+input.) "An input is accepted if any move sequence leads to acceptance" means that there's some collection of next states (bits of answer) that leads to the an accept state. How do you know _which_ input value leads to acceptance? That's the magic part. If there are N bits of input, there are 2**N possible move sequences, of which the existence of one correct sequence leads to acceptance.
It most assuradely has NOTHING to do with the question of how one builds a 'universal sentence parser' that can return a verifiable yes/no as to validity when Godel's says all sentences don't necessarily have a valid result (ie they aren't provably consistent).
I don't think anybody's claimed that it has - the Satisfiability problem and the subset 3-SAT problem don't deal with all Boolean problems, just ones with a particular form. Thanks! Bill Bill Stewart, bill.stewart@pobox.com PGP Fingerprint D454 E202 CBC8 40BF 3C85 B884 0ABE 4639
On Mon, 6 Nov 2000, Jim Choate wrote:
The real question related to a NDTM is 'if you have a algorithm that allows you to guess answers and verify them before submission for execution' why are you executing the algorithm? You already know the answer is correct.
The whole idea of NDTM's arises from parallelism - having the correct answer and validating it is equivalent to having all the answers and validating them in parallel, producing one or more correct ones.
This is all really moot since NDTM's don't handle a single language that a DTM can handle, and determining whether all Boolean sentences are valid (irrespective of their actual result) is dealing with a language.
Remember that we are not quantifying over the set of boolean expressions but over the set of possible inputs to a given, finite one. Sampo Syreeni <decoy@iki.fi>, aka decoy, student/math/Helsinki university
participants (12)
-
Bill Stewart -
Carskadden, Rush -
David Honig -
Declan McCullagh -
dmolnar -
Jim Choate -
Jim Choate
-
Jim Choate -
Olav -
petro -
Sampo A Syreeni -
Tim May