Search Header Logo

Theory

Authored by Amr Amin

Computers

University - Professional Development

Used 8+ times

Theory
AI

AI Actions

Add similar questions

Adjust reading levels

Convert to real-world scenario

Translate activity

More...

    Content View

    Student View

41 questions

Show all answers

1.

MULTIPLE CHOICE QUESTION

30 sec โ€ข 1 pt

The complexity Turning machine M is a polynomial time algorithm for PATH problem

true

false

2.

MULTIPLE CHOICE QUESTION

30 sec โ€ข 1 pt

A function f is computable if there is a Turing Machine M such that:

๐‘ž0๐‘ค >โˆ— ๐‘ž๐‘“๐‘“(๐‘ค) where 0<i<f, for all wโˆˆ ๐ท๐‘œ๐‘š๐‘Ž๐‘–๐‘› (D)

true

false

3.

MULTIPLE CHOICE QUESTION

30 sec โ€ข 1 pt

NP-class is the languages that have exponential time verifiers

true

false

4.

MULTIPLE CHOICE QUESTION

30 sec โ€ข 1 pt

By modifying the brute-force algorithm, We can easily obtain an exponential time algorithm for the Hamiltonian path (HAMPATH) problem

true

false

5.

MULTIPLE CHOICE QUESTION

30 sec โ€ข 1 pt

The HAMPATH problem has a feature called polynomial verifiability that is important for understanding its complexity

true

false

6.

MULTIPLE CHOICE QUESTION

30 sec โ€ข 1 pt

NP-class is the languages that have polynomial time verifiers

true

false

7.

MULTIPLE CHOICE QUESTION

30 sec โ€ข 1 pt

A language L is Turing-Acceptable if there is a Turing machine M that accepts L and Turing-Recognizable

true

false

Access all questions and much more by creating a free account

Create resources

Host any resource

Get auto-graded reports

Google

Continue with Google

Email

Continue with Email

Classlink

Continue with Classlink

Clever

Continue with Clever

or continue with

Microsoft

Microsoft

Apple

Apple

Others

Others

Already have an account?