Issue with notion of "Necessarily False"
240 views
Skip to first unread message
j mark inman
Mar 17, 2012, 1:43:54 AM3/17/12
to Polynomial Algorithm for 3-SAT
Hi Angela,
I did look over your paper after you commented to my post on Prof.
Lipton's site "Gödel's lost letter and P=NP". Unfortunately, I do not
believe you have a deterministic polynomial time algorithm for 3-SAT.
In fact, I have code for a very similar algorithm that I made a few
years ago that I determined is NOT deterministic for the same reason
your solution does not seem deterministic. The main problem with your
algorithm is the concept of "necessarily false". You see, as your
algorithm runs, it makes a decision to factor the literals in only one
way, however, there are several ways in which these clauses could be
factored, thus several different ways for the choice of "necessarily
false" to be made. Because this choice is not exhaustive, you will
have a situation where a false negative could result in high backbone
formulas and you will receive a wrong answer at least some of the
time. To exhaust this search, would, unfortunately, make the algorithm
exponential and no longer in P.
That said, on a personal note, I commend your efforts. I think it is
wonderful to have such an innovative and creative algorithm, even if
there is some issue with it, because it could lead to further
developments and understanding. I am not someone who believes as most
of the establishment does, I share your sentiment that P=NP. I have a
proof of my own, although I took a very different route after
discovering my algorithm had a hole in it. In essence, I was able to
generate a set which is both countable and has a complete metric
simultaneously, something not possible according to Cantor and the
current view in computer science and mathematics- and as such unifies
first and second logic which directly implies P=PSPACE. It is right
there in plain site that this set exists, so even though it might take
many years for the community to accept it, I believe it will be
accepted in my lifetime.
Cheers and best to you,
/jmark
I did look over your paper after you commented to my post on Prof.
Lipton's site "Gödel's lost letter and P=NP". Unfortunately, I do not
believe you have a deterministic polynomial time algorithm for 3-SAT.
In fact, I have code for a very similar algorithm that I made a few
years ago that I determined is NOT deterministic for the same reason
your solution does not seem deterministic. The main problem with your
algorithm is the concept of "necessarily false". You see, as your
algorithm runs, it makes a decision to factor the literals in only one
way, however, there are several ways in which these clauses could be
factored, thus several different ways for the choice of "necessarily
false" to be made. Because this choice is not exhaustive, you will
have a situation where a false negative could result in high backbone
formulas and you will receive a wrong answer at least some of the
time. To exhaust this search, would, unfortunately, make the algorithm
exponential and no longer in P.
That said, on a personal note, I commend your efforts. I think it is
wonderful to have such an innovative and creative algorithm, even if
there is some issue with it, because it could lead to further
developments and understanding. I am not someone who believes as most
of the establishment does, I share your sentiment that P=NP. I have a
proof of my own, although I took a very different route after
discovering my algorithm had a hole in it. In essence, I was able to
generate a set which is both countable and has a complete metric
simultaneously, something not possible according to Cantor and the
current view in computer science and mathematics- and as such unifies
first and second logic which directly implies P=PSPACE. It is right
there in plain site that this set exists, so even though it might take
many years for the community to accept it, I believe it will be
accepted in my lifetime.
Cheers and best to you,
/jmark
M Angela Weiss
Mar 19, 2012, 7:45:56 PM3/19/12
to Polynomial Algorithm for 3-SAT
Hello, Mark!
Thanks again for your letter! An important point, indeed. I can
factorize by choosing labels in several different ways but the fact
is that independently of the partition, the formula $PSI$ is
satisfiable iff its partitioned version is satisfiable (Proposition
2.5). The partition does not matter!
If there is a gap, it is in theorems 2.12 and 2.13, but I've checked
the proofs and they are working well (until someone points the
mistake!)
I really believe that P=NP and the answer will not require a
sophisticated tool. I do not believe my tool is "the golden key" to
open the answer, but I believe it will be an useful tool.
I would love to read your manuscript! It seems interesting! Is it
available on line?
Take care,
angela
Thanks again for your letter! An important point, indeed. I can
factorize by choosing labels in several different ways but the fact
is that independently of the partition, the formula $PSI$ is
satisfiable iff its partitioned version is satisfiable (Proposition
2.5). The partition does not matter!
If there is a gap, it is in theorems 2.12 and 2.13, but I've checked
the proofs and they are working well (until someone points the
mistake!)
I really believe that P=NP and the answer will not require a
sophisticated tool. I do not believe my tool is "the golden key" to
open the answer, but I believe it will be an useful tool.
I would love to read your manuscript! It seems interesting! Is it
available on line?
Take care,
angela
j mark inman
Mar 20, 2012, 3:23:10 AM3/20/12
to Polynomial Algorithm for 3-SAT
Thank you for the kind response.
I hope you are well and that my comments are helpful to you.
I'm wondering now about a specific aspect of Proposition 2.5. In this
proof, the claim is, "Ψ is satisfiable iff a partitioned version of it
is satisfiable." But at no point in the proof itself do you use the
words "satisfiable" - instead, you move forward to prove that for all
Ψ' that is unsatisfiable, then all Ψ is unsatisfiable and that for all
Ψ that is unsatisfiable, then all Ψ' is unsatisfiable. However,
proving the inverse of a statement is not proof of the statement...
You end the proof of 2.5 with "Our claim follows on noticing that at
each step of factorization, Ψ′ is replaced by an equivalent formula."
Just stating that there is an equivalent formula upon each step of
factorization is no evidence in it for me to believe it. In fact, I do
believe that Ψ′ implies a certificate that may be different from a
certificate Ψ′' where some different partition (e.g., instead of using
the first litteral in the first clause as the factor, you use some
randome litteral, or every 2nd litteral, et al.) is used to determine
a completely different set of "Necessarily False" such that the
partition giving Ψ′ is unsat and the partition giving Ψ′' is sat. I
believe so, because you assume the falseness of a literal before fully
factoring the clause, thus in the subsequent factorings, you change
the truth value of the formula as you factor! Notice how NecFls occurs
before some repetition of itself. in the algorithm before You would
need some "superposition" principle, similar to a qubit, in order to
remedy this problem polynomially.
There does seem to be good news here, however, and that is that 2SAT
is polynomial time solvable with the backtracking algorithm. Maybe
there is some relationship between the 3SAT Ψ and any given
factorization of Ψ in 2SAT such that there is a pseudo-polynomial time
algorithm for 3SAT. I don't think one currently exists, yet the
knapsack problem indicates that one can exist, and this might be worth
pursuing.
--
But let's assume for a moment that you are correct in 2.5, that my
assessment is wrong, and you are able to rewrite 2.5 such that you can
prove Ψ is satisfiable iff a partitioned version of it is satisfiable.
The following red flags on the algorithm are, if not fatal flaws,
worrying to anyone reading the paper for peer review:
1. Your algorithm requires search (and multiple iterative repeated
procedures). Please watch the 2006 lecture of M. Sipser speaking at
the Clay institute about the subject of search in an NP-complete
problem and why we think search is not necessary if there is a
solution to an NP-complete problem.
http://www.youtube.com/watch?v=msp2y_Y5MLE
2. Your claim that your algorithm is simple, isn't true. While
qualitative in nature, this red flag shows up around page 6 or 7, and
is at that moment, your paper is an extra complicated piece to
decipher. I had a much easier time reading Mike and Ike's Quantum
computation book... ;-)
3. You do not provide pseudocode or a working language code version of
your algorithm. It shouldn't be difficult to do this if your algorithm
works, yet it is missing. This would let other's test your claim.
4. You do not provide any benchmark certificates. Here is a list of
benchmark problems, so that when you do have a working algorithm, you
can test it: http://www.cs.ubc.ca/~hoos/SATLIB/benchm.html
-------------
I would be happy to provide you with a copy of my paper. I temporarily
self-published a draft copy on scribd about a year ago, but I have
since taken it off the internet because my new draft is going to be
significantly more powerful and has corrected a few errors and
clarified a few points. I expect to have this draft completed soon and
I plan to submit it to arXiv.org. I will let you know as soon as it is
available!
Cheers,
/jmark
I hope you are well and that my comments are helpful to you.
I'm wondering now about a specific aspect of Proposition 2.5. In this
proof, the claim is, "Ψ is satisfiable iff a partitioned version of it
is satisfiable." But at no point in the proof itself do you use the
words "satisfiable" - instead, you move forward to prove that for all
Ψ' that is unsatisfiable, then all Ψ is unsatisfiable and that for all
Ψ that is unsatisfiable, then all Ψ' is unsatisfiable. However,
proving the inverse of a statement is not proof of the statement...
You end the proof of 2.5 with "Our claim follows on noticing that at
each step of factorization, Ψ′ is replaced by an equivalent formula."
Just stating that there is an equivalent formula upon each step of
factorization is no evidence in it for me to believe it. In fact, I do
believe that Ψ′ implies a certificate that may be different from a
certificate Ψ′' where some different partition (e.g., instead of using
the first litteral in the first clause as the factor, you use some
randome litteral, or every 2nd litteral, et al.) is used to determine
a completely different set of "Necessarily False" such that the
partition giving Ψ′ is unsat and the partition giving Ψ′' is sat. I
believe so, because you assume the falseness of a literal before fully
factoring the clause, thus in the subsequent factorings, you change
the truth value of the formula as you factor! Notice how NecFls occurs
before some repetition of itself. in the algorithm before You would
need some "superposition" principle, similar to a qubit, in order to
remedy this problem polynomially.
There does seem to be good news here, however, and that is that 2SAT
is polynomial time solvable with the backtracking algorithm. Maybe
there is some relationship between the 3SAT Ψ and any given
factorization of Ψ in 2SAT such that there is a pseudo-polynomial time
algorithm for 3SAT. I don't think one currently exists, yet the
knapsack problem indicates that one can exist, and this might be worth
pursuing.
--
But let's assume for a moment that you are correct in 2.5, that my
assessment is wrong, and you are able to rewrite 2.5 such that you can
prove Ψ is satisfiable iff a partitioned version of it is satisfiable.
The following red flags on the algorithm are, if not fatal flaws,
worrying to anyone reading the paper for peer review:
1. Your algorithm requires search (and multiple iterative repeated
procedures). Please watch the 2006 lecture of M. Sipser speaking at
the Clay institute about the subject of search in an NP-complete
problem and why we think search is not necessary if there is a
solution to an NP-complete problem.
http://www.youtube.com/watch?v=msp2y_Y5MLE
2. Your claim that your algorithm is simple, isn't true. While
qualitative in nature, this red flag shows up around page 6 or 7, and
is at that moment, your paper is an extra complicated piece to
decipher. I had a much easier time reading Mike and Ike's Quantum
computation book... ;-)
3. You do not provide pseudocode or a working language code version of
your algorithm. It shouldn't be difficult to do this if your algorithm
works, yet it is missing. This would let other's test your claim.
4. You do not provide any benchmark certificates. Here is a list of
benchmark problems, so that when you do have a working algorithm, you
can test it: http://www.cs.ubc.ca/~hoos/SATLIB/benchm.html
-------------
I would be happy to provide you with a copy of my paper. I temporarily
self-published a draft copy on scribd about a year ago, but I have
since taken it off the internet because my new draft is going to be
significantly more powerful and has corrected a few errors and
clarified a few points. I expect to have this draft completed soon and
I plan to submit it to arXiv.org. I will let you know as soon as it is
available!
Cheers,
/jmark
M Angela Weiss
Mar 29, 2012, 12:58:25 PM3/29/12
to Polynomial Algorithm for 3-SAT
Thank you for your feedback. I needed a feekback. Your feedback is
clever, right to the point. THANKS!.
I wrote my points above, item by item. More than that, I posted a new
version of 2.5 in the page.
take care,
angela
-------------------------------------------------------------
-------------------------------------------------------------
Well, I believe that if there is a flaw, it will be found in Theorems
2.12
and 2.13. No gaps before that! See, no matter the way I make a
partition, the idea is:
PSI is satisfiable if and only if PSI' (partitioned version) is
satisfiable. Equivalently, PSI is unsatisfiable (not satisfiable) if
and only if PSI' is unsatisfiable.
If you accepted that PSI is in such a way that if $l$ is a literal of
$PSI,
then its negation, $NOT l$, is a literal of PSI as well, then, a
partition of PSI starts with a PARTITION (a set of pairwise disjoint
sets) of the clauses of PSI, $\{D_{l_{1}},...,D_{l_{k}\}$, $l$ ranging
a set of literals of PSI (I named it label, but think about a
partition of the set of clauses of PSI) $D_{l}$ a set of clauses of
PSI that contain $l$ (I do not mean that $D_{l}$ contains the set of
ALL clauses of PSI that contain $l$!). We have,
PSI= /\{C\in D_{l_{1}}} /\ ... /\ /\{C\in D_{l_{k}}}=
(l_{1}\/ S_{l_{1}}}) /\ ... /\ (l_{k}\/ S_{l_{k}}})
(/\ stands for AND, \/ stands for OR, = stands for equivalent)
Where /\{C\in D_{l_{i}}}= C_{1l_{1}}/\.../\C_{sl_{1}} is a
conjunction,
say, $s$ clauses, all of them containing $l_{i}$ among its literals,
so, factoring,
/\{C\in D_{l_{i}}}= C_{1l_{1}}/\.../\C_{sl_{1}} = l_{i}\/ S_{l_{i}}}
(I wrote it in a neater .pdf, 2.5 in More Words. It is posted in my
page).
-------------------------------------------------------------
-------------------------------------------------------------
>
> But let's assume for a moment that you are correct in 2.5, that my
> assessment is wrong, and you are able to rewrite 2.5 such that you can
> prove Ψ is satisfiable iff a partitioned version of it is satisfiable.
> The following red flags on the algorithm are, if not fatal flaws,
> worrying to anyone reading the paper for peer review:
>
> 1. Your algorithm requires search (and multiple iterative repeated
> procedures). Please watch the 2006 lecture of M. Sipser speaking at
> the Clay institute about the subject of search in an NP-complete
> problem and why we think search is not necessary if there is a
> solution to an NP-complete problem.
>
> http://www.youtube.com/watch?v=msp2y_Y5MLE
>
-------------------------------------------------------------
-------------------------------------------------------------
Clever! Very nice, indeed!
The idea is that, if I am right I can tell you polysize if a formula
is satisfiable or unsatisfiable. But I cannot tell you which are the
valuations to make PSI true.
Sipser Lecture is just wonderful! I keep my focus on the
problem. Really, let us suppose that my manuscript is "The sorcerer
stone". Even so, jumping from the (theoretical) mathematician answer
to a applied scientist answer, I think it is a big jump (say 50 years
long?)
-------------------------------------------------------------
-------------------------------------------------------------
-------------------------------------------------------------
Oh, boy! I will never use the magic words: "It is quite simple!" It
never is that simple and the magic never works, spite my will! My
apologies!
-------------------------------------------------------------
-------------------------------------------------------------
> 3. You do not provide pseudocode or a working language code version of
> your algorithm. It shouldn't be difficult to do this if your algorithm
> works, yet it is missing. This would let other's test your claim.
>
> 4. You do not provide any benchmark certificates. Here is a list of
> benchmark problems, so that when you do have a working algorithm, you
> can test it:http://www.cs.ubc.ca/~hoos/SATLIB/benchm.html
>
> -------------
> -------------------------------------------------------------
-------------------------------------------------------------
It took me some time to decide writing the Algorithm. I felt not that
sure I will perform the task of writing a simple code. I can write
algorithms, but I never wrote a program, at least such a big
one. I was divided in between the decision of writing the algorithm or
just the manuscript. My doubts were raised by the possibility of,
maybe if I do not write clearly, people will associate my weak side (I
am not a
programmer) to the idea that the manuscript is weak or totally wrong,
which is not true.
The algorithms will be posted in my page. Anyone, accordingly to
her(his) wishes can "translate" it into a nice language, e.g, lisp or
shemme.
-------------------------------------------------------------
-------------------------------------------------------------
-------------------------------------------------------------
Thanks!
-------------------------------------------------------------
-------------------------------------------------------------
clever, right to the point. THANKS!.
I wrote my points above, item by item. More than that, I posted a new
version of 2.5 in the page.
take care,
angela
-------------------------------------------------------------
Well, I believe that if there is a flaw, it will be found in Theorems
2.12
and 2.13. No gaps before that! See, no matter the way I make a
partition, the idea is:
PSI is satisfiable if and only if PSI' (partitioned version) is
satisfiable. Equivalently, PSI is unsatisfiable (not satisfiable) if
and only if PSI' is unsatisfiable.
If you accepted that PSI is in such a way that if $l$ is a literal of
$PSI,
then its negation, $NOT l$, is a literal of PSI as well, then, a
partition of PSI starts with a PARTITION (a set of pairwise disjoint
sets) of the clauses of PSI, $\{D_{l_{1}},...,D_{l_{k}\}$, $l$ ranging
a set of literals of PSI (I named it label, but think about a
partition of the set of clauses of PSI) $D_{l}$ a set of clauses of
PSI that contain $l$ (I do not mean that $D_{l}$ contains the set of
ALL clauses of PSI that contain $l$!). We have,
PSI= /\{C\in D_{l_{1}}} /\ ... /\ /\{C\in D_{l_{k}}}=
(l_{1}\/ S_{l_{1}}}) /\ ... /\ (l_{k}\/ S_{l_{k}}})
(/\ stands for AND, \/ stands for OR, = stands for equivalent)
Where /\{C\in D_{l_{i}}}= C_{1l_{1}}/\.../\C_{sl_{1}} is a
conjunction,
say, $s$ clauses, all of them containing $l_{i}$ among its literals,
so, factoring,
/\{C\in D_{l_{i}}}= C_{1l_{1}}/\.../\C_{sl_{1}} = l_{i}\/ S_{l_{i}}}
(I wrote it in a neater .pdf, 2.5 in More Words. It is posted in my
page).
-------------------------------------------------------------
-------------------------------------------------------------
>
> But let's assume for a moment that you are correct in 2.5, that my
> assessment is wrong, and you are able to rewrite 2.5 such that you can
> prove Ψ is satisfiable iff a partitioned version of it is satisfiable.
> The following red flags on the algorithm are, if not fatal flaws,
> worrying to anyone reading the paper for peer review:
>
> 1. Your algorithm requires search (and multiple iterative repeated
> procedures). Please watch the 2006 lecture of M. Sipser speaking at
> the Clay institute about the subject of search in an NP-complete
> problem and why we think search is not necessary if there is a
> solution to an NP-complete problem.
>
> http://www.youtube.com/watch?v=msp2y_Y5MLE
>
-------------------------------------------------------------
Clever! Very nice, indeed!
The idea is that, if I am right I can tell you polysize if a formula
is satisfiable or unsatisfiable. But I cannot tell you which are the
valuations to make PSI true.
Sipser Lecture is just wonderful! I keep my focus on the
problem. Really, let us suppose that my manuscript is "The sorcerer
stone". Even so, jumping from the (theoretical) mathematician answer
to a applied scientist answer, I think it is a big jump (say 50 years
long?)
-------------------------------------------------------------
-------------------------------------------------------------
> 2. Your claim that your algorithm is simple, isn't true. While
> qualitative in nature, this red flag shows up around page 6 or 7, and
> is at that moment, your paper is an extra complicated piece to
> decipher. I had a much easier time reading Mike and Ike's Quantum
> computation book... ;-)
> -------------------------------------------------------------
> qualitative in nature, this red flag shows up around page 6 or 7, and
> is at that moment, your paper is an extra complicated piece to
> decipher. I had a much easier time reading Mike and Ike's Quantum
> computation book... ;-)
-------------------------------------------------------------
Oh, boy! I will never use the magic words: "It is quite simple!" It
never is that simple and the magic never works, spite my will! My
apologies!
-------------------------------------------------------------
-------------------------------------------------------------
> 3. You do not provide pseudocode or a working language code version of
> your algorithm. It shouldn't be difficult to do this if your algorithm
> works, yet it is missing. This would let other's test your claim.
>
> 4. You do not provide any benchmark certificates. Here is a list of
> benchmark problems, so that when you do have a working algorithm, you
> can test it:http://www.cs.ubc.ca/~hoos/SATLIB/benchm.html
>
> -------------
-------------------------------------------------------------
It took me some time to decide writing the Algorithm. I felt not that
sure I will perform the task of writing a simple code. I can write
algorithms, but I never wrote a program, at least such a big
one. I was divided in between the decision of writing the algorithm or
just the manuscript. My doubts were raised by the possibility of,
maybe if I do not write clearly, people will associate my weak side (I
am not a
programmer) to the idea that the manuscript is weak or totally wrong,
which is not true.
The algorithms will be posted in my page. Anyone, accordingly to
her(his) wishes can "translate" it into a nice language, e.g, lisp or
shemme.
-------------------------------------------------------------
-------------------------------------------------------------
> I would be happy to provide you with a copy of my paper. I temporarily
> self-published a draft copy on scribd about a year ago, but I have
> since taken it off the internet because my new draft is going to be
> significantly more powerful and has corrected a few errors and
> clarified a few points. I expect to have this draft completed soon and
> I plan to submit it to arXiv.org. I will let you know as soon as it is
> available!
>
> Cheers,
>
-------------------------------------------------------------
> self-published a draft copy on scribd about a year ago, but I have
> since taken it off the internet because my new draft is going to be
> significantly more powerful and has corrected a few errors and
> clarified a few points. I expect to have this draft completed soon and
> I plan to submit it to arXiv.org. I will let you know as soon as it is
> available!
>
> Cheers,
>
-------------------------------------------------------------
Thanks!
-------------------------------------------------------------
-------------------------------------------------------------
Reply all
Reply to author
Forward
0 new messages