Skip to main content Accessibility help
×
  1. Home
  2. Search

Refine search

Refine search

Access:
Content type:
Publication date:
Apply   From and To filters
Subject: Show more
Journals Show more
Publishers: Show more
Societies Show more
Series: Show more
Collections: Show more

Actions for selected content:

Select all | Deselect all
  • View selected items
  • Export citations
  • Download PDF (zip)
  • Save to Kindle
  • Save to Dropbox
  • Save to Google Drive

Save Search

You can save your searches here and later view and run them again in "My saved searches".

Please provide a title, maximum of 40 characters.
Cancel
×

2 results

  • 3 - Space Complexity

  • from Part I - Time and Space
  • Thomas Watson, University of Memphis
  • Book:
    Complexity in Computer Science
    Published online:
    09 October 2026
    Print publication:
    19 November 2026, pp 137-161

  • Summary

    This chapter is about the prospect of proving that certain problems do not have logarithmic-space algorithms (are not in L). Results proven in this chapter include PSPACE-completeness and NL-completeness of classic problems, and the counterintuitive theorems PSPACE=NPSPACE and NL=coNL.

  • 15 - Verification

  • from Part III - Scope Of Complexity
  • Thomas Watson, University of Memphis
  • Book:
    Complexity in Computer Science
    Published online:
    09 October 2026
    Print publication:
    19 November 2026, pp 544-576

  • Summary

    This chapter covers a complexity-theoretic perspective on software verification: An efficient verifier wants to be convinced that some computation’s output is correct, given information by a more powerful prover. Interaction (back-and-forth communication between prover and verifier) is surprisingly effective at convincing a verifier with much less computational resources than would be needed without the prover’s help. This is applicable when someone delegates an intensive computation to an untrusted cloud computing service and wants to be convinced the computation was performed correctly. The chapter concludes with the surprising power of zero-knowledge proofs, in which the prover convinces the verifier without revealing any further information.