Complexity - NP - completeness

4 important questions on Complexity - NP - completeness

Explain polynomially reduced (use problem A and B in your explanation)

Problem A can be polynomially reduced to problem B if there is a function T with polynomial running time that projects inputs for A to inputs for B such that x is a yes input for A if T(x) is  a yes input for B.

A =< B

T(X) transforms A to B in polynomial number of steps.

When is a problem NP-complete?

A problem is NP-complete when it is in NP and any problem within NP is polynomially reducible to this problem.

Thus, B is NP-Complete if B is in NP and
A =< B and A is in NP

How do you prove whether a problem is NP-complete (2 steps)

  1. Prove that the problem is NP
  2. Prove that a know NP-complete problem can be polynomially reduced to this problem
  • Works for a no-answer
  • Works for a yes answer
  • Reduction done in polynomial time
  • Higher grades + faster learning
  • Never study anything twice
  • 100% sure, 100% understanding
Discover Study Smart

Study polynomially reducable example slide 31 of complexity

Lekker bezig!

The question on the page originate from the summary of the following study material:

  • A unique study and practice tool
  • Never study anything twice again
  • Get the grades you hope for
  • 100% sure, 100% understanding
Remember faster, study better. Scientifically proven.
Trustpilot Logo