CS 579

spring 2009

All Classes

Computational Complexity

Credit: 4 hours.

Turing machines; determinism and non-determinism; time and space hierarchy theorems; speed-up and tape compression; Blum axioms; structure of complexity classes NP, P, NL, L, and PSPACE; complete problems; randomness and complexity classes RP, RL, and BPP; alternation, polynomial-time hierarchy; circuit complexity, parallel complexity, NC, and RNC; relativized computational complexity; time-space trade-offs. Same as ECE 579 and MATH 578. Prerequisite: CS 473 or CS 475.

Status Icon Legend

: Section Status Closed
: Section Status Open
: Section Status Pending
: Section Status Open (Restricted)
: Section Status Unknown

Section Status updates every 10 minutes.

- CS 101
- CS 105
- CS 125
- CS 173
- CS 196
- CS 199
- CS 210
- CS 225
- CS 231
- CS 232
- CS 241
- CS 242
- CS 296
- CS 357
- CS 373
- CS 397
- CS 410
- CS 411
- CS 413
- CS 414
- CS 417
- CS 418
- CS 420
- CS 421
- CS 422
- CS 423
- CS 425
- CS 428
- CS 429
- CS 431
- CS 433
- CS 435
- CS 438
- CS 439
- CS 440
- CS 450
- CS 457
- CS 460
- CS 461
- CS 462
- CS 463
- CS 473
- CS 475
- CS 477
- CS 482
- CS 493
- CS 494
- CS 498
- CS 499
- CS 512
- CS 519
- CS 523
- CS 524
- CS 525
- CS 526
- CS 533
- CS 543
- CS 546
- CS 548
- CS 555
- CS 556
- CS 572
- CS 576
- CS 579
- CS 591
- CS 597
- CS 598
- CS 599

Detail	Status		CRN	Type	Section	Time	Day	Location	Instructor