HDTenEightyP/NetNews huggingface dataset:
From: jmr@cs.anu.edu.au (Mike Robson)
Newsgroups: comp.theory
Subject: Re: Silence on P=NP
Date: 24 Nov 1992 09:10:24 +1100
Organization: Computer Science Department, ANU, Australia
Distribution: inet
NNTP-Posting-Host: nunki.anu.edu.au

leen@fwi.uva.nl (Leen Torenvliet) writes:

>orourke@sophia.smith.edu (Joseph O'Rourke) writes:

>>The silence on the Swart & Gismondi proof of P=NP is deafening.
>>Will no one venture an opinion?  My knowledge of linear programming
>>is insufficient to the task.

>So is about everybody's it seems. I guess we're all waiting for some

   If noone out there has understood the argument well enough yet to accept it
   or point out a flaw, why don't we pool our efforts to try and elucidate it?

   Here's my comment to start the ball rolling:
      I am trying to understand the Graph Isomorphism paper first since that is the
      basis for the other two; I am fine as far as the end of page 5 where they talk
      about `a larger convex set $C_1$'. This seems to be the definition of $C_1$
      which crops up again significantly but I don't know which `larger convex set'
      it is supposed to be. Anybody like to clarify?


>some polyhedral magician like Lex Schrijver or Laszlo Lovasz
>to wake up and show us the error in the proof (I sure hope there
>is one!). I know that Lex is incommunicado until at least december 1,

   Why?? Apart from the dented pride of all the people who have been convinced
   that P!=NP, wouldn't the world be much more exciting with a O(n^15) or so
   algorithm for SAT than with the knowledge that there wasn't one?


>but I have no knowledge on the whereabouts of prof Lovasz.
>Leen
>-- 
>******************************************************************************
>* Leen Torenvliet                         / His train of thoughts is stil    *
>* University of Amsterdam                 /       boarding at the station.   *
>* Department of Mathematics and Comp. Sci./           (Calvin & Hobbes)      *


Dr J. M. (Mike) Robson,
Department of Computer Science,
Australian National University,
GPO Box 4,
Canberra, ACT 2601,
Australia.

Tel: [61] 6-2494001
Fax: [61] 6-2490010
email: jmr@cs.anu.edu.au

Newsgroups: comp.theory,sci.math,sci.crypt
From: chalmers@bronze.ucs.indiana.edu (David Chalmers)
Subject: Re: Cryptography and P=NP
Organization: Indiana University
Date: Wed, 18 Nov 1992 01:00:10 GMT

These odds just in from Ladbrokes' of London.

P = NP:  5 - 1
P !=NP:  1 - 8 ON

Fermat's conjecture TRUE:  1 - 30 ON
Fermat's conjecture FALSE: 12 - 1

Riemann hypothesis TRUE:  1 - 12 ON
Riemann hypothesis FALSE: 7 - 1

Goldbach's conjecture TRUE:  NO BETS
Goldbach's conjecture FALSE: 1000 - 1

Continuum hypothesis TRUE:  4 - 1
Continuum hypothesis FALSE: 3 - 2
CH neither TRUE nor FALSE:  5 - 2
Neither TRUE nor FALSE that CH either TRUE or FALSE: 8 - 1
Other: 20 - 1

To place bets, call Ladbrokes at 011-44-71-670-0417.  Results to be
determined by God's pronouncement on Dec. 31, 1999, if not settled
by human hand before then.

-- 
Dave Chalmers                            (dave@cogsci.indiana.edu)      
Center for Research on Concepts and Cognition, Indiana University.
"It is not the least charm of a theory that it is refutable."
Newsgroups: comp.theory,sci.math,sci.crypt
From: patl@athena.mit.edu (Patrick J. LoPresti)
Subject: Re: Cryptography and P=NP
Organization: Massachusetts Institute of Technology
Date: Sun, 22 Nov 1992 17:18:47 GMT

(My apologies if this shows up twice.  An earlier reply never appeared
at my site.)

In article <1992Nov17.043640.5525@CSD-NewsHost.Stanford.EDU> pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt) writes:
>
>If one perturbs the definition of primality slightly while retaining
>its basic statistical characteristics (mean, variance) then one can
>actually prove such theorems as "There are infinitely many twin primes"
>and "Every even number > 3 is the sum of two primes" (Goldbach's
>conjecture) without much difficulty.  (I believe "lucky" numbers
>provide an instance of this general principle.)  In these proofs the
>statistical evidence is overwhelming, encouraging one to assign
>extraordinary odds to the failure of Goldbach's conjecture.
>
[stuff deleted]
>
>There is *no* comparable statistical evidence for either P=NP or
>P!=NP.  The evidence to date for P!=NP is that a lot of people have
>looked for a fast algorithm for the generic NP problem and failed.
[more stuff deleted]


