2016-2017 Bulletin

Catalog Search

Search Options

Contents

Programs of Study
Academic Calendar
Welcome to Portland State University
Admissions Requirements
Academic Records, Credit, and Appeals
Enrollment
Tuition and fees
Financial Aid and Scholarships
Undergraduate Studies
Graduate Studies
A to Z List of Student Services
Student Policies and Guidelines
Interdisciplinary Studies
Office of International Affairs
University Library
University Honors College
College of the Arts
School of Business Administration
Graduate School of Education
Maseeh College of Engineering and Computer Science
College of Liberal Arts and Sciences
OHSU-PSU School of Public Health
School of Social Work
College of Urban and Public Affairs
Directories
Courses
- Actg - Accounting
- Anth - Anthropology
- Ar - Arabic
- Arch - Architecture
- ArH - Art History
- Art - Art
- ASc - Arts & Sciences
- ASL - American Sign Language
- BA - Business Administration
- Bi - Biology
- BSt - Black Studies
- CCJ - Criminology & Criminal Justice
- CE - Civil Engineering
- CFS - Child & Family Studies
- Ch - Chemistry
- ChLa - Chicano-Latino
- Chn - Chinese
- CI - Curriculum & Instruction
- Comm - Communication
- Coun - Counseling
- CR - Conflict Resolution
- CS - Computer Science
  - 100
  - 200
  - 300
  - 400
  - 500
  - 600
- Dane - Danish
- D - Dance
- EAS - Engineering & Applied Science
- Ec - Economics
- ECE - Elect and Computer Engineering
- Ed - Education
- EE-Electrical Engineering
- ELP - Educational Ldrshp & Policy
- Eng - English
- ESM - Environmental Sci & Mgmt
- ESR - Environmental Sciences & Res
- ETM - Engineering Management
- FILM - Film
- Fin - Finance
- Finn - Finnish
- FPA - Fine and Performing Arts
- Fr - French
- Geog - Geography
- Ger - Germanic Languages
- G - Geology
- Grk - Greek
- GRN-Gender Race and Nations
- GSCM - Global Supply Chain Management
- Heb - Hebrew
- Hon - University Honors Program
- HSMP - Health Systems Management and Policy
- Hst - History
- Hum - Humanities
- Intl - International Studies
- ISQA - Infor Systems & Quant Analysis
- ISt - Interdisciplin St
- It - Italian
- ITP - Initial Teacher Preparation
- Jpn - Japanese
- JSt - Judaic Studies
- Kor - Korean
- Lat - Latin
- Lib - Library
- Ling - Applied Linguistics
- ME - Mechanical Engineering
- Mgmt - Management
- MGrk - Modern Greek
- MIM - Master of Intl Mgt
- Mktg - Marketing
- MSE - Materials Science Engineering
- MS - Military Science
- MTax - Taxation
- Mth - Mathematical Sciences
- MuEd - Music Education
- Mup - Applied Music
- Mus - Music
- NAS - Indigenous Nations Studies
- Norw - Norwegian
- OMSE - Software Engineering
- PAH - Public Administration: Health
- PAP-Public-Affairs-Policy
- PA - Public Administration
- PE - Physical Education
- Per - Persian
- PHE - Public Health Education
- Phl - Philosophy
- Ph - Physics
- Port - Portuguese
- PS - Political Science
- Psy - Psychology
- READ - READOregon
- RE - Real Estate
- RSt - Religious Studies
- Rus - Russian
- Sci - Science Ed: Center for
- Sc - Science: General
- Soc - Sociology
- Span - Spanish
- SpEd - Special Education
- SpHr - Speech & Hearing Sci
- SSc - Social Science: General
- Stat - Statistics
- Swah - Swahili
- Swed - Swedish
- SW - Social Work
- SySc - Systems Science
- SysE - Systems Engineering
- TA - Theater Arts
- Tur - Turkish
- ULib - Library Research
- UnSt - University Studies
- UPA-Urban and Public Affairs
- USP - Urban Studies & Planning
- VIET-Vietnamese
- WLL - World Languages & Literature
- Wr - Writing
- WS - Womens Studies

Catalog Links

Share

Print this page

CS 582 Theory of Computation: Advanced Topics

Complexity theory: study of resource bounded computation, the complexity classes (P, NP, PSPACE, and PH), NP-completeness, relativized computation, randomized classes.

Credits

3

Prerequisite

CS 311, 350.