Theory

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

• true

• false

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

NP-class is the languages that have exponential time verifiers

• true

• false

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

• true

• false

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

• true

• false

NP-class is the languages that have polynomial time verifiers

• true

• false

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

• true

• false

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

• true

• false

A language S is Recursively-enumerable if there is a Turing machine N that accepts S

• true

• false

Polynomial differences in complexity running time are considered to be large whereas exponential differences are considered to be small

• true

• false