HDTenEightyP/NetNews huggingface dataset:
From: pef@dcs.qmw.ac.uk (Panayotis Fouliras; TA PhD)
Newsgroups: sci.math,comp.theory
Subject: Re: NP Completeness Question
Date: 13 Nov 92 11:40:38 GMT
Organization: Computer Science Dept, QMW, University of London

In <BxMu2J.2JD@watserv1.uwaterloo.ca> nrswart@phonon.uwaterloo.ca (Nicholas R. Swart) writes:

>In article <1dpkkeINNad2@mizar.usc.edu> tunal@mizar.usc.edu (Tamer Unal) writes:
>...
>>My guess is that 1. is in of polynomial complexity while 2.
>>is NP-complete.
>>
>>Any pointers, references, appreciated.
>>
>Professor E.R. Swart of the Computer Science Department at the University
>of Guelph, has recently developed a polynomial-sized linear programing
>formulation of the graph isomorphism problem and he has been able to show
>that with minor modifications, this same formulation can be used to solve
>the Hamilton tour, clique and other subgraph isomorphism problems.

>This proves that P=NP and all NP-complete and all other NP problems thus
>have polynomial time algorithms.

>So to answer your question, 1 and 2 are probably both polynomial.

>Nicholas
>Dept. of Elec. and Comp. Engineering
>University of Waterloo
>Waterloo, Ontario
>CANADA
>N2L 3G1

If this is so, could you please provide with a
pointer/reference to a publication, where the above is
described (preferably not Technical Reports, which are more
diffcult to access)?

Thank you in advance

Panayotis
--
UUCP:      pef@qmw-dcs.uucp  | Computer Science Dept    | "H Rwmania
Internet:  pef@dcs.qmw.ac.uk | QMW University of London |  kai an
JANET:     pef@uk.ac.qmw.dcs | Mile End Road            |  eperasen,
Voice:     +44 71 975 5220   | London E1 4NS            |  anthei kai
FAX:       +44 81 980 6533   |                          |  ferei kai
Cellphone: Too expensive to fit                            allon"
Newsgroups: sci.math
From: gjm11@cus.cam.ac.uk (G.J. McCaughan)
Subject: Re: Axioms of set theory, infinity and R. Rucker
Organization: U of Cambridge, England
Date: Fri, 6 Nov 1992 18:24:47 GMT

In article <1992Nov6.133138.16642@prl.philips.nl> schiller@prl.philips.nl (schiller c) writes:
>
>
>In the definition of a set, one axiom is the existence
>of infinity. It is one of the usual Zermelo-Fraenkel
>axioms.
>
>Reading the book "infinity and the mind" by Rudy Rucker
>(by the way, it is delighting), one learns that
>there are many different types of infinities which
>exist, of different "size". 
>
>Which of these is the infinity specified in the
>axioms of set theory ? Is it important to decide this
>question ? Does this have any effect on set theory ?

The usual axiom of infinity guarantees a countably infinite set; that is,
one the same size as the set of natural numbers.

With the axiom of choice, every infinite set contains a countable set, so
an axiom saying "There is an infinite set" without being so specific about
just what sort of infinite set there was would be OK. Without the axiom of
choice, there is a difference; and it is useful to have a guarantee that
there is a set that can function as a set of natural numbers, for instance.

With the axiom of choice, the natural numbers are as small as an infinite
set can be. Without it, that's still almost true but it's not always possible
to compare the sizes of infinite sets.

I hope this helps.

-- 
Gareth McCaughan     Dept. of Pure Mathematics & Mathematical Statistics,
gjm11@cus.cam.ac.uk  Cambridge University, England.    [Research student]
From: goddard@NeXTwork.Rose-Hulman.Edu (Bart E. Goddard)
Newsgroups: sci.math
Subject: Re: who should teach calculus?
Date: 12 Nov 1992 14:02:02 GMT
Organization: Computer Science Department at Rose-Hulman
Reply-To: goddard@NeXTwork.Rose-Hulman.Edu (Bart E. Goddard)
NNTP-Posting-Host: g214-1.nextwork.rose-hulman.edu

