USATODAY.com - Niche competitors crowd into MySpace http://www.usatoday.com/tech/news/2006-07-31-myspace-over_x.htm CNN.com - Cell phones: A new tool in the...
Blogger Jailed After Defying Court Orders - New York Times http://www.nytimes.com/2006/08/02/us/02protest.html?_r=1&ref=technology&oref=slogin USATODAY.com -...
Hi, Here is a proof that P=NP by induction. Let us number all SAT instances. Now let us define an algorithm A[X], which when given an instance I computes...
David Lantsman
davidlan@...
Aug 5, 2006 11:19 am
12251
... You need to start with an explicit algorithm to determine the number corresponding to a SAT instance in your encoding. Otherwise I can give a simpler...
Hi, ... determine the number ... encoding. Yes, I think that you are right. It is not possible to number them. Their cardinality is probably like the real...
David Lantsman
davidlan@...
Aug 5, 2006 12:23 pm
12253
Here is a proof that P=NP by induction. Let us define an algorithm A[X], which when given a 3SAT instance I, the size of which (number of clauses) is no more...
David Lantsman
davidlan@...
Aug 5, 2006 1:02 pm
12254
Hello, ... No. All instances of SAT are -finite- sequences over -finite- alphabet [*] so their cardinality is the same as the cardinality of the set of natural...
... constant time; i.e. there ... found the answer in time ... algorithm A[I] works in time C. Yes, it does, using induction. Induction is the key. If...
David Lantsman
davidlan@...
Aug 5, 2006 1:23 pm
12256
... Wrong. It's just too easy to mis-use something that -looks- like induction and hope it'll work. In fact, your construction didn't make use of the induction...
Dear Peter, ... induction hypothesis As you have said yourself, the fact that I did not make use of the induction hypothesis does not change anything because I...
Well David, it seems there is some confusion as to how the induction works and what it can or cannot prove. So, let me try to clarify it a bit... ... Yes, I...
Peter - you are right. Thanks. Again regarding the cardinality of SAT instances. You said that they are over a finite alphabet - but you can have any number of...
David Lantsman
davidlan@...
Aug 6, 2006 2:38 am
12261
On Sunday, August 06, 2006 7:57 AM David Lantsman wrote in theory- edge: DL>> So is it possible that the statement "P!=NP" is a very unique statement in our...
Hi, ... Once again, one needs to be very careful about the tiny details. The intuitive description of SAT problem as answering all the questions of the form...
... formulas with variables ... there are only countably ... Even if the set of variables is countable, but infinite, there are at least as many instances as ...
David Lantsman
davidlan@...
Aug 7, 2006 3:14 am
12266
Friends, I found some of the very useful (free) magazines on net.. For computer, telecom, electronics, feed & beverage, business, call center, offshoring and...
... Umm... how are you going to represent the number 1/3 (=0.333333...)? What about square root of 2? And what about pi? The problem is that the representation...
Hollywood Games People Play http://www.businessweek.com/technology/content/aug2006/tc20060804_618481.htm?campaign_id=bier_tcuts Tip Sheet: CEO Guide to...
Having problems with message search?
Fill out this form to ensure your group is one of the first to be migrated to the new message search system.
