P does not equal NP - a logical approach
in [Theory]
|
From: jeffrubard on 17 Jun 2008 16:02 Hey, do you guys want to hear a good one? The structure of Satisfiability shows that NP-complete problems cannot be simulated in P without oracles. Here's how: n propositional atoms can have 2^n different sets of truth-values. For an n-atom statement (it could be in CNF, although it makes no difference) any one of those 2^n lines in its "truth-table" could satisfy it: and since each of those permutations is independent of the others by definition (no truth value of an atom can depend in any way on the truth-value of any others), the upper bound on a deterministic search for a satisfying set of truth-values must be 2^n. Oracles work (or don't work) by reducing the truth-functional complexity under consideration to 2^n-1: the mathematically inclined among you will notice this is ever so slightly less than the cardinality of the power set. But that's a story for another time.
From: Hans H�ttel on 20 Jun 2008 16:13 In article <5d2c3780-9a38-407c-8c1b-4d0a2551f636(a)s21g2000prm.googlegroups.com>, jeffrubard(a)gmail.com wrote: > Hey, do you guys want to hear a good one? The structure of > Satisfiability shows that NP-complete problems cannot be simulated in > P without oracles. Here's how: n propositional atoms can have 2^n > different sets of truth-values. For an n-atom statement (it could be > in CNF, although it makes no difference) any one of those 2^n lines in > its "truth-table" could satisfy it: and since each of those > permutations is independent of the others by definition (no truth > value of an atom can depend in any way on the truth-value of any > others), the upper bound on a deterministic search for a satisfying > set of truth-values must be 2^n. > > Oracles work (or don't work) by reducing the truth-functional > complexity under consideration to 2^n-1: the mathematically inclined > among you will notice this is ever so slightly less than the > cardinality of the power set. But that's a story for another time. How does this line of reasoning (or rather, hand-waving) prove that there cannot be a deterministic polynomial-time Turing machine that is a decider for SAT? There is a serious lack of precision in the above. In particular, I am worried by the sloppy use of - the notion of truth assignments being "independent", - and the notion of an oracle Normally, we would define an oracle of language L as the assumption that the characteristic function of L is constant-time computable. Moreover, it is not clear how one would define independence of assignments. One can easily come up with a propositional formula F with two truth assignments A_1 and A_2 such that A_1 [ X = 0 ] (A_1 where X is now set to false) and A_2 [ X = 0 ] are both models of F, whereas neither A_1 [ X = 1 ] nor A_2 [ X = 1 ] will be. Any formula of the form "F' and (not x)" where F' is a tautology, will do. Hans -- Hans H�ttel Department of Computer Science Aalborg University Denmark
From: jeffrubard on 23 Jun 2008 22:46 On Jun 20, 1:13 pm, Hans Hüttel <hanshut...(a)mac.com> wrote: > In article > <5d2c3780-9a38-407c-8c1b-4d0a2551f...(a)s21g2000prm.googlegroups.com>, > > > > jeffrub...(a)gmail.com wrote: > > Hey, do you guys want to hear a good one? The structure of > > Satisfiability shows that NP-complete problems cannot be simulated in > > P without oracles. Here's how: n propositional atoms can have 2^n > > different sets of truth-values. For an n-atom statement (it could be > > in CNF, although it makes no difference) any one of those 2^n lines in > > its "truth-table" could satisfy it: and since each of those > > permutations is independent of the others by definition (no truth > > value of an atom can depend in any way on the truth-value of any > > others), the upper bound on a deterministic search for a satisfying > > set of truth-values must be 2^n. > > > Oracles work (or don't work) by reducing the truth-functional > > complexity under consideration to 2^n-1: the mathematically inclined > > among you will notice this is ever so slightly less than the > > cardinality of the power set. But that's a story for another time. > > How does this line of reasoning (or rather, hand-waving) prove that > there cannot be a deterministic polynomial-time Turing machine that is a > decider for SAT? It's total hand-waving; as stated it doesn't advance recursion theory one bit, because it doesn't sufficiently increase our conceptual purchase on the powers of automata. However, it's a fact of propositional logic that someone who did want to examine the P and NP problem will have to deal with. > There is a serious lack of precision in the above. In particular, I am > worried by the sloppy use of > > - the notion of truth assignments being "independent", Okay, here's a way you can think about this: if the truth-value of an atom was dependent on the assignments of the other atoms in the sentences, its truth-value would be a truth-function of the other atoms, and so we would not be talking about an "atom". > - and the notion of an oracle I don't really know too much about oracles; the notion employed here is analogical to proper oracles for a Turing Machine, but I would be surprised to learn you could not formulate the concepts more exactly. It's kind of irrelevant to the question of what obtains for unrelativized TMs, I just threw it in to suggest how the oracle computations might be related to the phenomenon I'm describing for non-oracle computations. > Normally, we would define an oracle of language L as the assumption that > the characteristic function of L is constant-time computable. > > Moreover, it is not clear how one would define independence of > assignments. One can easily come up with a propositional formula F with > two truth assignments A_1 and A_2 such that > > A_1 [ X = 0 ] (A_1 where X is now set to false) and > A_2 [ X = 0 ] > > are both models of F, whereas neither A_1 [ X = 1 ] nor A_2 [ X = 1 ] > will be. Any formula of the form > > "F' and (not x)" > > where F' is a tautology, will do. No, what I am talking about is the assignment of truth-values to atoms like "x", and it's really basic propositional logic that an atomic formula can be either true or false. Obviously the values of propositional formulae containing x are truth-functionally ("compositionally") dependent on its assigned value, but once you reach the atomic level there can be no systematic determination. That's not what happens in a nondeterministic algorithm for SAT -- you "sweep through" the logical form of the sentence based on previous choices -- but if you want something less "hand-wavy" I'll tell you I really think that a "universal nondeterministic polynomial automaton" capable of solving SAT for sentences of arbitrary length is going to have to have a transition function that steps through the power set of the natural numbers (since the set of all truth-functions in subsentences of sentences of n variables is the power set of n), and doing this in polynomial time essentially relies on the ability of the nondeterministic algorithm to have multi-choice transitions: simulating the "UNPA" deterministically is going to take exponential time, since the cardinality of the power set is 2^n and the deterministic automaton has to handle that one step at a time. Jeff Rubard
From: Hans H�ttel on 24 Jun 2008 16:23 In article <829f284f-139f-45ec-86be-db1d8af13f85(a)q27g2000prf.googlegroups.com>, jeffrubard(a)gmail.com wrote: > No, what I am talking about is the assignment of truth-values > to atoms like "x", and it's really basic propositional logic > that an atomic formula can be either true or false. Obviously > the values of propositional formulae containing x are > truth-functionally ("compositionally") dependent on its > assigned value, but once you reach the atomic level > there can be no systematic determination. > > That's not what happens in a nondeterministic algorithm > for SAT -- you "sweep through" the logical form of the > sentence based on previous choices -- but if you want > something less "hand-wavy" I'll tell you I really think > that a "universal nondeterministic polynomial > automaton" capable of solving SAT for sentences > of arbitrary length is going to have to have a > transition function that steps through the power set > of the natural numbers (since the set of all truth-functions > in subsentences of sentences of n variables is the power > set of n), and doing this in polynomial time essentially > relies on the ability of the nondeterministic algorithm > to have multi-choice transitions: simulating the "UNPA" > deterministically is going to take exponential time, > since the cardinality of the power set is 2^n and the > deterministic automaton has to handle that one step > at a time. Why is the above not just a more elaborate formulation of the following well-known informal justification of the belief that P is not equal to NP: "A decider for SAT has to examine all possible truth-value assignments. If it does not, we may leave out a satisfying one, and then the algorithm will not be a decider. But an exhaustive search requires exponential time." ?? -- Hans H�ttel Department of Computer Science Aalborg University Denmark
From: jeffrubard on 25 Jun 2008 10:56
On Jun 24, 1:23 pm, Hans Hüttel <hanshut...(a)mac.com> wrote: > In article > <829f284f-139f-45ec-86be-db1d8af13...(a)q27g2000prf.googlegroups.com>, > > > > jeffrub...(a)gmail.com wrote: > > No, what I am talking about is the assignment of truth-values > > to atoms like "x", and it's really basic propositional logic > > that an atomic formula can be either true or false. Obviously > > the values of propositional formulae containing x are > > truth-functionally ("compositionally") dependent on its > > assigned value, but once you reach the atomic level > > there can be no systematic determination. > > > That's not what happens in a nondeterministic algorithm > > for SAT -- you "sweep through" the logical form of the > > sentence based on previous choices -- but if you want > > something less "hand-wavy" I'll tell you I really think > > that a "universal nondeterministic polynomial > > automaton" capable of solving SAT for sentences > > of arbitrary length is going to have to have a > > transition function that steps through the power set > > of the natural numbers (since the set of all truth-functions > > in subsentences of sentences of n variables is the power > > set of n), and doing this in polynomial time essentially > > relies on the ability of the nondeterministic algorithm > > to have multi-choice transitions: simulating the "UNPA" > > deterministically is going to take exponential time, > > since the cardinality of the power set is 2^n and the > > deterministic automaton has to handle that one step > > at a time. > > Why is the above not just a more elaborate formulation of the following > well-known informal justification of the belief that P is not equal to > NP: > > "A decider for SAT has to examine all possible truth-value assignments. > If it does not, we may leave out a satisfying one, and then the > algorithm will not be a decider. But an exhaustive search requires > exponential time." > At my level of computer science knowledge, I'm excited about coming up with "well-known informal justifications", rather than incoherent garbage (although you graciously tried that tack first). What is different about what I am saying is that I am putting teeth in it by connecting it to the power set via the set of truth-functions, and conjecturing that the problem is essentially the problem of the cardinality of the power set (and the oracle solution or non-solution the problem of the continuum hypothesis, i.e. oracles that work assume the continuum hypothesis in that 2^(n-1) has the same cardinality as n, and oracles that do not work deny it by having the largest cardinality before 2^n be different from n). Jeff Rubard |