In article <1992Nov10.223300.19016@murdoch.acc.Virginia.EDU>  
tep2j@amsun.apma.Virginia.EDU (Todd E. Peterson) writes:
> I am interested in hearing net.opinions on the following:
> 
> Is it a good or bad practice to use non-mathematicians to
> teach mathematics courses?  

It's good, if you want the course to end in two days...

bart
Newsgroups: sci.math
From: pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt)
Subject: Re: Erdos number
Organization: Computer Science Department,  Stanford University.
Date: Fri, 13 Nov 1992 07:18:15 GMT

In article <EIJKHOUT.92Nov12213622@cupid.cs.utk.edu> eijkhout@cupid.cs.utk.edu (Victor Eijkhout) writes:
>>> So, are there any non-mathematicians with such a number? 
>
>With me the case is the other way around: my Erd"os number is three
>through an electronics engineer who co-authored with Richard Guy.
>His two is probably a lower bound, unless Erd"os himself wrote
>about non-mathematical subject.

Two counterexamples:

1. On a long train journey Erdos struck up a conversation with the
conductor, who ended up as a coauthor.

2. Don Knuth is a computer scientist.
-- 
Vaughan Pratt	  		A fallacy is worth a thousand steps.
Newsgroups: sci.math
From: tokero@bode.eng.ohio-state.edu (Onur Toker)
Subject: Help wanted about root finding algorithms
Organization: The Ohio State University Dept of Electrical Engineering
Date: Sat, 7 Nov 1992 17:39:21 GMT

Does anybody know very good root finding algorithms such as ones used
in MATLAB or other numerical analysis tools. I know the book called
'Numerical Recipies in ***' but I want much faster, and reliable 
algorithms. If you know any references please let me know.

Thanks

TOKER

e-address=tokero@ee.eng.ohio-state.edu
Newsgroups: sci.math
From: tim@gold.iss.nus.sg (tim poston)
Subject: Re: Trivial! (was: Re: Help X^2 == Y mod N)
Reply-To: tim@iss.nus.sg (tim poston)
Organization: Institute of Systems Science, NUS, Singapore
Date: Thu, 5 Nov 1992 06:12:36 GMT

In article <1992Nov5.001930.24516@galois.mit.edu> jbaez@riesz.mit.edu (John C. Baez) writes:
>Igor Rivin writes:
>>Just because you know how to do it doesn't mean it is trivial. 
>
>I don't know about you, but anything *I* understand completely is
>trivial by definition.  

No mathematics is trivial;
the trivium was grammar and rhetoric and I forget what;
roughly, the mediaeval equivalent of a Bachelor's.

Mathematics (along with harmony and two others I forget)
was part of the quadrivium;
equivalent of that peculiar US invention,
the PhD.

If you didn't study it in the trivium,
it's not trivial,
                     QED.


(actually I hadn't stated what was demonstrandum,
 but how do you make those neat proof-end tombstones in ASCII?)


Tim 


___________________________________________________________________
                On a General Election
         That cursed power that stands on Privilege
         (And goes with women, and champagne, and bridge)
         Broke, and Democracy resumed her reign
         (Which goes with bridge, and women, and champagne).
                                                 Hilaire Belloc
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Newsgroups: sci.math
From: sl25@cus.cam.ac.uk (Steve Linton)
Subject: Re: Office Hours
Organization: U of Cambridge, England
Distribution: sci
Date: Thu, 12 Nov 1992 22:33:07 GMT

Basically, look for another department. In my (limited) experience departmental
cultures vary between two poles:

At one end you have the sort of department you describe, where (I guess) people
come in at 9, work on their problems/teaching until 5, punctuated by seminars and
so on and then go home to their families. Other common symptoms are closed office
doors, limited coffee/tea hours, and an obsession with status and politics. 

At the other exterem is the sort of departmentI guess you are looking for, where
informal (sometimes crazily) so discussions, usaually of mathematics, can be
found 24 hours a day, office doors are usually open, but everyone lives in the
common room anyway, the coffee pot never runs dry, and nobody can remeber who got
landed with being head of department this year.

Most places lie between these extremes, and the most sociable department will
still have people who like to get on with their own work quietly, while mavericks
like you turn up even in the most insurance-company-like departments.

