En anglais

Polynomial solving and certificate checking

Computing · Algorithms & Data Structures · ages 21-22

Name ______________________ Date ____________

Which object is a valid yes certificate for three-color map coloring?
- A list of every border length and every region's measured area
- A list of all regions and the number of borders around each one
- An allowed coloring with different colors across every border
What does membership in NP require for a decision problem?
- Both yes and no inputs have polynomially checkable short certificates
- Yes inputs have polynomially checkable short certificates
- Every input is solved deterministically in polynomial time
NP-hardness alone establishes that a problem is NP-complete.
Circle one: True False
Decision problem A reduces to B in polynomial time, preserving yes-or-no answers. B has a polynomial-time algorithm. What follows?
- A has no accepted certificate on any possible input
- B is NP-complete because it receives a reduction from A
- A has a polynomial-time algorithm
A proposed three-coloring assigns red to both regions sharing one border. What may the verifier conclude?
- Reject this coloring; another might work
- Reject every possible three-coloring of the entire map
- Prove the map-coloring problem lies outside the class NP
A correct deterministic polynomial-time algorithm is proved for one NP-complete decision problem. What follows?
- Only that problem enters P; other NP problems stay outside
- P = NP
- Polynomial-time certificate checking becomes impossible
Every NP problem reduces to puzzle H in polynomial time. No polynomial certificate verifier for H is known. Which conclusion is justified by these facts?
- H is NP-complete because a missing verifier proves membership
- H is NP-hard; NP membership is unproved
- H is in P because the reductions themselves supply a solver
A startup says its SAT solver proves P = NP because it finishes quickly on its customers' inputs. Which response is justified?
- These runs give no polynomial worst-case guarantee
- Fast customer runs prove a bound on every possible SAT input
- Customer runs prove SAT has no polynomial certificate verifier

Answer key

For grown-ups. Fold this page away before handing over the rest.

Polynomial solving and certificate checking W1-mt_wwmNVG_VnB-s1

An allowed coloring with different colors across every border · The coloring assigns one allowed color to every region and passes every shared-border check.
Yes inputs have polynomially checkable short certificates · NP requires polynomial-length certificates for yes inputs and a polynomial-time verifier. No certificate may be accepted for a no input.
False · NP-completeness requires NP-hardness and membership in NP. Hardness alone supplies only the reduction requirement.
A has a polynomial-time algorithm · Convert an A input to B and run B's algorithm. Answer preservation and polynomial bounds give a polynomial algorithm for A.
Reject this coloring; another might work · The red-red border rejects this certificate. A different assignment of colors might pass.
P = NP · Every NP problem reduces to the chosen target, putting NP inside P. The reverse containment already holds.
H is NP-hard; NP membership is unproved · The reductions establish NP-hardness. Not knowing a verifier neither proves NP membership nor proves that H is outside NP.
These runs give no polynomial worst-case guarantee · P requires a correct algorithm with a polynomial worst-case bound over all inputs. Selected successful runs do not establish that bound.