Let t: N \to R^+ be a function. The time complexity class, TIME( t ( n ) ) is defined as the collection of all languages that are decidable by an O( t ( n ) ) time Turing machine.

The problem of testing whether a directed graph contains a Hamiltonian path connecting two specified nodes is solvable in polynomial time. 

The following algorithm M is a polynomial-time algorithm.

M = “On input ⟨G, s, t⟩, where G is a directed graph with nodes s and t:

1. Place a mark on node s.

2. Repeat the following until no additional nodes are marked:

3. Scan all the edges of G. If an edge (a, b) is found going from

   a marked node a to an unmarked node b, mark node b.

4. If t is marked, accept. Otherwise, reject.”

The problem defined as C = {x| x = pq, for integers p, q > 1} is polynonially verifiable. 

3SAT is polynomial time reducible to CLIQUE.

Which is the time complexity of the following Turing machine 

M = “On input string w of length n:

1. Scan across the tape and reject if a 0 is found to the right of a 1.

2. Repeat as long as some 0s and some 1s remain on the tape:

3. Scan across the tape, checking whether the total number of

   0s and 1s remaining is even or odd. If it is odd, reject.

4. Scan again across the tape, crossing off every other 0 starting with the first 0, and then crossing off every other 1 starting

   with the first 1.

5. If no 0s and no 1s remain on the tape, accept. Otherwise,

   reject .”

Can we develop a polynomial algorithm for every NP class problem? 

A function f: \Sigma^* \to \Sigma^* is a computable function if some Turing machine M , on every input w, halts with just f(w) on its tape.

Which of the following languages is decidable