Factors that can help include unsuitable, inefficient and/or over-crowded offices
(force people together); a lot of visitors, preferably foreign, who have nothing
else to do locally except mathematics; a good departmental secretary and probably
lots of others.

I know of one case of a department being converted, almost overnight, which
hinged on a maverick visitor who refused to stand on ceremony for anything and a
couple of graduate students who got to drinking beer and talking mathematics with
him. The professor had the flexibility to  realise that good work was actually
being done, though in a most unGerman way (this was in Germany) and the
department is now a major centre for the subject, attracts huge numbers of
visitors and some of the best graduate students around and is one of my
own favourite places  to visit. Their building is desperately over-crowded, but
this only helps.

In your own situation, you have a problem with both a formal department and a
lack of a mathematical common interest, which may be insuperable.

Good Luck


		Steve Linton

PS I am over-generalising wildly from the 8 or 10 departments I have any
experiance of, and everything I say should be taken with a large pinch of salt.
(That's what USENET is for isn't it)
Newsgroups: sci.math
From: prener@watson.ibm.com (Dan Prener)
Subject: Re: group theory for HS students
Date: Sun, 8 Nov 1992 00:12:13 GMT
Distribution: sci
Disclaimer: This posting represents the poster's views, not necessarily those of IBM
	<04VSB5M6@cc.swarthmore.edu>
Organization: IBM T.J. Watson Research Center, Hawthorne, New York

In article <04VSB5M6@cc.swarthmore.edu> rbrown1@cc.swarthmore.edu (Randolph Gregory Brown) writes:

   [ ... ]

>            Math teaching suffers from a chronalogical problem -- just
>because calculus was invented (discovered if you really want) before
>group theory doesn't mean that it should be learned beforehand.

The conventional order of the mathematics curriculum isn't based on the
history of mathematics.  It is a compromise to accomodate a heterogeneous
audience.

If math courses had the training of mathematicians as their only purpose,
then the ordering would be more like what you suggest.  On the other hand,
there is an urgent need to provide, say, physics students, with calculus
at an even faster rate than is usually done.

So the compromise gives everyone a quick jolt of calculus, then gets on
with other stuff.  Real analysis courses are an explicit recognition that
that first jolt of calculus wasn't really part of the orderly training
of mathematicians.
--
                                   Dan Prener (prener@watson.ibm.com)
Newsgroups: sci.math
From: cyeomans@ms.uky.edu (Charles Yeomans)
Subject: Re: Erdos number
Date: Thu, 12 Nov 1992 15:41:55 GMT
Organization: University Of Kentucky, Dept. of Math Sciences

In article <1992Nov11.001750.12213@mailhost.ocs.mq.edu.au> gerry@macadam.mpce.mq.edu.au (Gerry Myerson) writes:
>
>
>In article <1992Nov2.231234.19251@smds.com>, sammy@smds.com (Samuel Murphy) writes:
>> 
>> In article <1992Oct29.170517.7780@email.tuwien.ac.at> zach@csdec1.tuwien.ac.at writes:
>> >In article <petersen.720366033@rzcspc1>, petersen@rzcspc1.informatik.uni-hamburg.de (Holger Petersen) writes:
>
>[definition of Erdos number, deleted]
>
>> So, are there any non-mathematicians with such a number? 
>
>Yes. John Clough, Professor of Music at SUNY, Buffalo, wrote a paper in the 
>Monthly with me some years ago, thereby acquiring an Erdos number of 4. 
>
>> What is the largest number known?
>> 
Perhaps we could get the AMS to make an Erdos number computer available via 
e-math.ams.com.

Charles Yeomans
cyeomans@ms.uky.edu
yeomans@austin.onu.edu
From: clong@remus.rutgers.edu (Chris Long)
Newsgroups: sci.math
Subject: A Set Problem
Date: 4 Nov 92 21:33:08 GMT
Organization: Rutgers Univ., New Brunswick, N.J.