Isn't it true that, with respect to a random oracle, P!=NP with
probability 1?

How does this "statistical" evidence differ from your example
regarding the Goldbach conjecture?

- Pat
Newsgroups: comp.theory,sci.math,sci.crypt
From: fahn@Xenon.Stanford.EDU (Paul Fahn)
Subject: Re: Cryptography and P=NP
Organization: Computer Science Department, Stanford University.
Date: Fri, 20 Nov 1992 05:38:16 GMT

In article <1992Nov20.000916.29325@CSD-NewsHost.Stanford.EDU> pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt) writes:
>
>
>Are the following terms acceptable?
>
>
>1.  I, Vaughan Pratt, agree that if P is not equal to NP then I will
>pay you, Chris Long, $1000 on demand.  You agree that if P is equal to
>NP then you will pay me $10,000 on demand.
>

[ other terms of contract ]

>

And now for the important questions: what digital signature method shall 
be used to bind the parties to the contract? What certifying authority
shall be used to verify that the public keys used to sign actually belong
to the individuals in question?
From: sgall+@CS.CMU.EDU (Jiri Sgall)
Newsgroups: comp.theory
Subject: Re: Silence on P=NP
Date: 23 Nov 92 22:41:16 GMT
Article-I.D.: cs.By6xov.Muv.2
Organization: Carnegie Mellon University

In article <1992Nov21.222755.18863@sophia.smith.edu> you write:
>The silence on the Swart & Gismondi proof of P=NP is deafening.
>Will no one venture an opinion?  My knowledge of linear programming
>is insufficient to the task.

To say the least, it's very poorly written. All the informal introductions 
are just a random informal statements about P and NP that could be produced by
any undergradute student who just passed an algorithms class. In a paper on 
such results I would expect at least some nontrivial insight about the methods
used and why should they work. Main results are stated as corollaries, no formal
definitions, etc.

The technical parts introduce precisely some linear programming problem. Then
the argument goes along the lines "this does not work but if you modify it in
the following way, it will". Certainly not a way in which you write a proof in
mathematics. Also things like talking about "a point in the convex hull of a
larger convex set" do not give an impression that the authors have a good
grasp on the subject.

My opinion is that nobody can take this writeup seriously. The papers should be
rewritten completely so that they resemble a formal proof and than someone can
check it. Probably the usual way would be to submit it in a journal or a 
conference like FOCS/STOC.

Of course, if the proof is incorrect (which I believe is the case) then the
best thing to do is to "publish" it as a poorly written unrefereed technical
report - it certainly maximizes the time until the error is discovered.  
(I think the ultimate version of this technique is due Fermat :-)

