Study guides · Intermediate

Computability, Reductions, P, and NP

Separate computability from efficiency and follow the direction of a polynomial-time reduction.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Termination and efficiency are separate questions
  2. P and NP classify decision problems
  3. A reduction has a direction
  4. NP-completeness and actual workloads
  5. Ask Logeia about this articleCheck your understanding

Termination and efficiency are separate questions

A decision problem asks for a yes-or-no answer. Decidability means there is a procedure that halts with the correct answer on every valid input. This definition does not require a practical running time. Exhaustively enumerating a finite candidate set may decide a problem while requiring exponentially many steps as the input grows. Undecidability is different: for a problem such as general program halting, no algorithm decides all instances. Keep impossibility of a universal terminating procedure separate from the difficulty of accelerating an existing terminating algorithm.

P and NP classify decision problems

P contains decision problems solvable in polynomial time measured against input length. NP can be characterized by polynomial-size certificates for yes instances that a polynomial-time verifier can check. For satisfiability, an assignment of Boolean values is a candidate certificate: evaluating the formula under that assignment is efficient. Finding such an assignment is a different task. NP does not mean “not polynomial,” and P is contained in NP. State the input encoding and the decision version being discussed, because optimization tasks and numerical magnitudes can otherwise hide important changes in the complexity claim.

A reduction has a direction

A polynomial-time reduction from A to B efficiently transforms an instance of A into an instance of B while preserving its answer. If B has an efficient solver, the transformation supplies an efficient way to solve A. Consequently, to demonstrate that B is at least as hard as a known hard problem A, reduce A to B, not the reverse. The transformation itself must satisfy the time and size bounds. Check both yes and no cases rather than showing only that one convenient example maps correctly. Reduction direction is essential to the conclusion.

NP-completeness and actual workloads

An NP-complete problem is in NP and receives polynomial-time reductions from every NP problem. Whether P equals NP remains unresolved, so NP-completeness is not a proof that no polynomial-time algorithm can ever exist. A worst-case classification also does not say that every practical instance is equally hard. Structure, parameter restrictions, approximation and heuristics may make useful workloads tractable. When using those approaches, state whether the answer is exact, what input restrictions matter and what happens at a time limit. Practical success and a worst-case theorem can both be true without contradicting one another.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 22

Choose a learning path