What does computational complexity study?

The resources (time and space) needed to solve a problem as a function of input size n

Only whether a problem is solvable or not

The number of lines in an algorithm's code

The hardware speed needed to run a program

How are T(n) and S(n) defined for a Turing machine?

T(n) is the maximum number of steps and S(n) the maximum number of tape cells used on any input of length n

T(n) is the average number of steps, S(n) the number of states

T(n) is the number of states, S(n) the number of symbols

T(n) is the minimum steps, S(n) the minimum cells used

Which statement about P and NP is correct?

P is solved by a deterministic TM in polynomial time; NP by a non-deterministic TM in polynomial time (answers verifiable in polynomial time)

P needs exponential time; NP needs polynomial space

NP is solved by a deterministic TM in exponential time only

P and NP are proven to be equal

Which pairing of class inclusions and meaning is correct?

P is inside NP, which is inside PSPACE, which is inside EXPTIME; problems in P are called tractable

EXPTIME is inside P, and P problems are intractable

NP is inside P, and exponential-time problems are tractable

PSPACE is inside P, and sorting is intractable

Asked 2/7
2072 Chaitra
2073 Chaitra

Define computational complexity

Short answer

Computational complexity studies the time and space resources an algorithm needs as a function of input size n. Time complexity T(n) is the max steps; space complexity S(n) is max tape cells. It classifies problems into classes like P (polynomial time), NP, PSPACE, EXPTIME. Complexity separates tractable problems (in P) from intractable ones.

Define computational complexity. (Write a short note on computational complexities.)

Computational complexity is the study of the resources (mostly time and memory space) that an algorithm or Turing machine needs to solve a problem, as a function of the input size n. It classifies problems by how hard they are to solve, not just by whether they are solvable.

Measures

Time complexity T(n): the maximum number of steps (moves) a TM takes on any input of length n.
Space complexity S(n): the maximum number of tape cells the TM uses on any input of length n.

Complexities are expressed in asymptotic notation, such as O(n), O(n²) and O(2ⁿ), and are usually studied for the worst case.

Complexity classes

Class	Meaning
P	solvable by a deterministic TM in polynomial time, O(nᵏ)
NP	solvable by a non-deterministic TM in polynomial time (a solution can be verified in polynomial time)
PSPACE	solvable using polynomial space
EXPTIME	solvable by a deterministic TM in time $2^{p(n)}$ for some polynomial p

Known: P ⊆ NP ⊆ PSPACE ⊆ EXPTIME. Whether P = NP is an open problem.

Importance

Problems in P are called tractable (practical); problems that need exponential time are intractable for large n (for example the travelling salesman problem, as far as we know). Examples: sorting is O(n log n) (in P); SAT is in NP and is NP-complete.

Complexity theory separates problems that are merely hard from those that are undecidable, and it guides the choice between exact, approximate and heuristic algorithms.

✓ Answer checked by Claude Opus 5.5 (high effort)

All Theory of Computation chapter 6 questions →