-- Jiri Sgall
Newsgroups: comp.theory
From: orourke@sophia.smith.edu (Joseph O'Rourke)
Subject: Re: Silence on P=NP
Organization: Smith College, Northampton, MA, US
Date: Mon, 23 Nov 1992 19:39:12 GMT

I received this reply to my posting from David Shallcross at Bellcore:

From davids@bellcore.com Mon Nov 23 12:44:35 1992
Date: Mon, 23 Nov 92 12:43:17 -0500
From: davids@bellcore.com (David Shallcross)

Subject: Re: Silence on P=NP
Newsgroups: comp.theory
Organization: Bellcore, Morristown NJ

In article <1992Nov21.222755.18863@sophia.smith.edu> you write:
>The silence on the Swart & Gismondi proof of P=NP is deafening.
>Will no one venture an opinion?  My knowledge of linear programming
>is insufficient to the task.

Well, I have problems posting from here, but I read through the papers,
and found some fundamental errors.  Basically, he works with the set
of two-sided permutation operators on matrices f(X) = P'XP, where P
is some permutation matrix and P' is the transpose of P.  Since f is
linear in X, we can write this as f(x) = Tx, where x is just X
rearranged into a vector.  He further rearranges T into a vector t, and
(the usually combinatorial optimization - integer programming thing)
gives a system F1 of linear inequalities such that the set of such t's
is the set of integer vectors that satisfy F1.  (Let C1 be the set of
real vectors that satisfy F1.(Gismondi and Swart never actually define
C1.)) What we would like, in order to easily solve lots of NP-hard problems, 
is a polynomial description of the convex hull C0 of such t's.  What they do, 
up to some gaps in their proofs that I cannot quite follow, is give a set C2,
containing C0 and contained in C1, by adding new variables, deducing
new constraints, and projecting the new variables back out.

Their main theorem, which might be correct, is that any point in C2
either lies in C0, or is a convex combination of a point in C1 and a
point in C0.  This is not very surprising, because, for any set A0
contained in any other set A1 (in R^n), the union of A0 with the
interior of A1 also has this property.

The proof of Corollary 1 is clearly invalid, however.  It claims that
if we intersect C2 with some additional linear constraints (that a
graph Ga is mapped to a graph Gb by f) to get C3, and C3 is nonempty, 
then C3 must contain an integer point (and so there must an isomorphism 
between Ga and Gb).  The argument for this is that any point in C3 is the 
convex combination of an integer point in C0 and some other point in C1, 
which is true, but there is no reason that either of those two points
need also satisfy the added linear constraints.

The later two papers more or less act as if C0=C2, in which case all
their wonderous results would be true.  Basically, there are
misunderstandings of the theory of integer programming.

Post this if you like.

Your once-student,
David Shallcross
From: grove@triangle.Berkeley.EDU (Eddie Grove)
Newsgroups: comp.theory
Subject: Re: The P=NP question (was Re: NP Completeness Question
Date: 15 Nov 1992 23:07:47 GMT
Organization: University of California, Berkeley
Distribution: inet
NNTP-Posting-Host: triangle.berkeley.edu

In article <Bxpv45.2I1@watserv1.uwaterloo.ca> nrswart@phonon.uwaterloo.ca (Nicholas R. Swart) writes:
>My attention has been drawn to the discussion about my work on the
>P/NP conundrum.  Let me explain what has been going on.  My Ph.D.
>student Stephen Gismondi and I have for some months been working on
>the graph isomorphism problem and about three months ago I alighted
>on a novel approach which seems to make everything fall into place. 

Could someone give a reference for graph isomorphism being NP-Complete?

I was not aware this had been proved.

It would still be interesting to see a poly-time algorithm for it if
it is not known to be NP-Complete, of course.

Eddie Grove
Newsgroups: comp.theory,comp.lang.functional
From: mwj@rz.uni-jena.de (Johannes Waldmann)
Subject: complexity measures for the lambda calculus?
Organization: Friedrich-Schiller-University Jena, Germany
Date: Mon, 23 Nov 1992 08:24:59 GMT

How can I measure the complexity of computations in the lambda
calculus? Of course I could chose an evaluation strategy,
simulate everything on a Turing machine and apply housekeeping
there. But that's not what I want. I thought of counting the
minimal number of beta reductions (that a given expression needs 
to reach normal form). One could allow parallel reductions (of redexes
not contained in each other)... Has there been work on this field,
is it considered useful? Any hints, pointers to the literature
etc would be appreciated. 

I will summarize if I get enough email responses. --- Johannes.

Newsgroups: comp.theory
From: nrswart@phonon.uwaterloo.ca (Nicholas R. Swart)
Subject: E-mail of E.R. Swart's research reports
Organization: University of Waterloo
Date: Fri, 20 Nov 1992 18:46:43 GMT

To all those who requested e-mail copies of Swart's reports because you could
not reach the host please hang in there. I should be sending out copies by
the end of the day. The problem is that one of the files is too big to pass
through most mailers so it needs to be split into several pieces.

Thanks for waiting.

Nicholas Swart
Dept. of Elec. and Comp. Engineering
University of Waterloo
Waterloo, Ontario
CANADA
N2L 3G1
From: thieloph@crypt3.cs.uni-sb.de (Christoph Thiel)
Newsgroups: comp.theory
Subject: FTP-site of N.R.Swart (P=NP) not reachable
Date: 19 Nov 92 10:33:57 GMT
Organization: Universitaet des Saarlandes, Saarbruecken


Hi,

nrswart@phonon.uwaterloo.ca (Nicholas R. Swart) writes

> The site is:		snowhite.cis.uoguelph.ca
> or equivalently:	131.104.48.1
>
> The files are located in the directory /pub/comptheory and are given below:
>
> -r--r--r--  1 ftp      system     413515 Nov 17 10:16 isomorph.ps
> -r--r--r--  1 ftp      system     127949 Nov 17 10:18 isomorph.ps.Z
> -r--r--r--  1 ftp      system      85803 Nov 17 10:15 neqls1.ps
> -r--r--r--  1 ftp      system      28316 Nov 17 10:19 neqls1.ps.Z
> -r--r--r--  1 ftp      system      61792 Nov 17 10:16 tsp.ps
> -r--r--r--  1 ftp      system      22287 Nov 17 10:19 tsp.ps.Z


I have some problems with the given FTP-adress. When I try it i get the
message

              ftp: connect: Network is unreachable.

So could someone send me another adress or the files per e-mail.

My e-mail adress is:

        thieloph@cs.uni-sb.de


Thanks in advance.

Newsgroups: comp.theory
From: lowry@watson.ibm.com (Andy Lowry)
Subject: Re: Cryptography and P=NP
Date: Tue, 17 Nov 1992 18:19:06 GMT
Disclaimer: This posting represents the poster's views, not necessarily those of IBM
	<Nov.16.16.59.47.1992.6436@remus.rutgers.edu>
Organization: IBM T.J. Watson Research Center
Followup-To: comp.theory

In article <Nov.16.16.59.47.1992.6436@remus.rutgers.edu> clong@remus.rutgers.edu (Chris Long) writes:
 > Both are unproven, but there are *very* strong reasons for
 > believing them to be true.  So strong that anyone who believes
 > otherwise must be either ignorant or a crackpot.

Who better to make a breakthrough discovery than an ignorant crackpot?
--
Andy Lowry, lowry@watson.ibm.com, (914) 784-7925
IBM Research, P.O. Box 704, Yorktown Heights, NY  10598
From: mccolm@darwin.math.usf.edu. (Gregory McColm)
Newsgroups: comp.theory
Subject: Re: Human Computers....
Date: 14 Nov 92 20:04:01 GMT
Article-I.D.: ariel.1992Nov14.200401.24530
Organization: Univ. of South Florida, Math Department

In article <BxF6zI.GF@cantua.canterbury.ac.nz> wft@math.canterbury.ac.nz (Bill Taylor) writes:
>|>  I'm looking for examples in fiction literature
>|> of super sophisticated communicative computers a la HAL.
>
>The classic example, very like HAL, is the computer in 
>"The Moon Is a Harsh Mistress", by Robert Heinlein.
>

Most communicative computer books are really part of the 
old GOLEM genre (a Medieval Jewish tale of an alchemist 
who created an artificial man who ran amok).  Some golems 
are good (eg, Rink-a-tink of Oz, Isaac Asimov's Robot series), 
but most are Frankenstein types.  Robots have drifted out 
of fashion, replaced in part by androids and cyborgs, and 
new larege machines have appeared in science fiction.  Some, 
like Colossus (The Forbin Project---I forget the author), HAL, 
Fred Saberhagen's Berserkers, and virtually every computer 
of Norton's, are up to no good.  Others, like Heinlein's MYCROFT
(The Moon is a Harsh Mistress is one of his less bad books) 
and Poul Anderson's MUDDLEHEAD (Trader to the Stars series) 
wear white hats.

While the literature is huge (just go to a bookstore and 
look at the robot/computer books by Simak, Norton, Niven, etc), 
almost all these works were by computer illiterates and 
their computers are quite unreal.  I have heard that there is 
a new "virtual reality" genre in SF which may be more realistic, 
but I haven't read any.  Its probably like TRON.  Your best 
bet may be something like the Andromeda novels of Fred Hoyle, 
who is an eminent if eccentric astrophysicist who writes SF, 
including SF with computers.  Poul Anderson, Arthur C Clarke, 
and Isaac Asimov are all scientifically literate, so you can 
try them.

>
>Incidentally, this book is worth reading, not just for the relationship
>between the hero and the computer, but also for the marvellous sense of
>realism engendered by the thickness of the peripheral details and comments;
>a thickness sadly lacking in most science fiction.


Don't go to SF for characterization.  SF writers are much 
weaker than, say, murder mystery writers on relations between 
characters.  (There are a few good writers, like CJ Cherryh, 
David Brin, etc.)  Heinlein is quite awful in this respect, but 
most of his fans forgive him because of his imaginative 
short stories.  Detail thickness a la Thomas Clancy can be 
best found in books by people like Michael Crichton.

-----Greg McColm
--
SHAMELESS AD:  Math PhDs in Analysis, Discrete Math./Th. of Comp., Num. Anal., 
Prob., are invited to apply to the Math. Dept. of Univ. of S. Florida for 
research/teaching positions that may be available: contact K. L. Pothoven at 
mathdept@math.usf.edu. Deadline 2/1/93. USF is a politically correct employer.
Newsgroups: comp.theory
Newsgroups: comp.theory
From: neto@cs.toronto.edu (David Neto)
Subject: Question about Gismondi and Swart, CIS92-D4
Organization: Department of Computer Science, University of Toronto
Date: 19 Nov 92 21:59:36 GMT

I've been reading the paper, and can't come up with a proof for a
particular step.  On the top of page 10, it is claimed that any
solution t to F3 is a linear combination of the q_i's, where the
coeffiecients alpha_i's add up to 1.  That is, t is in the space
spanned by all q_i's.  My question, which may be trivial (perhaps I
lack the necessary background in linear programming), is: how can we
guarantee that this solution is somewhere in this vector space?  Is it
the case that the s,t, and u constraints guarantee this, but I can't
find the reason?

Thanks,
David Neto
neto@cs.toronto.edu
Newsgroups: comp.theory,sci.math,sci.crypt
From: pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt)
Subject: Re: Cryptography and P=NP
Organization: Computer Science Department,  Stanford University.
Date: Fri, 20 Nov 1992 00:09:16 GMT


In article <Nov.19.01.26.05.1992.11158@remus.rutgers.edu> clong@remus.rutgers.edu (Chris Long) writes:
>In article <1992Nov17.043640.5525@CSD-NewsHost.Stanford.EDU>,
>  Vaughan Pratt writes:
>
>> Moshe Vardi has made P=NP his odds-on favorite,
>
>I'll bet $10000 to his $1000.
>
>> I admit I'm a conservative old coward in sticking to even odds.
>
>Same for you.
>-- 
>Chris Long, 265 Old York Rd., Bridgewater, NJ  08807-2618


Are the following terms acceptable?


1.  I, Vaughan Pratt, agree that if P is not equal to NP then I will
pay you, Chris Long, $1000 on demand.  You agree that if P is equal to
NP then you will pay me $10,000 on demand.

2.  The question of whether P equals NP is widely considered to be open
today.  The parties will consider the status of this question changed
from "open" to "settled" when more than half, and no less than 20, of
the authorities openly stating an opinion agree that the question has
been settled, and also agree on the answer.

3.  The sole test for authority is membership on any past or present
ACM STOC or IEEE FOCS program committee, excluding the parties to this
agreement.

4.  This agreement shall lapse on December 31, 1995 / 2000 (delete one).

5.  Each party is entitled to have this agreement reviewed by an
attorney of their choice.

6.  This agreement is to be interpreted by and construed according to
the laws of the State of Nevada, and any action or other proceedings
pursuant to the agreement shall be brought in Reno, Nevada.

7.  Any such action, whether in equity, tort, or contract, shall be
submitted to binding arbitration according to the commercial
arbitration rules of the American Arbitration Association.  The
prevailing party shall be entitled to an award of reasonable attorney's
fees and costs.

Would you prefer 1995 or 2000 as the year of expiration?
-- 
Vaughan Pratt	  		A fallacy is worth a thousand steps.
Newsgroups: comp.theory
From: leen@fwi.uva.nl (Leen Torenvliet)
Subject: Re: Silence on P=NP
Organization: FWI, University of Amsterdam
Date: Mon, 23 Nov 1992 09:11:36 GMT

orourke@sophia.smith.edu (Joseph O'Rourke) writes:

>The silence on the Swart & Gismondi proof of P=NP is deafening.
>Will no one venture an opinion?  My knowledge of linear programming
>is insufficient to the task.

So is about everybody's it seems. I guess we're all waiting for some
some polyhedral magician like Lex Schrijver or Laszlo Lovasz
to wake up and show us the error in the proof (I sure hope there
is one!). I know that Lex is incommunicado until at least december 1,
but I have no knowledge on the whereabouts of prof Lovasz.
Leen
-- 
******************************************************************************
* Leen Torenvliet                         / His train of thoughts is stil    *
* University of Amsterdam                 /       boarding at the station.   *
* Department of Mathematics and Comp. Sci./           (Calvin & Hobbes)      *
Newsgroups: comp.theory,sci.math,sci.crypt
From: nrswart@phonon.uwaterloo.ca (Nicholas R. Swart)
Subject: Re: ***** Research Reports by Prof. E.R. Swart - now available *****
Organization: University of Waterloo
Date: Tue, 17 Nov 1992 18:16:17 GMT


The research reports by Prof. Swart on the P/NP issue are now available
via anonymous FTP.

The site is:		snowhite.cis.uoguelph.ca
or equivalently:	131.104.48.1

The files are located in the directory /pub/comptheory and are given below:

-r--r--r--  1 ftp      system     413515 Nov 17 10:16 isomorph.ps
-r--r--r--  1 ftp      system     127949 Nov 17 10:18 isomorph.ps.Z
-r--r--r--  1 ftp      system      85803 Nov 17 10:15 neqls1.ps
-r--r--r--  1 ftp      system      28316 Nov 17 10:19 neqls1.ps.Z
-r--r--r--  1 ftp      system      61792 Nov 17 10:16 tsp.ps
-r--r--r--  1 ftp      system      22287 Nov 17 10:19 tsp.ps.Z

Both compressed versions (.Z) and uncompressed versions are available. They
are all in postscript format.

Please let me know if you have any problems.

Nicholas R. Swart
Dept. of Elec. and Comp. Engineering
University of Waterloo
Waterloo, Ontario
CANADA
N2L 3G1
Newsgroups: comp.theory
From: chaudhus@rolls.cs.rpi.edu (Samit Chaudhuri)
Subject: Re: The P=NP question (was Re: NP Completeness Question
Organization: Rensselaer Polytechnic Institute, Troy, NY
Date: Wed, 18 Nov 1992 22:38:30 GMT

The Research Report CIS92-D4 by Gismondi, S.J. and Swart E. R. that gives a
polynomial time algorithm to the graph isomorphism problem doesn't make a 
point very clear:

In Theorem 1 it proves that every extreme point of the formulation F3 
corresponds to,
  a) An extreme point of C0, the convex hull of all the doubly 
     stochastic Q matrices (Note that they do not necessarily represent an 
     isomorphism between the graphs under consideration. The additional 
     constraints Ta = b are required to ensure that.), or
  b) A convex combination of an extreme point of C0 and a point in 
     C1 (the feasible region of formulation F1)

In Corollary 1 it says that the same is also valid for the formulation F4 
(F4 satisfies all the constraints of F3 together with the additional 
constraint Ta = b). Would the new constraint necessarily preserve the 
properties of F3 ?

It didn't seem obvious to me, could anyone explain ?
Newsgroups: comp.theory
From: cmoraga@dcc.uchile.cl (MORAGA ORELLANA CORNELIO SEGUNDO)
Subject: statistical analysis for BTREE performance
Originator: cmoraga@dcc.uchile.cl
Date: Tue, 24 Nov 1992 01:54:44 GMT
Organization: Universidad de Chile, Depto. de Ciencias de la Computacion

  Where I can find a comprensive statistical analysis (exact) for B-trees. 
  Average  behavior during searching, insertion ??

  Thanks in advance

  cmoraga@dcc.uchile.cl
Newsgroups: comp.theory