Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

computability and complexity

This class was created by Brainscape user Jason Swift. Visit their profile to learn more about the creator.

By: Jason Swift
Start Studying

Decks in this class (20)

L1 - Introduction
What question underpins the origi...,
Was,
Define what it means for a proble...
7  cards
L2 - Problems and Effective Procedures
Define a problem,
What are some examples of qualifi...,
What are some examples of unquali...
14  cards
L3 - WHILE Language
Why do we prefer a high level lan...,
Why is the while language a good ...,
How many data types does while ha...
17  cards
L4 - WHILE Semantics
What do semantics describe,
Semantics abstract away from hard...,
What are semantics independent of
20  cards
L5 - Extensions of WHILE
0  cards
L6 - Self-interpreter for WHILE
What is a universal while program,
How is the uwp similar to the utm,
What is the goal of having a self...
6  cards
L7 - Halting Problem
What was hilberts statement,
Define the decision problem and w...,
Define the halting problem
6  cards
L8 - Further Undecidable Problems
What is problem reduction,
How does problem reduction relate...,
How does problem reduction and th...
10  cards
L9 - Turing Church Thesis
Define the turing church thesis,
Define turing completeness,
What is a synonym for turing comp...
14  cards
L10 - Register Machine and Cellular Automata
What is a register machine,
What is the difference between re...,
What is the syntax for resetting ...
10  cards
L11 - Complexity Classes & Turing-Church Thesis
Define computable,
What is the relationship between ...,
Define feasbile problems
10  cards
L12 - Problems known to be in P
What is the cobham edmonds thesis,
What is a rebuttal to cobham edwa...,
Give an example of a decision pro...
5  cards
L13 - Problems now known to be in P
What does it mean if a problem is...,
What are 4 examples of problems n...,
What is the time complexity of ts...
5  cards
L14 - Problems in NP
What does np stand for,
What does it mean if a problem is...,
Explain how we know all p is in np
9  cards
L15 - The Million Dollar Question
How can we reduce the 3sat proble...,
Give the 3 steps of reducing 3sat...,
Define np np hard np complete pro...
4  cards
L16 - Parallel Computing
How can parallel computing be app...,
What is an issue with sequential ...,
Why does parallel computing not m...
7  cards
L17 - Molecular Computing
What is another name for molecula...,
What are the benefits of dna comp...,
What are the 4 operations perform...
6  cards
L18 - Chemical Reactions Network
Define crn
1  cards
L19 - Quantum Computing
Define superposition,
What is the purpose of quantum co...,
Explain how the schrodingers cat ...
13  cards
L20 - Quantum Algorithms and Quantum Computers
What is the aim of shors factoris...,
What is brute force complexity of...,
What time can shors perform facto...
5  cards

More about
computability and complexity

  • Class purpose General learning

Learn faster with Brainscape on your web, iPhone, or Android device. Study Jason Swift's Computability and Complexity flashcards now!

How studying works.

Brainscape's adaptive web mobile flashcards system will drill you on your weaknesses, using a pattern guaranteed to help you learn more in less time.

Learn more about spaced repetition

Add your own flashcards.

Either request "Edit" access from the author, or make a copy of the class to edit as your own. And you can always create a totally new class of your own too!

What's Brainscape anyway?

Brainscape is a digital flashcards platform where you can find, create, share, and study any subject on the planet.

We use an adaptive study algorithm that is proven to help you learn faster and remember longer....

Looking for something else?

Complex
  • 3 decks
  • 758 flashcards
  • 9 learners
Decks: Exam 1, Exam 2, Exam 3, And more!
GCSE Computer Science (OCR)
  • 15 decks
  • 1702 flashcards
  • 1746 learners
Decks: Definitions, 11 Systems Architecture, 12 Memory Complete, And more!
Find Flashcards
Make Flashcards
Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions