Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!seismo!mimsy!oddjob!hao!boulder!sunybcs!rutgers!iuvax!pur-ee!uiucdcs!uiucdcsp!johnson
From: johnson@uiucdcsp.cs.uiuc.edu
Newsgroups: comp.ai
Subject: Re: Is Computer Science Science?
Message-ID: <76600013@uiucdcsp>
Date: Thu, 10-Sep-87 05:27:00 EDT
Article-I.D.: uiucdcsp.76600013
Posted: Thu Sep 10 05:27:00 1987
Date-Received: Sat, 12-Sep-87 15:40:18 EDT
References: <5113@sunybcs.UUCP>
Lines: 18
Nf-ID: #R:sunybcs.UUCP:5113:uiucdcsp:76600013:000:1009
Nf-From: uiucdcsp.cs.uiuc.edu!johnson    Sep 10 04:27:00 1987


There is a general rule that disciplines with names like XXX Science are
not a science.  In spite of that, there are some general laws that arise
out of CS.  My favorite are all from computability and complexity theory,
though I do not do that kind of research and don't plan to.

Undecideability -- just because a question has an answer doesn't mean
that there is a method to answer it.  E.g. all programs will either
terminate or not terminate, but the halting problem is undecideable.

NP complete problems -- just because a proposed answer is very easy to
check for correctness does not mean that the question is easy to solve.
NP complete problems are those whose answer can be checked in polynomial
time but where any method for finding the solution must essentially
check all possible solutions, taking exponential time.  In a similar
manner, a proof can be easily checked for correctness, but it is
undecideable (in any interesting theory) whether there exists a proof
or not for a particular theorem.