Show that there exists two infinite sets of non-negative integers
such that every positive integer may be written uniquely as the sum
of two integers, one from each set.  Do there exist three infinite
sets of non-negative integers such that every positive integer may
be written uniquely as the sum of three integers, one from each set?
-- 
Chris Long, 265 Old York Rd., Bridgewater, NJ  08807-2618
From: dik@cwi.nl (Dik T. Winter)
Newsgroups: sci.math
Subject: Re: Mercator Projection
Date: 10 Nov 92 10:23:02 GMT
Organization: CWI, Amsterdam

In article <1992Nov10.060543.25580@CSD-NewsHost.Stanford.EDU> pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt) writes:
 > In article <7868@charon.cwi.nl> dik@cwi.nl (Dik T. Winter) writes:
Some nonsense.
 > >EB is right.
 > 
 > I think you're alone on this one.  Alan Paeth mentioned in an earlier
 > post that this was a common but incorrect assumption.
 > 
Right, I was wrong as is the EB.  Must have been a bad night.
-- 
dik t. winter, cwi, kruislaan 413, 1098 sj  amsterdam, nederland
home: bovenover 215, 1025 jn  amsterdam, nederland; e-mail: dik@cwi.nl
From: chrisman@purina.berkeley.edu (chrisman)
Newsgroups: sci.math
Subject: Re: Teaching Calculus
Date: 9 Nov 1992 20:45:43 GMT
Organization: U.C. Berkeley Math. Department.
Distribution: usa
NNTP-Posting-Host: purina.berkeley.edu

In article <1992Nov9.005052.3384@news.cs.indiana.edu> johnl@spinner.cs.indiana.edu (John Lacey) writes:
:Benjamin.J.Tilly@dartmouth.edu (Benjamin J. Tilly) writes:
:
:>I know that many people feel that using limits to teach calculus
:>confuses the students and it might be better to have an alternate
:>approach. How about the following one which uses continuous functions
:>to replace limits?
:
:I, for one, feel that it is not limits but how they are taught that is
:confusing.  I have yet to see a teacher that doesn't totally confuse
:people about when you can substitute the limit in, and when you cannot.
                           ~~~~~~~~~~~~~~~~~~~~~~~

You mean, when you can claim that  lim (x->a) [f(x)]  is equal to f(a)?
But this is exactly the notion of continuity, which Benjamin wants to teach.


Newsgroups: sci.math
From: len@schur.math.nwu.edu (Len Evens)
Subject: Re: who should teach calculus?
Organization: Dept of Math, Northwestern Univ
Date: Thu, 12 Nov 1992 14:33:32 GMT

In article <1992Nov10.223300.19016@murdoch.acc.Virginia.EDU> tep2j@amsun.apma.Virginia.EDU (Todd E. Peterson) writes:
>I am interested in hearing net.opinions on the following:
>
>Is it a good or bad practice to use non-mathematicians to
>teach mathematics courses?  In particular, what about the
>use of engineering faculty to teach engineering calculus
>courses, and other applied mathematics courses?
>
>                             ________________
>Todd E Peterson              |\  /\  /\  /\  /|     phone 804 982 2909
>Dept of Applied Math         |_\/__\/__\/__\/_|     fax   804 982 2972
>Thornton Hall, UVa           | /\  /\  /\  /\ |     email tep2j@virginia.edu
>Charlottesville VA 22903     |/__\/__\/__\/__\|


There are several issues to be discussed here.

   In principle, qualified
engineering faculty should be allowed to teach calculus and other mathematics
courses.   Often such people are very well prepared and their day to day
work keeps them invovled with serious mathematics.  However, the teaching
of calculus must remain the responsibility of mathematics departments,
and it is such departments who should have final say on who in any department
is qualified.   By the way, I would add that in cases where there are
separate `pure' and `applied' mathematics departments, they should
share this responsiblity jointly.

	Another important point, however, is that the teaching of
