Skip to main content

The National Challenge in Computer Science and Technology (1988) / Chapter Skim
Currently Skimming:

8 Theoretical Computer Science
Pages 60-63

The Chapter Skim interface presents what we've algorithmically identified as the most significant single chunk of text within every page in the chapter.
Select key terms on the right to highlight them within pages of the chapter.


From page 60...
... , theoretical computer science plays a very different role within computer science than, say, theoretical physics plays within physics. Theoretical physicists seek to understand the physical universe, which exists independently.
Read the entire page →
From page 61...
... The theory developed to date enables computer scientists to demonstrate that various problems are easily solvable or provably intractable and further enables them to determine that numerous problems have essentially the same complexity. Computational complexity thus serves much the same function in computer science that the laws of thermodynam~cs play in the physical sciences (Packet and Traub 1987~; it strives to determine the limits of the possible.
Read the entire page →
From page 62...
... Fundamental advances in these areas have drawn on mathematical logic to produce a conceptual framework that facilitates computer language translation on conventional architectures. Twenty-five years ago, for example, the generation of a Fortran compiler was considered a legitimate research topic, involving 20 to 50 person-years of work; today, compilers for advanced languages on conventional uniprocessors are routinely constructed by students over the course of a single academic semester.
Read the entire page →
From page 63...
... At the same tune, new and evolving architectures, especially multiprocessors, are presenting designers of compilers with new challenges and long development times, thereby attesting to the field's continued growth. CRYPTOLOGY Although code-making is an ancient craft, dating back to the Roman Empire, computer science theory has played an essential role in adapting encryption to meet the special demands of complex modern society.
Read the entire page →

Key Terms

  • theoretical computer
  • computational complexity
  • theory developed
  • linear programming
  • resources required

  • theoretical work
  • computational resources
  • computer languages
  • theoretical advances
  • adapting encryption

  • password publicly
  • provably intractable
  • fortran compiler
  • complex modern
  • theoretical physics

  • academic semester
  • developed linear
  • languages theoretical
  • research topic
  • highly efficient

  • sales representative
  • intrinsic limits
  • complexity include
  • legitimate research
  • science theory

  • intrinsic uncertainty
  • physics plays
  • enables computer
  • programming algorithm
  • sorting algorithm


    • This material may be derived from roughly machine-read images, and so is provided only to facilitate research.
    More information on Chapter Skim is available.