calculus to some extent justifies the hiring of mathematicians so it
indirectly supports mathematics as an enterprise.  This is a selfish
point of view, but if engineering (or any other departments) have
excess faculty not needed for their own teaching needs, it suggest that
those departments are over staffed.   In times of financial difficulty
it may be acceptable to use such `excess capacity' for other purposes,
but in the long run resources should be diverted where they are needed.


Leonard Evens      len@math.nwu.edu      708-491-5537
Dept. of Mathematics, Northwestern Univ., Evanston, IL 60208
Newsgroups: sci.math
From: hrubin@mentor.cc.purdue.edu (Herman Rubin)
Subject: Re: Axioms of set theory, infinity and R. Rucker
Organization: Purdue University Statistics Department
Date: Sat, 7 Nov 1992 02:07:37 GMT

In article <1992Nov6.182447.25955@infodev.cam.ac.uk> gjm11@cus.cam.ac.uk (G.J. McCaughan) writes:
>In article <1992Nov6.133138.16642@prl.philips.nl> schiller@prl.philips.nl (schiller c) writes:


>>In the definition of a set, one axiom is the existence
>>of infinity. It is one of the usual Zermelo-Fraenkel
>>axioms.

>>Reading the book "infinity and the mind" by Rudy Rucker
>>(by the way, it is delighting), one learns that
>>there are many different types of infinities which
>>exist, of different "size". 

>>Which of these is the infinity specified in the
>>axioms of set theory ? Is it important to decide this
>>question ? Does this have any effect on set theory ?

>The usual axiom of infinity guarantees a countably infinite set; that is,
>one the same size as the set of natural numbers.

>With the axiom of choice, every infinite set contains a countable set, so
>an axiom saying "There is an infinite set" without being so specific about
>just what sort of infinite set there was would be OK. Without the axiom of
>choice, there is a difference; and it is useful to have a guarantee that
>there is a set that can function as a set of natural numbers, for instance.

>With the axiom of choice, the natural numbers are as small as an infinite
>set can be. Without it, that's still almost true but it's not always possible
>to compare the sizes of infinite sets.

However, one does not need the axiom of choice.  The ordinal numbers, defined
as in Godel, for example, do not need that axiom for the definition.  Then
for any set x, the Hartogs function of x, which is the set of all ordinal
numbers of size smaller than or equal to x, is an ordinal number not of such
a size.  This must contain the natural numbers if x is not a finite set, so
any kind of infinite set is adequate.

It is not possible to have a smaller infinite set than the natural numbers,
but it is possible to have infinite sets of a size incomparable to that of
the natural numbers.
-- 
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
Phone: (317)494-6054
hrubin@snap.stat.purdue.edu (Internet, bitnet)  
{purdue,pur-ee}!snap.stat!hrubin(UUCP)
Newsgroups: sci.math
From: levine@symcom.math.uiuc.edu (Lenore Levine)
Subject: Curious about Julia Set
Organization: University of Illinois at Urbana
Date: Sat, 7 Nov 1992 18:40:45 GMT

Does the Julia set of a complex function always have (two-dimensional)
measure zero?

Just curious...
From: mac@abacus.concordia.ca ( JOHN MCKAY )
Newsgroups: sci.math
Subject: Permutation groups
Date: 5 Nov 92 12:11:21 GMT
Organization: Cicma, Concordia University, Montreal, Quebec
Originator: mac@abacus


We are in the process of classifying and tabulating properties of
transitive permutation groups of small degree (up to 15 at present).
Our primary application is to Galois computations.
There are over 600 groups and so we have space restrictions - within
these, we are happy to consider including invariants of use to others.
Currently we intend to include: order, permutation generators,
minimality, parity, systems of imprimitivity, frequency of cycle shapes
of elements, smaller degree incarnations, number of conjugacy classes of
elements, lengths of orbits of r-sets and r-sequences of points
(for r at least to degree/2).
Any further suggestions are welcome.  A good naming system is needed.
Please email suggestions for inclusion to    mckay@vax2.concordia.ca 
Thank you. 


-- 
Thought for the day: Odd order groups are even.

Newsgroups: sci.math,news.answers
From: kibo@world.std.com (James "Kibo" Parry)
Subject: Re: three sided coin
Organization: Two rooms filled with typography, in downtown Boston
Date: Thu, 5 Nov 1992 03:53:46 GMT

In article <1d6ti8INN976@CAUCHY.MATH.YALE.EDU> ferenbaugh-charles@math.yale.edu (Charles Ferenbaugh) writes:
>
>so you've shortchanged Perot.  
           ^^^^^

It's not nice to make puns about the guy just because he has to measure
his height in centimeters instead of inches.

>PS.  Pardon my ignorance - who or what is Kibo, anyway?

Two feet taller than Perot.

								-- K.

Newsgroups: sci.math
From: bs@gauss.mitre.org (Robert D. Silverman)
Subject: Re: Generalizing Prime Numbers
Organization: Research Computer Facility, MITRE Corporation, Bedford, MA
Date: Mon, 9 Nov 1992 12:22:11 GMT

In article <1992Nov8.191948.14975@athena.mit.edu> frisch1@athena.mit.edu (Jonathan Katz) writes:
>I was wondering if anyone knows about any method of generalizing the concept of
>prime numbers to the complex plane.
>Is there more than one way to generalize it?
>Any help on the would be appreciated.
 
Without discussing what is known as "generalized primes", one can indeed
extend the concept of 'prime' [or more specifically, ideal with prime 
norm] to the complex plane.

Let's stick to the simplest case; the ring of Gaussian integers.
Note that if one adjoins i = sqrt(-1) to Z, then primes of the form
4N+1, are no longer prime.  For example consider 5.It can now be
written as (2+i) (2-i).  The rational integer 5 (or ordinary integer) 5
has norm 25 in this ring. The norm of each of (2+i) and (2-i) is 5,
So we have written an ordinary prime as the product of complex numbers,
each of which has prime norm.

In general, if one has a monic polynomial of degree d, with coefficients
in Z, one can form a field by adjoining a root(s) of this polynomial
to Q. This field has a integral basis, among which one can find 'primes'
in the sense you mean. 

If one considers the ordinary primes you know and ask: which have factorizations
in this field, the answer is that it is governed by what is known as the
higher reciprocity laws (the same way quadratic reciprocity works for
quadratic fields). 

This is a very brief, oversimplified introduction. Hope it helps.

--
Bob Silverman
These are my opinions and not MITRE's.
Mitre Corporation, Bedford, MA 01730
"You can lead a horse's ass to knowledge, but you can't make him think"
Xref: sparky sci.math:14791 sci.physics:18717
From: hougen@focus.csl.uiuc.edu (Darrell Roy Hougen)
Newsgroups: sci.math,sci.physics
Subject: Re: Three-sided coin
Date: 11 Nov 92 20:44:11 GMT
Distribution: usa
Organization: Center for Reliable and High-Performance Computing, University of Illinois at Urbana-Champaign
NNTP-Posting-Host: focus.csl.uiuc.edu

chrisman@sizzlean.berkeley.edu (chrisman) writes:

% In article <1992Nov11.045329.21895@galois.mit.edu> jbaez@riesz.mit.edu (John C. Baez) writes:
% .In article <1992Nov10.051702.24907@CSD-NewsHost.Stanford.EDU> pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt) writes:
% .>In article <1992Nov10.032643.10467@galois.mit.edu> jbaez@riesz.mit.edu (John C. Baez) writes:
% .>>My best shot at answer invoked an idea from stat mech, namely,
% .>>equipartition.  This says that the solution occurs when the *energy* of
% .>>standing upright equals the energy of lying on edge.  Guess this means
% .>>the radius should equal half the thickness of the coin, or if you
% .>>prefer, the diameter should equal the thickness.
% .>
% .>Wouldn't that give the coin a 1/2 chance of landing on its edge rather
% .>than 1/3?
% .
% .Well, not according the stat mech principle that equal-energy states
% .have an equal chance of being occupied.  Since there are 3 states of
% .equal energy (heads, tails, edge), each should have a 1/3 chance of
% .being occupied.  That is, if the reasoning was right here.  However, I
% .no longer think it is.

[ Response deleted ]

The problem here seems to be the definition of state.  When the coin
is lying on its edge, it can roll to a new position without changing
its state.  The area of the edge is 2*pi*r^2 whereas the area of each
side is only pi*r^2, ie., the area of the edge is twice that of the
either side.  Hence, I would doubt that the probability of the coin
staying on edge is equal to that of it lying on the side.

Darrell
Newsgroups: sci.math